题解：P11833 [省选联考 2025] 推箱子

// Problem: F - Takahashi in Narrow Road
// Contest: AtCoder - AtCoder Beginner Contest 371
// URL: https://atcoder.jp/contests/abc371/tasks/abc371_f
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define int ll

const int N = 1e6 + 10, INF = 1e14;

int n, a[N];

struct Node {
	int l, r, v, tag;
}tr[N << 2];

int sum(int x, int y) {
	return (x + x + y - 1) * y / 2;
}

void pushup(int u) {
	tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v;
}

void calc(int u, int d) {
	tr[u].tag = d;
	tr[u].v = sum(d, tr[u].r - tr[u].l + 1);
}

void pushdown(int u) {
	if (tr[u].tag != -INF) {
		calc(u << 1, tr[u].tag);
		calc(u << 1 | 1, tr[u].tag + tr[u << 1].r - tr[u << 1].l + 1);
		tr[u].tag = -INF;
	}
}

void build(int u, int l, int r) {
	tr[u].l = l, tr[u].r = r, tr[u].v = a[l], tr[u].tag = -INF;
	if (l != r) {
		int mid = l + r >> 1;
		build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
		pushup(u);
	}
}

void modify(int u, int l, int r, int d) {
	if (tr[u].l >= l && tr[u].r <= r) calc(u, d + tr[u].l - l);
	else {
		int mid = tr[u].l + tr[u].r >> 1;
		pushdown(u);
		if (l <= mid) modify(u << 1, l, r, d);
		if (r > mid) modify(u << 1 | 1, l, r, d);
		pushup(u);
	}
}

int query(int u, int l, int r) {
	if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;
	int mid = tr[u].l + tr[u].r >> 1, res = 0;
	pushdown(u);
	if (l <= mid) res = query(u << 1, l, r);
	if (r > mid) res += query(u << 1 | 1, l, r);
	return res;
}

struct Box {
	int a, b, c;
}box[N];

int p[N];

bool solve() {
	cin >> n;
	
	for (int i = 1; i <= n; ++ i ) {
		cin >> box[i].a >> box[i].b >> box[i].c;
	}
	
	iota(p + 1, p + n + 1, 1);
	
	sort(p + 1, p + n + 1,
		[&](int x, int y) {
			return box[x].c < box[y].c;
		});
	
	for (int i = 1; i <= n; ++ i ) a[i] = box[[p[i]]].a;
	build(1, 1, n);
	
	int q, ans = 0;
	
	for (int i = 1; i <= n; ++ i ) {
		int t = p[i], g = box[p[i]].b;
		
		if (query(1, t, t) == g) continue;
		if (query(1, t, t) < g) {
			int lo = t, hi = n, res = -1;
			
			while (lo <= hi) {
				int mid = lo + hi >> 1;
				if (query(1, mid, mid) - g + 1 < mid - t + 1) {
					res = mid;
					lo = mid + 1;
				} else {
					hi = mid - 1;
				}
			}
			// cout << res << '\n';
			
			ans += sum(g, res - t + 1) - query(1, t, res);
			// cout << g << ' ' << res - t + 1 << ' ' << query(1, t, res) << '\n';
			modify(1, t, res, g);
		} else {
			int lo = 1, hi = t, res = -1;
			
			while (lo <= hi) {
				int mid = lo + hi >> 1;
				if (g - query(1, mid, mid) + 1 < t - mid + 1) {
					res = mid;
					hi = mid - 1;
				} else {
					lo = mid + 1;
				}
			}
			// cout << res << '\n';
			
			ans += query(1, res, t) - sum(g - (t - res + 1) + 1, t - res + 1);
			// cout << g - (t - res + 1) + 1 << ' ' << t - res + 1 << ' ' << query(1, res, t) << '\n';
			modify(1, res, t, g - (t - res + 1) + 1);
		}
	
	// cout << i << ' ' << box[i].a << ' ' << box[i].b << ' ' << box[i].c << '\n';
		if (ans > box[p[i]].c) return false;
	}
	
	return true;
}

signed main() {
	int c, T;
	cin >> c >> T;
	while (T -- ) cout << (solve() ? "Yes\n" : "No\n");
	return 0;
}