Submission #810846

#TimeUsernameProblemLanguageResultExecution timeMemory
810846OrazBExamination (JOI19_examination)C++14
0 / 100
3067 ms189608 KiB
#include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; using namespace std; #define pii pair <int, int> // #define ordered_set tree<pair<pii,int>, null_type,less<pair<pii,int>>, rb_tree_tag,tree_order_statistics_node_update> #define all(x) (x).begin(), (x).end() #define ll long long int #define pb push_back #define ff first #define ss second const int N = 1e6; int M = 0; int n, q; map<int,int> now1, now2, now3; map<pii,int> num; int pos[N], s[N], t[N], ans[N]; int x[N], y[N], z[N], ind[N]; int f[N][2]; void upd(int x, int y, int l = 1, int r = M, int idx = 1){ if (l == r){ num[{x, idx}]++; return; } int md = (l+r)>>1; if (md <= y) upd(x, y, l, md, idx<<1); else upd(x, y, md+1, r, idx<<1|1); num[{x, idx}] = num[{x, idx<<1}]+num[{x, idx<<1|1}]; } int get(int x, int y, int l = 1, int r = M, int idx = 1){ if (l > y) return 0; if (r <= y) return num[{x, idx}]; int md = (l+r)>>1; return get(x, y, l, md, idx<<1)+get(x, y, md+1, r, idx<<1|1); } void add(int x, int y){ for (int i = x; i <= M; i += i&(-i)){ f[i][0]++; upd(i, y); } for (int i = y; i <= M; i += i&(-i)){ f[i][1]++; } } int count(int x, int y){ int cnt = 0; for (int i = x; i > 0; i -= i&(-i)){ cnt += f[i][0]; // cnt -= get(i, y); } // if (x == 5 and y == 4) cout << "APA" << '\n'; for (int i = y; i > 0; i -= i&(-i)){ cnt += f[i][1]; } return cnt; } int main () { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> q; set<int> dec1, dec2, dec3; for (int i = 1; i <= n; i++){ cin >> s[i] >> t[i]; dec1.insert(s[i]); dec2.insert(t[i]); dec3.insert(s[i]+t[i]); pos[i] = i; } for (int i = 1; i <= q; i++){ cin >> x[i] >> y[i] >> z[i]; dec1.insert(x[i]); dec2.insert(y[i]); dec3.insert(z[i]); } int T = 0; for (auto i : dec1){ now1[i] = ++T; } M = T; T = 0; for (auto i : dec2){ now2[i] = ++T; } M = max(M, T); T = 0; for (auto i : dec3){ now3[i] = ++T; } sort(pos+1,pos+n+1, [&](int x, int y){ return (now3[s[x]+t[x]]) > (now3[s[y]+t[y]]); }); // add(4, 5); // add(3, 7); // add(1, 1); // add(2, 2); // cout << count(5, 8); // cout << now3[115] << '\n'; for (int i = 1; i <= q; i++){ x[i] = now1[x[i]]; y[i] = now2[y[i]]; z[i] = now3[z[i]]; ind[i] = i; } sort(ind+1,ind+q+1, [&](int x, int y){ return z[x] > z[y]; }); // cout << now1[60] << " " << now2[60] << '\n'; int l = 0; for (int i = 1; i <= q; i++){ while(l < n and now3[s[pos[l+1]]+t[pos[l+1]]] >= z[ind[i]]){ l++; add(now1[s[pos[l]]], now2[t[pos[l]]]); } // cout << l << " " << count(x[ind[i]]-1, y[ind[i]]-1) << ' '; // cout << x[ind[i]]-1 << " " << y[ind[i]]-1 << '\n'; ans[ind[i]] = l-count(x[ind[i]]-1, y[ind[i]]-1); } 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...