Submission #1235830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235830		antromancap	Examination (JOI19_examination)	C++20	2 / 100	3090 ms	6520 KiB

examination

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5, M = 330;
int n, Q, ans[N], block[N], cnt[N], st[M], ed[M], id[N], mn[M], mx[M];
pair<int, int> a[N];

struct Query {
	int x, y, z, id;
} q[N];

namespace checker {
int f[N];
void process() {
	for (int i = 1; i <= Q; i++) {
		for (int j = 1; j <= n; j++) f[i] += a[j].first >= q[i].x && a[j].second >= q[i].y && a[j].first + a[j].second >= q[i].z;
		// cout << f[i] << '\n';
	}
}
bool ok() {
	for (int i = 1; i <= Q; i++)
		if (f[i] != ans[i]) return cerr << i << ' ' << f[i] << ' ' << ans[i] << '\n', 0;
	return 1;
}
} // namespace checker
random_device rd;
mt19937_64 gen(rd());

long long Rand(long long l, long long r) { return gen() % (r - l + 1) + l; }
void Test() {
	n = 100000, Q = 100000;
	int LIM = 1000000;
	for (int i = 1; i <= n; i++) a[i].first = Rand(1, LIM), a[i].second = Rand(1, LIM);
	for (int i = 1; i <= Q; i++) q[i].id = i, q[i].x = Rand(1, LIM), q[i].y = Rand(1, LIM), q[i].z = Rand(1, 2 * LIM);
	// cout << n << ' ' << Q << '\n';
	// for (int i = 1; i <= n; i++) cout << a[i].first << ' ' << a[i].second << '\n';
	// for (int i = 1; i <= Q; i++) cout << q[i].x << ' ' << q[i].y << ' ' << q[i].z << '\n';
}
void Input() {
	cin >> n >> Q;
	for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
	for (int i = 1; i <= Q; i++) cin >> q[i].x >> q[i].y >> q[i].z, q[i].id = i;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	Input();
	// Test();
	// checker::process();
	for (int i = 1; i <= n; i++) block[i] = (i + M - 1) / M;
	for (int i = 1; i <= block[n]; i++) st[i] = ed[i - 1] + 1, ed[i] = ed[i - 1] + M;
	ed[block[n]] = n;
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= block[n]; i++) {
		mn[i] = a[st[i]].first;
		mx[i] = a[ed[i]].first;
		sort(a + st[i], a + ed[i] + 1, [&](pair<int, int> x, pair<int, int> y) { return x.second < y.second; });
		for (int j = st[i]; j <= ed[i]; j++) cerr << a[j].first << ' ' << a[j].second << '\n';
	}
	for (int i = 1; i <= n; i++) id[i] = i;
	sort(id + 1, id + n + 1, [&](int x, int y) { return a[x].first + a[x].second < a[y].first + a[y].second; });
	for (int bl = 1; bl <= block[n]; bl++)
		for (int i = st[bl]; i <= ed[bl]; i++) cnt[i] = ed[bl] - i + 1;
	for (int i = 1; i <= Q; i++)
		for (int bl = 1; bl <= block[n]; bl++)
			if (mn[bl] <= q[i].x && q[i].x <= mx[bl]) {
				for (int j = st[bl]; j <= ed[bl]; j++) ans[i] += a[j].first >= q[i].x && a[j].second >= q[i].y && a[j].first + a[j].second >= q[i].z;
			}

	for (int i = 1; i <= Q; i++) block[i] = (i + M - 1) / M;
	for (int i = 1; i <= block[Q]; i++) st[i] = ed[i - 1] + 1, ed[i] = ed[i - 1] + M;
	ed[block[Q]] = Q;
	sort(q + 1, q + Q + 1, [&](Query x, Query y) { return x.z < y.z; });
	for (int i = 1; i <= block[Q]; i++) sort(q + st[i], q + ed[i] + 1, [&](Query x, Query y) { return x.y < y.y; });

	for (int bl = 1, j = 1; bl <= block[Q]; bl++) {
		int t = 0;
		for (int i = st[bl]; i <= ed[bl]; i++) t = max(t, q[i].z);
		while (j <= n && a[id[j]].first + a[id[j]].second < t) {
			for (int k = id[j], l = st[block[k]]; k >= l; k--) cnt[k]--;
			for (int k = st[bl]; k <= ed[bl]; k++) {
				ans[q[k].id] += mn[block[id[j]]] > q[k].x && a[id[j]].second >= q[k].y && a[id[j]].first + a[id[j]].second >= q[k].z;
			}
			j++;
		}
		for (int x = 1; x <= block[n]; x++) {
			for (int y = st[bl], k = st[x]; y <= ed[bl]; y++) {
				while (k <= min(n, x * M) && a[k].second < q[y].y) k++;
				if (k <= min(n, x * M) && mn[x] > q[y].x) ans[q[y].id] += cnt[k];
			}
		}
	}
	// cout << (checker::ok() ? "ok" : "nah");
	for (int i = 1; i <= Q; i++) cout << ans[i] << '\n';
}

• Subtask 1: 2 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57