Submission #1235723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235723		antromancap	Examination (JOI19_examination)	C++20	2 / 100	3094 ms	2972 KiB

examination

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5, M = 1000;
int n, Q, b[N], 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;
	bool operator<(const Query &u) const { return z < u.z; }
} 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;
	}
}
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 = 2000, Q = 2000;
	for (int i = 1; i <= n; i++) a[i].first = Rand(1, 1e6), a[i].second = Rand(1, 1e6);
	for (int i = 1; i <= n; i++) q[i].id = i, q[i].x = Rand(1, 1e6), q[i].y = Rand(1, 1e6), q[i].z = Rand(1, 2e6);
	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++) b[j] = a[j].second;
	}
	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; });
	sort(q + 1, q + Q + 1);
	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, j = 1; i <= Q; i++) {
			while (j <= n && a[id[j]].first + a[id[j]].second < q[i].z) {
				if (block[id[j]] == bl) {
					for (int k = id[j]; k >= st[bl]; k--) cnt[k]--;
				}
				j++;
			}
			if (q[i].x < mn[bl]) {
				int p = lower_bound(b + st[bl], b + ed[bl] + 1, q[i].y) - b;
				ans[q[i].id] += cnt[p];
			} else if (q[i].x <= mx[bl]) {
				for (int k = st[bl]; k <= ed[bl]; k++)
					ans[q[i].id] += a[k].first >= q[i].x && a[k].second >= q[i].y && a[k].first + a[k].second >= q[i].z;
			}
		}
	}

	// 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