Submission #1097976

#TimeUsernameProblemLanguageResultExecution timeMemory
1097976VMaksimoski008Inspections (NOI23_inspections)C++17
77 / 100
2081 ms13904 KiB
#include <bits/stdc++.h> #define ar array #define int long long using namespace std; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; const int mod = 1e9 + 7; const int LOG = 20; const int maxn = 1e5 + 5; vector<pll> qus; int bin_search(ll p) { int l=0, r=qus.size()-1, ans=-1; while(l <= r) { int mid = (l + r) / 2; if(qus[mid].first <= p) ans = mid, l = mid + 1; else r = mid - 1; } return ans; } signed main() { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); int n, m, q; cin >> n >> m >> q; ll day = 1; vector<int> L(m), R(m); for(int i=0; i<m; i++) cin >> L[i] >> R[i]; for(int i=0; i<q; i++) { ll x; cin >> x; qus.push_back({ x, i }); } sort(qus.begin(), qus.end()); vector<ll> ans(q); set<array<ll, 3> > s; for(int i=0; i<m; i++) { vector<array<ll, 3> > to_rem, to_add; // cout << i << ": " << '\n'; // for(auto &[l, r, x] : s) cout << l << " " << r << " " << x << '\n'; // cout << '\n'; //brute force prvo for(auto &[l, r, x] : s) { if(L[i] <= l && r <= R[i]) { int p = bin_search(day + l - L[i] - x - 1); if(p > -1) ans[p] += r - l + 1; to_rem.push_back({ l, r, x }); } else if(l < L[i] && R[i] < r) { int p = bin_search(day - (x + L[i] - l) - 1); if(p > -1) ans[p] += R[i] - L[i] + 1; to_rem.push_back({ l, r, x }); to_add.push_back({ l, L[i]-1, x }); to_add.push_back({ R[i]+1, r, R[i] + 1 - l + x}); } else if(l < L[i] && L[i] <= r && r <= R[i]) { int p = bin_search(day - (x + L[i] - l) - 1); if(p > -1) ans[p] += r - L[i] + 1; to_rem.push_back({ l, r, x }); to_add.push_back({ l, L[i]-1, x }); } else if(L[i] <= l && l <= R[i] && R[i] < r) { int p = bin_search(day + l - L[i] - x - 1); if(p > -1) ans[p] += R[i] - l + 1; to_rem.push_back({ l, r, x }); to_add.push_back({ R[i]+1, r, R[i] + 1 - l + x }); } } to_add.push_back({ L[i], R[i], day }); // cout << "REM" << '\n'; // for(auto &[l, r, x] : to_rem) cout << l << " " << r << " " << x << '\n'; // cout << '\n'; // cout << "ADD\n"; // for(auto &[l, r, x] : to_add) cout << l << " " << r << " " << x << '\n'; // cout << '\n'; for(auto &x : to_rem) s.erase(x); for(auto &x : to_add) s.insert(x); day += R[i] - L[i] + 1; } for(int i=q-2; i>=0; i--) ans[i] += ans[i+1]; for(int i=0; i<q; i++) qus[i].first = ans[i]; sort(qus.begin(), qus.end(), [&](pll a, pll b) { return a.second < b.second; }); for(auto x : qus) cout << x.first << " "; 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...
#Verdict Execution timeMemoryGrader output
Fetching results...