oj.uz

Submission #832596

# Submission time Handle Problem Language Result Execution time Memory
832596 2023-08-21T12:13:35 Z _martynas Inspections (NOI23_inspections) C++11
55 / 100
 427 ms 28100 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 79 ms 6220 KB Output is correct
14 Correct 77 ms 4676 KB Output is correct
15 Correct 78 ms 4764 KB Output is correct
16 Correct 91 ms 5068 KB Output is correct
17 Correct 80 ms 4752 KB Output is correct
18 Correct 79 ms 4864 KB Output is correct
19 Correct 79 ms 5336 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 78 ms 5320 KB Output is correct
4 Correct 127 ms 7024 KB Output is correct
5 Incorrect 427 ms 28100 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 79 ms 6220 KB Output is correct
14 Correct 77 ms 4676 KB Output is correct
15 Correct 78 ms 4764 KB Output is correct
16 Correct 91 ms 5068 KB Output is correct
17 Correct 80 ms 4752 KB Output is correct
18 Correct 79 ms 4864 KB Output is correct
19 Correct 79 ms 5336 KB Output is correct
20 Correct 90 ms 6220 KB Output is correct
21 Correct 77 ms 6476 KB Output is correct
22 Correct 96 ms 7460 KB Output is correct
23 Correct 78 ms 6688 KB Output is correct
24 Correct 76 ms 6292 KB Output is correct
25 Correct 105 ms 6988 KB Output is correct
26 Correct 73 ms 7552 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 79 ms 6220 KB Output is correct
14 Correct 77 ms 4676 KB Output is correct
15 Correct 78 ms 4764 KB Output is correct
16 Correct 91 ms 5068 KB Output is correct
17 Correct 80 ms 4752 KB Output is correct
18 Correct 79 ms 4864 KB Output is correct
19 Correct 79 ms 5336 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 78 ms 5320 KB Output is correct
23 Correct 127 ms 7024 KB Output is correct
24 Incorrect 427 ms 28100 KB Output isn't correct
25 Halted 0 ms 0 KB -