首页 > 代码库 > 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;}
View Code

 

hdu-2871