学步园

大意：给定的board的长、宽以及公告的长、宽，问第ith广告在第几行。

思路：把h看做区间，w看做长度即可，维护一个最大值，每次往最左边更新。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

const int maxn = 222222;

int maxv[maxn<<2];
int ql, qr;
int p, v;
int h, w, n;

void pushup(int o)
{
	maxv[o] = max(maxv[o*2], maxv[o*2+1]);
}

void build(int o, int L, int R)
{
	int M = L + (R-L)/2;
	maxv[o] = w;
	if(L == R) ;
	else
	{
		build(o*2, L, M);
		build(o*2+1, M+1, R);
	}
}

/*int query(int o, int L, int R) //合并查询与更新 
{
	int M = L + (R-L)/2, ans;
	if(L == R) {maxv[o] -= v; return L; }
	if(maxv[o*2 >= v]) ans = query(o*2, L, M);
	else ans = query(o*2+1, M+1, R);
	pushup(o);
	return ans;
}*/

int query(int o, int L, int R)
{
	int M = L + (R-L)/2, ans;
	if(L == R) return L;
	if(maxv[2*o] >= v) ans = query(o*2, L, M);
	else ans = query(o*2+1, M+1, R);
	return ans;
}

void update(int o, int L, int R)
{
	int M = L + (R-L)/2;
	if(L == R) maxv[o] -= v;
	else
	{
		if(p <= M) update(o*2, L, M);
		else update(o*2+1, M+1, R);
		pushup(o);
	}
}

void solve()
{
	build(1, 1, h);
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &v);
		if(maxv[1] < v) printf("-1\n");
		else
		{
			p = query(1, 1, h);
			update(1, 1, h);
			printf("%d\n", p);
		}
	}
}

int main()
{
	while(~scanf("%d%d%d", &h, &w, &n))
	{
		if(h > n) h = n;
		solve();
	}
	return 0;
}