线段树水题,需要稍微思考一下。
手写线段树感觉好爽!!!线段树好神!!!
#include <cstdio> #include <cstring> #include <cstdlib> #include <ctime> #include <climits> #include <cmath> #include <iostream> #include <string> #include <vector> #include <set> #include <map> #include <list> #include <queue> #include <stack> #include <deque> #include <algorithm> using namespace std; typedef long long ll; #define lhs rt<<1 #define rhs rt<<1|1 const int maxn = 200010; int h, w, n, ans; int x, c[maxn*4]; int query(int x, int rt = 1, int L = 1, int R = h) { if (L == R) { c[rt] -= x; return L; } int M = (L+R) >> 1, ret; if (c[lhs] >= x) ret = query(x, lhs, L, M); else ret = query(x, rhs, M+1, R); c[rt] = max(c[lhs], c[rhs]); return ret; } void init(int rt = 1, int L = 1, int R = h) { c[rt] = w; if (L == R) return; int M = (L+R) >> 1; init(lhs, L, M); init(rhs, M+1, R); } int main() { while (scanf("%d%d%d", &h, &w, &n) == 3) { h = min(h, n); init(); for (int i=0;i<n;i++) { scanf("%d", &x); if (c[1] < x) puts("-1"); else printf("%d\n", query(x)); } } return 0; }