Submission #1235830

#TimeUsernameProblemLanguageResultExecution timeMemory
1235830antromancapExamination (JOI19_examination)C++20
2 / 100
3090 ms6520 KiB
#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'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...