#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++) {
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();
}
while (!end.empty() && end.begin()->first < i) {
cur.erase(cur.lower_bound(end.begin()->second));
end.erase(end.begin());
}
if (cur.size() < 2) { continue; }
left++;
bool event = (!pairs.empty() && pairs.back().first.first <= i+1) || (!end.empty() && end.begin()->first < i+1);
if (event) {
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;
}
}
}
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |