hdu 2795

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=2795
構想:配列は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 }