HDU_2795

    尽管h的范围很大，但有一个有效的优化就是如果h>n那么可以直接令h=n，因为即便每行只贴1张海报，最后也只会占n行。

    之后就是将每行看成一个点，用线段树记录每行还剩多少空间即可。

#include
     
       #include
      
        #define MAXD 200010 int H, W, N, tree[4 * MAXD]; void build(int cur, int x, int y) {
   int mid = (x + y) / 2, ls = 2 * cur, rs = 2 * cur + 1;     tree[cur] = W; if(x == y) return ;     build(ls, x, mid);     build(rs, mid + 1, y); } void update(int cur) {
   int ls = 2 * cur, rs = 2 * cur + 1;     tree[cur] = tree[ls] > tree[rs] ? tree[ls] : tree[rs]; } void init() {
   if(H > N)         H = N;     build(1, 1, H); } void refresh(int cur, int x, int y, int k) {
   int mid = (x + y) / 2, ls = 2 * cur, rs = 2 * cur + 1; if(x == y)     {
           printf("%d\n", x);         tree[cur] -= k; return ;     } if(tree[ls] >= k)         refresh(ls, x, mid, k); else         refresh(rs, mid + 1, y, k);     update(cur); } void solve() {
   int i, j, k; for(i = 0; i < N; i ++)     {
           scanf("%d", &k); if(tree[1] < k)             printf("-1\n"); else             refresh(1, 1, H, k);     } } int main() {
   while(scanf("%d%d%d", &H, &W, &N) == 3)     {
           init();         solve();     } return 0; }