Time Limit: 20000/8000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
链接:http://acm.hdu.edu.cn/showproblem.php?pid=2795
#include <bits/stdc++.h> using namespace std; int h,w,n; const int maxn = 1000005; struct Node { int v; Node *ls, *rs; void up(){ v = min(ls->v, rs->v); } }pool[maxn<<2], *tail = pool, *root, *zero; void init(){ zero = ++tail; zero->v=0; zero->ls = zero->rs = zero; //root = zero; } Node *build(int l = 1, int r = h){ Node *nd = ++tail; nd-> v = 0; if(l == r)nd-> v = 0,nd->ls=nd->rs=zero; else { int m = (l + r) >> 1; nd->ls = build(l, m); nd->rs = build(m+1, r); nd->up(); //printf("%d %d %d %d %d\n",l,r,nd->ls->v,nd->rs->v,nd->v); } return nd; } #define Ls l, m, nd->ls #define Rs m+1, r, nd->rs int modify(int del, int l = 1, int r = h, Node * nd = root){ if(l == r){ nd->v += del; return l; } int m = (l + r) >> 1; int ans = -1; if(nd->ls->v + del <= w) ans = modify(del, Ls); else if(nd->rs->v + del <= w) ans = modify(del, Rs); nd->up(); return ans; } int main() { while(scanf("%d%d%d",&h,&w,&n)==3){ if(h > n)h=n; tail = pool; init(); root = build(); for(int i = 1; i <= n; i++){ int ww; scanf("%d",&ww); if(ww+root->v>w)printf("-1\n");//lastmx else printf("%d\n",modify(ww)); } } return 0; }
原文:https://www.cnblogs.com/EdSheeran/p/8873616.html