【hdu2795】Billboard

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #define MAXN 222222
 6 using namespace std;
 7 int segtree[MAXN*4];
 8 int n,h,t,x,ans;
 9 void adddata(int now)
10 {
11     segtree[now]=max(segtree[(now<<1)],segtree[(now<<1)+1]);
12 }
13 void buildtree(int now,int l,int r)
14 {
15     if (l==r)    {segtree[now]=t;    return;}
16     int mid=(l+r)>>1;
17     buildtree((now<<1),l,mid);
18     buildtree((now<<1)+1,mid+1,r);
19     adddata(now);
20 }
21 int query(int now,int l,int r,int v)
22 {
23     if (l==r)    {segtree[now]-=v;return l;}
24     int mid=(l+r)>>1;
25     if (segtree[(now<<1)]>=v)    ans=query((now<<1),l,mid,v);
26     else    ans=query((now<<1)+1,mid+1,r,v);
27     adddata(now);
28     return ans;
29 }
30 int main()
31 {
32     int i,p;
33     while (~scanf("%d%d%d",&h,&t,&n))
34     {
35         h=min(h,n);
36         buildtree(1,1,h);
37         for (i=1;i<=n;i++)
38         {
39             scanf("%d",&x);
40             if (x>segtree[1])    printf("-1\n");
41             else{    p=query(1,1,h,x);    printf("%d\n",p);}
42         }
43     }
44     return 0;
45 }