Main » 2013 October 20 » [POJ Hotel]终于A了。
12:58 PM [POJ Hotel]终于A了。 |
还是GSS的思想把区间分开，段用lazy-tag更新(ps:写死了)#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<vector> #include<set> #include<map> #include<string> #include<algorithm> #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) #define pb push_back #define mp make_pair #define LC(x) ((x)<<1) #define RC(x) (((x)<<1)+1) #define N 50100 using namespace std; typedef long long LL; typedef long double LD; struct node { int l,r,fill,lm,rm,om; int dis(){return r-l+1;} void init(){lm=rm=om=dis();fill=0;} void calc(){if (fill==0) lm=rm=om=dis();else if (fill==1) lm=rm=om=0;} }; struct segtree { node tree[3*N]; void update(int x) { node lc=tree[LC(x)],rc=tree[RC(x)]; if (lc.fill==0) tree[x].lm=lc.lm+rc.lm;else tree[x].lm=lc.lm; if (rc.fill==0) tree[x].rm=rc.rm+lc.rm;else tree[x].rm=rc.rm; tree[x].om=max(lc.om,rc.om); tree[x].om=max(tree[x].om,tree[x].lm); tree[x].om=max(tree[x].om,tree[x].rm); tree[x].om=max(tree[x].om,lc.rm+rc.lm); if (lc.fill==1&&rc.fill==1) tree[x].fill=1; else if (lc.fill==0&&rc.fill==0) tree[x].fill=0; else tree[x].fill=-1; } void pushdown(int x) { if (tree[x].fill==-1) return; if (tree[x].fill==0) { tree[LC(x)].fill=0;tree[LC(x)].calc(); tree[RC(x)].fill=0;tree[RC(x)].calc(); }else { tree[LC(x)].fill=1;tree[LC(x)].calc(); tree[RC(x)].fill=1;tree[RC(x)].calc(); } tree[x].fill=-1; } void build(int x,int L,int R) { tree[x].l=L;tree[x].r=R;int M=(L+R)>>1; if (L==R) {tree[x].init();return;} build(LC(x),L,M);build(RC(x),M+1,R);update(x); } void insert(int x,int L,int R,int d) { if (tree[x].l==L&&tree[x].r==R) {tree[x].fill=d;tree[x].calc();return;} pushdown(x); int M=(tree[x].l+tree[x].r)>>1; if (R<=M) insert(LC(x),L,R,d); else if (L>M) insert(RC(x),L,R,d); else {insert(LC(x),L,M,d);insert(RC(x),M+1,R,d);} update(x); } int query(int x,int w) { if (tree[x].l==tree[x].r) return tree[x].l; pushdown(x); if (tree[LC(x)].om>=w) return query(LC(x),w); else if (tree[LC(x)].rm+tree[RC(x)].lm>=w) return tree[LC(x)].r-tree[LC(x)].rm+1; else if (tree[RC(x)].om>=w) return query(RC(x),w); else return 0; } }Tree; int main() { ios::sync_with_stdio(false); int n,m,i,ans,op,t1,t2; while (scanf("%d %d",&n,&m)!=EOF) { Tree.build(1,1,n); FOR(i,1,m) { scanf("%d",&op); if (op==1) { scanf("%d",&t1);int ans=Tree.query(1,t1); printf("%d\n",ans); if (ans) Tree.insert(1,ans,ans+t1-1,1); }else if (op==2) { scanf("%d %d",&t1,&t2); Tree.insert(1,t1,t1+t2-1,0); } } } return 0; } |
|
|
| Total comments: 0 | |