1 //Accepted    6396 KB    3046 ms  2 //线段树  3 //由于n只有200000，我们可以知道，当h>200000时，大于200000的部分是没有用的  4 //所以我们可以用n来创建线段树  5 //我的思路是：  6 //维护一个已用区段的线段树  7 //用len表示当前已用的区段  8 //当需要贴一个宽度为wi的announcement时，先判断已用的区段能不能放下，如果不能这考虑len+1 （len+1<n && len+1<h）  9 //如果上述两种情况都不能放下，这放不下，output -1； 10 //test: 11 //3 6 3 12 //4 13 //3 14 //2 15 //answer:1 2 1 16 #include <cstdio> 17 #include <cstring> 18 #include <iostream> 19 #include <queue> 20 #include <cmath> 21 #include <algorithm> 22 using namespace std; 23 /** 24   * This is a documentation comment block 25   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！ 26   * @authr songt 27   */ 28 const int imax_n = 200005; 29 int max(int a,int b) 30 { 31     return a>b?a:b; 32 } 33 struct node 34 { 35     int l,r; 36     int tmax; 37 }f[imax_n*4]; 38 int n,width,height; 39 int w; 40 void build(int t,int l,int r) 41 { 42     f[t].l=l; 43     f[t].r=r; 44     f[t].tmax=width; 45     if (l==r) 46     { 47         return ; 48     } 49     int mid=(l+r)/2; 50     build(2*t,l,mid); 51     build(2*t+1,mid+1,r); 52 } 53 int query(int t,int l,int r) 54 { 55     if (f[t].l==l && f[t].r==r) 56     { 57         return f[t].tmax; 58     } 59     int mid=f[t].l+(f[t].r-f[t].l)/2; 60     if (r<=mid) return query(2*t,l,r); 61     else 62     { 63         if (l>mid) return query(2*t+1,l,r); 64         else return max(query(2*t,l,mid),query(2*t+1,mid+1,r)); 65     } 66 } 67 void update(int t,int l,int c) 68 { 69     if (f[t].l==l && f[t].r==l) 70     { 71         f[t].tmax=f[t].tmax-c; 72         return ; 73     } 74     int mid=f[t].l+(f[t].r-f[t].l)/2; 75     if (l<=mid) update(2*t,l,c); 76     else update(2*t+1,l,c); 77     f[t].tmax=max(f[2*t].tmax,f[2*t+1].tmax); 78 } 79 int queryid(int t,int sw) 80 { 81     if (f[t].l==f[t].r && f[t].tmax>=sw) 82     { 83         return f[t].l; 84     } 85     if (f[2*t].tmax>=sw) return queryid(2*t,sw); 86     else return queryid(2*t+1,sw); 87 } 88 void slove() 89 { 90     int len=1; 91     for (int i=0;i<n;i++) 92     { 93         scanf("%d",&w); 94         if (w>width) 95         { 96             printf("-1\n"); 97             continue; 98         } 99         int temp_w=query(1,1,len);100         if (temp_w>=w)101         {102             int t=queryid(1,w);103             printf("%d\n",t);104             update(1,t,w);105         }106         else107         {108             if (len<height && len<n)109             {110                 printf("%d\n",len+1);111                 update(1,len+1,w);112                 len++;113             }114             else115             {116                 printf("-1\n");117             }118         }119     }120 }121 int main()122 {123     while (scanf("%d%d%d",&height,&width,&n)!=EOF)124     {125         build(1,1,n);126         slove();127     }128     return 0;129 }

 1 //Accepted    6396 KB    2250 ms 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <queue> 6 #include <cmath> 7 #include <algorithm> 8 using namespace std; 9 /**10   * This is a documentation comment block11   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！12   * @authr songt13   */14 int max(int a,int b)15 {16     return a>b?a:b;17 }18 int min(int a,int b)19 {20     return a<b?a:b;21 }22 struct node23 {24     int l,r;25     int tmax;26 }f[200005*4];27 int n,w,h;28 void build(int t,int l,int r)29 {30     f[t].l=l;31     f[t].r=r;32     f[t].tmax=w;33     if (l==r) return ;34     int mid=(l+r)/2;35     build(2*t,l,mid);36     build(2*t+1,mid+1,r);37 }38 int query(int t,int c)39 {40     if (f[t].l==f[t].r && f[t].tmax>=c)41     {42         f[t].tmax=f[t].tmax-c;43         return f[t].l;44     }45     int mid=(f[t].l+f[t].r)/2;46     int res=-1;47     if (f[2*t].tmax>=c)  res=query(2*t,c);48     else49     if (f[2*t+1].tmax>=c)  res=query(2*t+1,c);50     f[t].tmax=max(f[2*t].tmax,f[2*t+1].tmax);51     return res;52 }53 void slove()54 {55     int x;56     for (int i=1;i<=n;i++)57     {58         scanf("%d",&x);59         if (f[1].tmax>=x)60         {61             printf("%d\n",query(1,x));62         }63         else64         {65             printf("-1\n");66         }67     }68 }69 70 int main()71 {72     while (scanf("%d%d%d",&h,&w,&n)!=EOF)73     {74         build(1,1,min(h,n));75         slove();76     }77     return 0;78 }