Submission #1038451

#TimeUsernameProblemLanguageResultExecution timeMemory
1038451Jarif_RahmanExamination (JOI19_examination)C++17
100 / 100
301 ms20164 KiB
#include <bits/stdc++.h> #define pb push_back #define f first #define sc second using namespace std; typedef long long int ll; typedef string str; const int inf = 1e9; struct BIT{ int n; vector<int> sm; BIT(int _n){ n = _n; sm.resize(n); } void add(int in, int x){ in++; while(in <= n) sm[in-1]+=x, in+=in&-in; } int sum(int in){ in++; int s = 0; while(in >= 1) s+=sm[in-1], in-=in&-in; return s; } int sum(int l, int r){ return sum(r)-(l == 0? 0:sum(l-1)); } }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; vector<tuple<int, int, int, int>> S; for(int i = 0; i < n; i++){ int s, t; cin >> s >> t; S.push_back({s, t, s+t, inf}); } for(int i = 0; i < q; i++){ int a, b, c; cin >> a >> b >> c; S.push_back({a, b, c, i}); } sort(S.begin(), S.end()); int m = S.size(); { vector<int> srt; for(auto [_0, _1, x, _2]: S) srt.push_back(x); sort(srt.begin(), srt.end()); map<int, int> mp; for(int i = 0; i < m; i++) mp[srt[i]] = i; for(auto &[_0, _1, x, _2]: S) x = mp[x]; } BIT bit(m); vector<int> ans(q, 0); function<void(int, int)> cdq = [&](int l, int r){ if(l == r) return; int md = (l+r)/2; cdq(l, md); cdq(md+1, r); vector<tuple<int, int, int>> cur; for(int i = l; i <= md; i++){ auto [a, b, c, in] = S[i]; if(in < inf) cur.push_back({b, in, c}); } for(int i = md+1; i <= r; i++){ auto [a, b, c, in] = S[i]; if(in == inf) cur.push_back({b, in, c}); } sort(cur.rbegin(), cur.rend()); for(auto [b, in, c]: cur){ if(in == inf) bit.add(c, 1); else ans[in]+=bit.sum(c, m-1); } for(auto [b, in, c]: cur){ if(in == inf) bit.add(c, -1); } }; cdq(0, m-1); for(int x: ans) cout << x << "\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...