【HDU】2795 Billboard

 1 #include<cstdio>
 2 #define MAXN 200010
 3 #define MIN(a,b) ((a)>(b)?(b):(a))
 4 #define MAX(a,b) ((a)>(b)?(a):(b))
 5 int w,tree[MAXN<<2];
 6 inline void PushUp(int rt)
 7 {
 8     tree[rt]=MAX(tree[rt<<1],tree[rt<<1|1]);
 9 }
10 void Build(int L,int R,int rt)
11 {
12     if(L==R)
13         tree[rt]=w;
14     else
15     {
16         int mid=(L+R)>>1;
17         Build(L,mid,rt<<1);
18         Build(mid+1,R,rt<<1|1);
19         PushUp(rt);
20     }
21 }
22 int Query(int val,int L,int R,int rt)
23 {
24     if(L==R)
25     {
26         tree[rt]-=val;
27         return L;
28     }
29     else
30     {
31         int ans,mid=(L+R)>>1;
32         if(val<=tree[rt<<1])
33             ans=Query(val,L,mid,rt<<1);
34         else
35             ans=Query(val,mid+1,R,rt<<1|1);
36         PushUp(rt);
37         return ans;
38     }
39 }
40 int main()
41 {
42     int h,i,x,n;
43     while(~scanf("%d%d%d",&h,&w,&n))
44     {
45         h=MIN(h,n);
46         Build(1,h,1);
47         for(i=0;i<n;i++)
48         {
49             scanf("%d",&x);
50             if(tree[1]<x)
51                 puts("-1");
52             else
53                 printf("%d\n",Query(x,1,h,1));
54         }
55     }
56     return 0;
57 }
新博客：www.zhixiangli.com