【HDOJ】2795 Billboard

线段树。注意h范围（小于等于n）。

 #include <stdio.h>
 #include <string.h> #define MAXN 200005
 #define lson l, mid, rt<<1
 #define rson mid+1, r, rt<<1|1
 #define mymax(x, y) (x>y) ? x:y int nums[MAXN<<];
 int h, w; void PushUP(int rt) {
     nums[rt] = mymax(nums[rt<<], nums[rt<<|]);
 } void build(int l, int r, int rt) {
     int mid;
     nums[rt] = w;     if (l == r)
         return ;     mid = (l+r)>>;
     build(lson);
     build(rson);
 } int query(int wi, int l, int r, int rt) {
     int mid, ret;     if (l == r) {
         nums[rt] -= wi;
         return l;
     }
     mid = (l+r)>>;     if (nums[rt<<] >= wi)
         ret = query(wi, lson);
     else
         ret = query(wi, rson);     PushUP(rt);
     return ret;
 } int main() {
     int n, wi;     while (scanf("%d%d%d", &h, &w, &n) != EOF) {
         if (h > n)
             h = n;      // h < n
         build(, h, );
         while (n--) {
             scanf("%d", &wi);
             if (nums[] < wi)
                 printf("-1\n");
             else
                 printf("%d\n", query(wi, , h, ));
         }
     }     return ;
 }