Submission #1235563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235563		antromancap	Examination (JOI19_examination)	C++20	0 / 100	3097 ms	4164 KiB

examination

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 1, M = 1000;
int n, Q, b[N], ans[N], block[M], 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];

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

	cin >> n >> Q;
	for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
	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;
		for (int j = st[i]; j <= ed[i]; j++) b[j] = a[j].second;
		sort(b + st[i], b + ed[i] + 1);
	}
	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 i = 1; i <= Q; i++) cin >> q[i].x >> q[i].y >> q[i].z, q[i].id = i;
	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;
			}
		}
	}

	for (int i = 1; i <= Q; i++) cout << ans[i] << '\n';
}

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