Submission #914150

#TimeUsernameProblemLanguageResultExecution timeMemory
914150esomerInspections (NOI23_inspections)C++17
100 / 100
700 ms44496 KiB
#include<bits/stdc++.h> using namespace std; #define int long long vector<pair<int, int>> queries; vector<long long> prefix; vector<long long> substract; vector<pair<int, int>> safety; long long totalSum = 0; long long sum(int l, int r){ if(l > r) return 0; if(l > 0) return prefix[r] - prefix[l-1]; else return prefix[r]; } long long getDist(int i, int j, int ind){ assert(i <= j); long long mid = sum(i+1, j-1); return mid + queries[i].second - ind + ind - queries[j].first; } void add(long long dist, int val){ int lo = 0; int hi = (int)safety.size() - 1; int bst = (int)safety.size(); while(lo <= hi){ int mid = (lo + hi) / 2; if(safety[mid].first > dist){ bst = mid; hi = mid - 1; }else lo = mid + 1; } // cout << "add: dist " << dist << " val "<< val << " bst "<< bst << "\n"; totalSum += val; substract[bst] += val; } void solve(){ int n, m, q; cin >> n >> m >> q; vector<vector<int>> start(n), ends(n+1); queries.resize(m); prefix.resize(m); for(int i = 0; i < m; i++){ int l, r; cin >> l >> r; l--; r--; start[l].push_back(i); ends[r+1].push_back(i); if(i == 0) prefix[i] = r - l + 1; else prefix[i] = prefix[i-1] + r - l + 1; queries[i] = {l, r}; } safety.resize(q); substract.assign(q+1, 0); for(int i = 0; i < q; i++){ int s; cin >> s; safety[i] = {s, i}; } sort(safety.begin(), safety.end()); set<pair<int, long long>> s; for(int i = 0; i < n; i++){ for(int x : ends[i]){ auto it = s.lower_bound({x, -1}); pair<int, long long> p = *it; add(p.second, -(n-i)); int prev = -1, nxt = -1; if(it != s.begin()){ it--; prev = (*it).first; } s.erase(p); it = s.lower_bound({x, -1}); if(it != s.end()){ nxt = (*it).first; } if(nxt != -1){ it = s.lower_bound({nxt, -1}); add((*it).second, -(n-i)); s.erase(it); if(prev == -1){ s.insert({nxt, -1}); add(-1, n-i); }else{ long long dist = getDist(prev, nxt, i); s.insert({nxt, dist}); add(dist, n-i); } } } for(int x : start[i]){ if(s.empty()){ s.insert({x, -1}); add(-1, n-i); continue; } auto it = s.lower_bound({x, -1}); if(it == s.end()){ it--; long long dist = getDist((*it).first, x, i); add(dist, n-i); s.insert({x, dist}); }else if(it == s.begin()){ int y = (*it).first; long long dist = getDist(x, y, i); add(dist, n-i); s.erase(it); s.insert({y, dist}); s.insert({x, -1}); add(-1, n-i); }else{ pair<int, long long> tp = (*it); it--; pair<int, long long> btm = (*it); s.erase(tp); add(tp.second, -(n-i)); long long distTpMe = getDist(x, tp.first, i); long long distMeBtm = getDist(btm.first, x, i); add(distTpMe, n-i); add(distMeBtm, n-i); s.insert({x, distMeBtm}); s.insert({tp.first, distTpMe}); } } // cout << "remove"<< endl; } vector<long long> ans(q); for(int i = 0; i < q; i++){ totalSum -= substract[i]; ans[safety[i].second] = totalSum; } for(long long& x : ans) cout << x << " "; cout << "\n"; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); // int tt; cin >> tt; int tt = 1; while(tt--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...