Submission #997939

#TimeUsernameProblemLanguageResultExecution timeMemory
997939toan2602Examination (JOI19_examination)C++14
0 / 100
482 ms44556 KiB
#include<bits/stdc++.h> using namespace std; #define int long long int n, d = 0, q, x[100005], y[100005], z[100005], cnt[200005]; bool mark[500005], Q[500005]; set<int> s; struct NODE { int x, y, z, idx; bool operator < (NODE b) { return x < b.x; } } node[500005]; int bit[500005]; void update(int pos, int val) { while(pos <= d) { bit[pos] += val; pos += pos & -pos; } } int get(int pos) { int res = 0; while(pos > 0) { res += bit[pos]; pos -= pos & -pos; } return res; } int range(int l, int r) { return get(r) - get(l-1); } void cdq(int l, int r) { int mid = (l + r) / 2; if(l == r) return; cdq(l, mid); cdq(mid + 1, r); for (int i = mid + 1; i <= r; i++) { if(!Q[node[i].idx]) update(node[i].z, 1); } vector<NODE> v; int p1; p1 = mid+1; for (int i = l; i <= mid; i++) { while(p1 <= r && node[p1].y < node[i].y) { v.push_back(node[p1]); if(!Q[node[p1].idx]) update(node[p1].z, -1); p1++; } v.push_back(node[i]); cnt[node[i].idx] += range(node[i].z, d); } while(p1 <= r) { v.push_back(node[p1]); if(!Q[node[p1].idx]) update(node[p1].z, -1); p1++; } for (int i = l; i <= r; i++) { node[i] = v[i-l]; } return; } map<int, int> mp; signed main() { cin >> n >> q; for (int i = 1; i <= n; i++) { cin >> node[i].x >> node[i].y; node[i].z = node[i].x + node[i].y; s.insert(node[i].x); s.insert(node[i].y); s.insert(node[i].z); node[i].idx = i; } for (int i = 1; i <= q; i++) { cin >> x[i] >> y[i] >> z[i]; s.insert(x[i]); s.insert(y[i]); s.insert(z[i]); } for (int i: s) mp[i] = ++d; for (int i = 1; i <= n; i++) { node[i].x = mp[node[i].x]; node[i].y = mp[node[i].y]; node[i].z = mp[node[i].z]; //cout << node[i].x << ' ' << node[i].y << ' ' << node[i].z << '\n'; } for (int i = 1; i <= q; i++) { x[i] = mp[x[i]]; y[i] = mp[y[i]]; z[i] = mp[z[i]]; node[i+n] = {x[i], y[i], z[i], i + n}; Q[i+n] = true; } sort(node + 1, node + 1 + q + n); cdq(1, n+q); for (int i = 1; i <= q; i++) { cout << cnt[i+n] << '\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...