http://acm.hdu.edu.cn/showproblem.php?pid=2795
放在第几行 就是第几行的剩余空值x》xi 以行建树 求区间第K值
View Code
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 #define N 200010 7 #define LL __int64 8 LL s[N<<2],h,ww; 9 void build(int l,int r,int w) 10 { 11 s[w] = ww; 12 if(l==r) 13 return ; 14 int m = (l+r)>>1; 15 build(l,m,w<<1); 16 build(m+1,r,w<<1|1); 17 } 18 void pushup(int w) 19 { 20 s[w] = max(s[w<<1],s[w<<1|1]); 21 } 22 int query(int p,int l,int r,int w) 23 { 24 if(l==r) 25 { 26 s[w]-=p; 27 return l; 28 } 29 int m = (l+r)>>1,re; 30 if(p<=s[w<<1]) 31 re = query(p,l,m,w<<1); 32 else 33 re = query(p,m+1,r,w<<1|1); 34 pushup(w); 35 return re; 36 } 37 int main() 38 { 39 int i,j,k,n,m; 40 LL wi; 41 while(~scanf("%I64d%I64d%d",&h,&ww,&n)) 42 { 43 if(h>n) 44 h = n; 45 build(1,h,1); 46 while(n--) 47 { 48 cin>>wi; 49 if(s[1]<wi) 50 puts("-1"); 51 else 52 printf("%d\n",query(wi,1,h,1)); 53 } 54 } 55 return 0; 56 }