Submission #832596

#	Time	Username	Problem	Language	Result	Execution time	Memory
832596		_martynas	Inspections (NOI23_inspections)	C++11	55 / 100	427 ms	28100 KiB

Main

#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+1-right_cut}};
    }
    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;
}

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 0 / 22
• Subtask 4: 26 / 26
• Subtask 5: 0 / 23