Submission #1215145

#TimeUsernameProblemLanguageResultExecution timeMemory
1215145vaneaExamination (JOI19_examination)C++20
22 / 100
3093 ms7612 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int mxN = 1e5+10; const int block = pow(100000, .5); int cnt[mxN], active = 0; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; vector<array<int, 2>> v(n); for(int i = 0; i < n; i++) { cin >> v[i][0] >> v[i][1]; } vector<vector<int>> ord(3, vector<int>(n)); for(int i = 0; i < 3; i++) iota(ord[i].begin(), ord[i].end(), 0); for(int i = 0; i < 2; i++) { sort(ord[i].begin(), ord[i].end(), [&](int a, int b) { return v[a][i] < v[b][i]; }); } sort(ord[2].begin(), ord[2].end(), [&](int a, int b) { return v[a][0] + v[a][1] < v[b][1] + v[b][0]; }); vector<vector<int>> vals(3, vector<int>(n)); for(int i = 0; i < 2; i++) { for(int j = 0; j < n; j++) { vals[i][j] = v[ord[i][j]][i]; } } for(int j = 0; j < n; j++) { vals[2][j] = v[ord[2][j]][0] + v[ord[2][j]][1]; } vector<array<int, 3>> qs(q), s(q); vector<int> qi(q); iota(qi.begin(), qi.end(), 0); for(int i = 0; i < q; i++) { for(int j = 0; j < 3; j++) { cin >> qs[i][j]; qs[i][j] = lower_bound(vals[j].begin(), vals[j].end(), qs[i][j]) - vals[j].begin(); } int x = 0; for(int j = 0; j < 3; j++) { s[i][j] = qs[i][j]/block; if(x) s[i][j] = n - s[i][j]; x ^= s[i][j] & 1; } } sort(qi.begin(), qi.end(), [&](int a, int b) { return s[a] < s[b]; }); array<int, 3> curr = {n, n, n}; vector<int> ans(q); for(auto id : qi) { for(int j = 0; j < 3; j++) { while(curr[j] > qs[id][j]) { curr[j]--; cnt[ord[j][curr[j]]]++; if(cnt[ord[j][curr[j]]] == 3) ++active; } while(curr[j] < qs[id][j]) { cnt[ord[j][curr[j]]]--; if(cnt[ord[j][curr[j]]] == 2) active--; curr[j]++; } } ans[id] = active; } for(auto it : ans) { cout << it << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...