hdu 2795
7437 ワード
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=2795
構想:配列はmin(h,n)の大きさを開くだけでいい...セグメントツリーの最後のレイヤは、各ローの残りの量であり、親ノードは現在のサブツリーの最大連続空きを保持します.
View Code
構想:配列はmin(h,n)の大きさを開くだけでいい...セグメントツリーの最後のレイヤは、各ローの残りの量であり、親ノードは現在のサブツリーの最大連続空きを保持します.
View Code
1 #include<iostream>
2 const int MAXN=200007;
3 using namespace std;
4 int h,w,n;
5 int MAX[MAXN<<2];
6
7 void Push_Up(int rt){
8 MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
9 }
10
11 void Build(int l,int r,int rt){
12 MAX[rt]=w;
13 if(l==r)return ;
14 int m=(l+r)>>1;
15 Build(l,m,rt<<1);
16 Build(m+1,r,rt<<1|1);
17 }
18
19 int Query(int x,int l,int r,int rt){
20 if(l==r){
21 MAX[rt]-=x;
22 return l;
23 }
24 int m=(l+r)>>1;
25 int ret=(MAX[rt<<1]>=x)?Query(x,l,m,rt<<1):Query(x,m+1,r,rt<<1|1);
26 Push_Up(rt);
27 return ret;
28 }
29
30
31 int main(){
32 while(~scanf("%d%d%d",&h,&w,&n)){
33 if(h>n)h=n;
34 Build(1,h,1);
35 while(n--){
36 int x;
37 scanf("%d",&x);
38 if(MAX[1]<x){
39 printf("-1
");
40 }else
41 printf("%d
",Query(x,1,h,1));
42 }
43 }
44 return 0;
45 }