主席树极品马蜂 WA60 求调

# include<bits/stdc++.h>
# define ll long long
# define INF 1000000000000000000
using namespace std;

struct JUS {
	ll w, v, s;
} jus[100005];

ll n, m, rot[100005];
 
class {
	public : 
		ll pot;
		struct Point {
			ll L, R, lc, rc, siz, sum;
		} po[2200005];
		void build (ll &p, ll x = 1, ll y = 100000) {
			p = ++ pot;
			po[p] = {x, y, 0, 0, 0, 0};
			if (x == y) return;
			ll mid = (x + y) >> 1;
			build (po[p].lc, x ,mid);
			build (po[p].rc, mid + 1, y);
		}
		void insert (ll q, ll &p, ll pos, ll k) {
			p = ++ pot; po[p] = po[q]; 
			po[p].siz += k;
			if (po[p].L == po[p].R) {
				po[p].sum += po[p].L * k;
				return;
			}
			ll mid = (po[p].L + po[p].R) >> 1;
			if (pos <= mid) insert (po[q].lc, po[p].lc, pos, k);
			else insert (po[q].rc, po[p].rc, pos, k);
			po[p].sum = po[po[p].lc].sum + po[po[p].rc].sum;
		}
		ll query (ll p, ll k) {
			if (k == 0) return 0;
			if (po[p].L == po[p].R) {
				if (k <= po[p].siz) return k * po[p].L;
				else return INF; 
			}
			ll g = po[po[p].lc].siz;
			if (k <= g) return query (po[p].lc, k);
			else return po[po[p].lc].sum + query (po[p].rc, k - g);
		}
} flk;

signed main () {
//	freopen ("code.in", "r", stdin);
//	freopen ("code.out", "w", stdout);
	ios::sync_with_stdio (0);
	cin.tie (0), cout.tie (0);
	
	cin >> n >> m;
	for (ll i = 1; i <= n; i ++) {
		cin >> jus[i].w >> jus[i].v >> jus[i].s;
	}
	
	sort (jus + 1, jus + 1 + n, [&](JUS x, JUS y) {
		return x.w > y.w;
	});	
	
	flk.build (rot[0]);
	for (ll i = 1; i <= n; i ++) 
		flk.insert (rot[i - 1], rot[i], jus[i].v, jus[i].s);
	
	while (m --) {
		ll x, y; cin >> x >> y;
		ll L = 1, R = n, res = n + 1;
		while (L <= R) {
			ll mid = (L + R) >> 1;
			if (flk.query (rot[mid], y) <= x) res = mid, R = mid - 1;
			else L = mid + 1;
		}
		cout << (res == n + 1 ? -1 : jus[res].w) << endl;
	}
	
	return 0;
}