This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <array>
#include <cassert>
using namespace std;
using ll = long long;
const int mxn = 2e5+5;
int n, m, q;
int l[mxn], r[mxn];
ll s[mxn], ans[mxn];
struct Interval {
int l, r;
long long t;
bool operator<(const Interval& other) const {
return r < other.r;
}
array<Interval, 2> cut(int m, bool right_cut) {
return {Interval{l, m-right_cut, t}, Interval{m+1-right_cut, r, t+m-l}};
}
pair<ll, ll> eat(Interval top) {
assert(top.l <= l && r <= top.r);
pair<ll, ll> info; info.second = r-l+1;
info.first = (l-top.l)+(top.t-t);
return info;
}
};
int main(int argc, char const *argv[]) {
cin >> n >> m >> q;
for(int i = 1; i <= m; i++) {
cin >> l[i] >> r[i];
}
for(int i = 1; i <= q; i++) {
cin >> s[i];
}
// using intervals find largest s such that all s* s.t. s*<=s increase
map<ll, ll> inc;
set<Interval> ints;
long long t = 0;
for(int i = 1; i <= m; i++) {
Interval curr{l[i], r[i], t};
// printf("%d: [%d; %d] at %d\n", i, l[i], r[i], t);
auto it = ints.lower_bound(Interval{-1000, l[i]});
while(it != ints.end() && it->l <= r[i]) {
Interval last = *it;
ints.erase(it);
// printf("\t[%d; %d] (%d)\n", last.l, last.r, last.t);
if(curr.l <= last.l && last.r <= curr.r) {
auto leftovers = last.eat(curr);
// printf("[%d; %d] (%d) ate [%d; %d] (%d)\n", curr.l, curr.r, curr.t, last.l, last.r, last.t);
// printf("leftovers: %d %d\n", leftovers.first, leftovers.second);
inc[leftovers.first-1] += leftovers.second;
}
else {
auto parts = last.cut((last.r > curr.r ? curr.r : curr.l), !(last.r > curr.r));
ints.insert(parts[0]);
ints.insert(parts[1]);
// printf("split into:\n");
// printf("[%d; %d] (%d)\n", parts[0].l, parts[0].r, parts[0].t);
// printf("[%d; %d] (%d)\n", parts[1].l, parts[1].r, parts[1].t);
}
// find it again
it = ints.lower_bound(Interval{-1000, l[i]});
}
ints.insert(curr);
t += r[i]-l[i]+1;
}
// accumulate answers
vector<int> dec_s(q); iota(dec_s.begin(), dec_s.end(), 1);
sort(dec_s.begin(), dec_s.end(), [&](int i, int j) { return s[i] > s[j];});
int sum = 0;
auto it = inc.rbegin();
for(int i = 0; i < q; i++) {
int j = dec_s[i];
while(it != inc.rend() && it->first >= s[j]) {
sum += it->second;
it++;
}
ans[j] = sum;
}
for(int i = 1; i <= q; i++) cout << ans[i] << " ";
cout << "\n";
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... |