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); else find(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]); else printf("%d ",ans[i]); } } return 0;}
分享到:
相关推荐
poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
POJ-3299解题 C++源代码 Description Adapted from Wikipedia, the free encyclopedia The humidex is a measurement used by Canadian meteorologists to reflect the combined effect of heat and humidity. It...
西北工业大学-c语言-POJ-题目及答案-第七季.doc
poj-2528 Mayor's posters 测试数据及答案
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
算法-炮兵阵地(POJ-1185)(包含源程序).rar
算法-开关问题(POJ-1830)(包含源程序).rar
算法-青蛙的约会(POJ-1061)(包含源程序).rar
北大POJ2002-Squares 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
POJ - 2136. VerticalHistogram(统计字母个数)题目链接题目就是给你四行字符串,然后要你统计大写字母(只有大写字母)的个数,然后以特定
北大POJ2525-Text Formalization【TrieTree】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/XW4FQ3
poj 1028 Web Navigation 的代码,已通过!