Time Limit: 20000/8000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 16755 Accepted Submission(s): 7089
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; #define mem(x,y) memset(x,y,sizeof(x)) #define SI(x) scanf("%d",&x) #define SL(x) scanf("%lld",&x) #define PI(x) printf("%d",x) #define P_ printf("") #define PL(x) printf("%lld",x) typedef long long LL; const int INF=0x3f3f3f3f; #define ll root<<1 #define rr root<<1|1 #define lson ll,l,mid #define rson rr,mid+1,r const int MAXN=200100; int tree[MAXN<<2]; #define V(x) tree[x] int w; int ans; void pushup(int root){ V(root)=max(V(ll),V(rr)); } void build(int root,int l,int r){ V(root)=w; if(l==r)return; int mid=(l+r)>>1; build(lson); build(rson); } void query(int root,int l,int r,int v){ if(l==r){ V(root)-=v; ans=l;return; } int mid=(l+r)>>1; if(V(ll)>=v)query(lson,v); else query(rson,v); pushup(root); } int main(){ int h,n; while(~scanf("%d%d%d",&h,&w,&n)){ if(h>n)h=n; build(1,1,h); while(n--){ int x; SI(x); ans=INF; if(x>V(1)){ puts("-1");continue; } query(1,1,h,x); printf("%d\n",ans); } } return 0; }
原文:http://www.cnblogs.com/handsomecui/p/5125504.html