Submission #1200490

#TimeUsernameProblemLanguageResultExecution timeMemory
1200490ofozInspections (NOI23_inspections)C++20
0 / 100
2094 ms37896 KiB
#include <bits/stdc++.h> #define int long long using namespace std; #define pi pair<int, int> #define ppi pair<pair<int, int>, int> #define vi vector<int> void solve() { int n, m, q; cin >> n >> m >> q; int s = 0; vector<ppi> pairs; for (int i = 0; i < m; i++) { int l, r; cin >> l >> r; pairs.push_back({{l, r}, s}); s += (r-l+1); } vector<pi> queries(q); int x; for (int i = 0; i < q; i++) { cin >> x; queries[i] = {x, i}; } sort(pairs.rbegin(), pairs.rend()); map<int, int> mx; multiset<int> cur; multiset<pi> end; int start = 0; int left = 0; for (int i = 1; i <= n; i++) { bool event = (!pairs.empty() && pairs.back().first.first <= i) || (!end.empty() && end.begin()->first < i); if (event && left) { for (auto it = next(cur.begin(), 1); it != cur.end(); it++) { int diff = *it - *prev(it, 1); start += left; mx[diff] += left; } left = 0; } while (!pairs.empty() && pairs.back().first.first <= i) { cur.insert(pairs.back().second - i + 1); end.insert({pairs.back().first.second, pairs.back().second - i + 1}); pairs.pop_back(); event = 1; } while (!end.empty() && end.begin()->first < i) { cur.erase(cur.lower_bound(end.begin()->second)); end.erase(end.begin()); event = 1; } if (cur.size() < 2) { continue; } left++; } if (left) {} vector<int> res(q); sort(queries.begin(), queries.end()); int j = 0; int c = start; for (pi p : mx) { while (j < q && queries[j].first < p.first) { res[queries[j].second] = c; j++; continue; } c -= p.second; if (j >= q) break; if (p.first > queries[j].first) continue; res[queries[j].second] = c; } for (int x : res) cout << x << ' '; } /* iterate through each machine i. how do we process the events? for each l, we insert the number of days s into the set for each r, we erase the number of days */ signed main() { solve(); 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...