首页 > 代码库 > hdu-2871
hdu-2871
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<set>#include<cmath>#define lson r,m,rt<<1#define rson m+1,r,rt<<1|1const int maxn=55555;using namespace std;int lsum[maxn<<2],rsum[maxn<<2],sum[maxn<<2];int cover[maxn<<2];struct node{ int first;int last; bool operator < (const node &rhs) const { return rhs.first>first; }};set<node>s;set<node>::iterator itr;void pushUp(int rt,int m){ rsum[rt]=rsum[rt<<1|1]; lsum[rt]=lsum[rt<<1]; if(lsum[rt]==(m-(m>>1))) lsum[rt]=lsum[rt]+lsum[rt<<1|1]; if(rsum[rt]==m>>1) rsum[rt]=rsum[rt]+rsum[rt<<1]; sum[rt]=max(rsum[rt<<1]+lsum[rt<<1|1],max(sum[rt<<1],sum[rt<<1|1]));}void build(int l,int r,int rt){ if(l==r) { lsum[rt]=rsum[rt]=sum[rt]=1; cover[rt]=-1; return ; } int m=(l+r)>>1; build(lson); build(rson); pushUp(rt,r-l+1);}int query(int d,int l,int r,int rt){ return 1;}void update(int d,int L,int R,int l,int r,int rt){ return;}int main(){ int n,m; while(scanf("%d%d",&n,&m)!=EOF) { s.clear(); node w; build(1,n,1); for(int i=0;i<m;i++){ char str[10]; int d; scanf("%s",str); if(str[0]==‘N‘){ scanf("%d",&d); if(d>sum[1]) printf("Reject New\n"); else{ int a=query(d,1,n,1); w.first=a;w.last=a+d; s.insert(w); update(1,a,a+d,1,n,1); printf("New at %d\n",a); } } if(str[0]==‘F‘) { scanf("%d",&d); int state=1,a,b; for(itr=s.begin();itr!=s.end();itr++) { if(itr->first<=d&&itr->last>=d){ a=itr->first;b=itr->last; state=0; break; } } if(state) printf("Reject Free\n"); else { update(0,a,b,1,n,1); } } } } return 0;}
hdu-2871
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。