Billboard HDU - 2795

 1 #include <map>
 2 #include <stack>
 3 #include <queue>
 4 #include <cmath>
 5 #include <string>
 6 #include <limits>
 7 #include <cstdio>
 8 #include <cstdlib>
 9 #include <cstring>
10 #include <iostream>
11 #include <algorithm>
12 #define Scc(c) scanf("%c",&c)
13 #define Scs(s) scanf("%s",s)
14 #define Sci(x) scanf("%d",&x)
15 #define Sci2(x, y) scanf("%d%d",&x,&y)
16 #define Sci3(x, y, z) scanf("%d%d%d",&x,&y,&z)
17 #define Scl(x) scanf("%I64d",&x)
18 #define Scl2(x, y) scanf("%I64d%I64d",&x,&y)
19 #define Scl3(x, y, z) scanf("%I64d%I64d%I64d",&x,&y,&z)
20 #define Pri(x) printf("%d\n",x)
21 #define Prl(x) printf("%I64d\n",x)
22 #define Prc(c) printf("%c\n",c)
23 #define Prs(s) printf("%s\n",s)
24 #define For(i,x,y) for(int i=x;i<y;i++)
25 #define For_(i,x,y) for(int i=x;i<=y;i++)
26 #define FFor(i,x,y) for(int i=x;i>y;i--)
27 #define FFor_(i,x,y) for(int i=x;i>=y;i--)
28 #define Mem(f, x) memset(f,x,sizeof(f))
29 #define LL long long
30 #define ULL unsigned long long
31 #define MAXSIZE 200005
32 #define INF 0x3f3f3f3f
33 const int mod=1e9+7;
34 const double PI = acos(-1.0);
35 
36 using namespace std;
37 struct node
38 {
39     int left,right;
40     int maxx;
41 } tree[MAXSIZE*4];
42 int a[MAXSIZE];
43 int h,w;
44 void build (int i, int left,int right)
45 {
46     tree[i].left=left;
47     tree[i].right=right;
48     if(left==right)
49     {
50         tree[i].maxx=w;
51         return ;
52     }
53     build(i<<1,left,(left+right)/2 );
54     build(i<<1|1,(left+right)/2+1,right);
55     tree[i].maxx=max(tree[i<<1].maxx,tree[i<<1|1].maxx);
56 }
57 int query(int i,int l,int r,int v)
58 {
59     if(l==r)
60     {
61         tree[i].maxx-=v;
62         return l;// 返回叶子的位置，即行位置
63     }
64     int mid=(l+r)/2;
65     int sum=0;
66     if(v<=tree[i<<1].maxx)
67         sum=query(i<<1,l,mid,v);
68     else
69         sum= query(i<<1|1,mid+1,r,v);
70     tree[i].maxx= max(tree[i<<1].maxx,tree[i<<1|1].maxx);
71     return sum;
72 }
73 int main()
74 {
75     int n;
76     while(~Sci3(h,w,n))
77     {
78         h=min(h,n);//这里是缩小建树时的储存空间，当h>n时，最多只需要n行即可。
79         build(1,1,h);
80         int a;
81         For_(i,1,n)
82         {
83             Sci(a);
84             if(tree[1].maxx<a)//判断是否还能放广告
85                 Pri(-1);
86             else
87                 Pri(query(1,1,h,a));
88         }
89     }
90     return 0;
91 }