POJ-2828-Buy Tickets

编程技术  /  houtizong 发布于 3年前   131

POJ-2828-Buy Tickets

http://poj.org/problem?id=2828

线段树，逆序插入

#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>using namespace std;#define N 200010struct cam{int x,y;int num;}list[N*8];int pos[N],value[N],ans[N];int n;void build(int k,int x,int y)  //用线段树存储区间内还有多少位子没有被占{list[k].x=x;list[k].y=y;list[k].num=(y-x+1);if(x==y)return;int mid;mid=(x+y)/2;build(k<<1,x,mid);build(k<<1|1,mid+1,y);}void find(int k,int pos,int value){list[k].num--;if(list[k].x==list[k].y){ans[list[k].x]=value;return;}if(list[k<<1].num>=pos)find(k<<1,pos,value);elsefind(k<<1|1,pos-list[k<<1].num,value);}int main(){int i;while(scanf("%d",&n)!=EOF){for(i=1;i<=n;i++)scanf("%d%d",&pos[i],&value[i]);build(1,1,n);for(i=n;i>=1;i--)find(1,pos[i]+1,value[i]);for(i=1;i<=n;i++){if(i==n)printf("%d\n",ans[i]);elseprintf("%d ",ans[i]);}}return 0;}