oj.uz

Submission #568074

# Submission time Handle Problem Language Result Execution time Memory
568074 2022-05-24T15:41:16 Z Cyanmond New Home (APIO18_new_home) C++17
12 / 100
 5000 ms 302848 KB 
#include <bits/stdc++.h>

using namespace std;
using i64 = int64_t;

constexpr int inf = 1000000100;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)
#define RVP(i, n) for (int i = (n - 1); i >= 0; --i)

#define ALL(x) (x).begin(), (x).end()

struct PriqueErase {
    priority_queue<int, vector<int>, greater<int>> a, b;

    void push(int x) { a.push(x); }

    void erase(int x) { b.push(x); }

    int top() {
        while (not a.empty()) {
            const int v = a.top();
            if (b.empty()) {
                return v;
            } else if (v == b.top()) {
                a.pop();
                b.pop();
            } else {
                return v;
            }
        }
        return inf;
    }
};

struct RIEPM {
    int n, siz;
    vector<PriqueErase> data;

    RIEPM(int n_) : n(n_) {
        siz = 1;
        while (siz < n) siz <<= 1;
        data.assign(2 * siz, PriqueErase());
    }

    void push(int l, int r, int v) {
        assert(0 <= l and l <= r and r <= n);
        for (l += siz, r += siz; l < r; l >>= 1, r >>= 1) {
            if (l & 1) data[l++].push(v);
            if (r & 1) data[--r].push(v);
        }
    }

    void erase(int l, int r, int v) {
        assert(0 <= l and l <= r and r <= n);
        for (l += siz, r += siz; l < r; l >>= 1, r >>= 1) {
            if (l & 1) data[l++].erase(v);
            if (r & 1) data[--r].erase(v);
        }
    }

    int top(int i) {
        assert(0 <= i and i < n);
        i += siz;
        int res = inf;
        while (i != 0) {
            res = min(res, data[i].top());
            i >>= 1;
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K, Q;
    cin >> N >> K >> Q;
    vector<int> X(N), T(N), A(N), B(N);
    REP(i, N) {
        cin >> X[i] >> T[i] >> A[i] >> B[i];
        --T[i];
    }
    vector<int> L(Q), Y(Q);
    REP(i, Q) cin >> L[i] >> Y[i];

    auto reverse_points = [&]() {
        REP(i, N) X[i] = inf - X[i];
        REP(i, Q) L[i] = inf - L[i];
    };

    auto solve = [&]() {
        vector<int> press;
        REP(i, N) press.push_back(X[i]);
        REP(i, Q) press.push_back(L[i]);
        sort(ALL(press));
        press.erase(unique(ALL(press)), press.end());

        auto get_key = [&](int i) { return (int)(lower_bound(ALL(press), i) - press.begin()); };

        const int M = (int)press.size();
        RIEPM hp(M);

        vector<tuple<int, int, int, int>> event;
        REP(i, N) {
            event.push_back({A[i], 0, X[i], T[i]});
            event.push_back({B[i] + 1, 1, X[i], T[i]});
        }
        REP(i, Q) event.push_back({Y[i], 2, L[i], i});
        sort(ALL(event));

        vector<map<int, int>> pd(K);
        vector<int> res(Q, -1);

        int cnt_zero = K;
        for (const auto &[c, qt, p, i] : event) {
            if (qt == 0) {
                if (pd[i].empty()) --cnt_zero;
                if (pd[i].find(p) != pd[i].end()) {
                    ++pd[i][p];
                    continue;
                }
                ++pd[i][p];
                auto itr = pd[i].find(p);
                auto itr_r = itr;
                ++itr_r;
                if (itr_r == pd[i].end()) {
                    hp.push(get_key(p), M, p);
                } else {
                    hp.push(get_key(p), get_key((p + itr_r->first + 2) / 2), p);
                }
                if (itr == pd[i].begin()) continue;
                auto itr_l = itr;
                --itr_l;
                if (itr_r != pd[i].end()) {
                    hp.erase(get_key(itr_l->first), get_key((itr_l->first + itr_r->first + 2) / 2),
                             itr_l->first);
                } else {
                    hp.erase(get_key(itr_l->first), M, itr_l->first);
                }
                hp.push(get_key(itr_l->first), get_key((itr_l->first + p + 2) / 2), itr_l->first);
            }
            if (qt == 1) {
                if (pd[i].size() == 1) ++cnt_zero;
                --pd[i][p];
                if (pd[i][p] != 0) {
                    continue;
                }
                pd[i].erase(p);
                auto itr_r = pd[i].upper_bound(p);
                if (itr_r != pd[i].end()) {
                    hp.erase(get_key(p), get_key((p + itr_r->first + 2) / 2), p);
                } else {
                    hp.erase(get_key(p), M, p);
                }
                if (itr_r == pd[i].begin()) continue;
                auto itr_l = itr_r;
                --itr_l;
                hp.erase(get_key(itr_l->first), get_key((itr_l->first + p + 2) / 2), itr_l->first);
                if (itr_r != pd[i].end()) {
                    hp.push(get_key(itr_l->first), get_key((itr_l->first + itr_r->first + 2) / 2),
                            itr_l->first);
                } else {
                    hp.push(get_key(itr_l->first), M, itr_l->first);
                }
            }
            if (qt == 2) {
                if (cnt_zero != 0) continue;
                const int pi = get_key(p);
                const int vi = hp.top(pi);
                if (vi == inf) continue;
                res[i] = p - vi;
            }
        }

        return res;
    };

    const auto res1 = solve();
    reverse_points();
    const auto res2 = solve();
    REP(i, Q) {
        const int ans = max(res1[i], res2[i]);
        cout << ans << '\n';
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 320 KB Output is correct
6 Correct 5 ms 592 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 3 ms 592 KB Output is correct
14 Correct 3 ms 588 KB Output is correct
15 Correct 3 ms 588 KB Output is correct
16 Correct 3 ms 596 KB Output is correct
17 Correct 3 ms 596 KB Output is correct
18 Correct 3 ms 588 KB Output is correct
19 Correct 4 ms 596 KB Output is correct
20 Correct 4 ms 596 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 3 ms 596 KB Output is correct
23 Correct 2 ms 604 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 3 ms 688 KB Output is correct
26 Correct 3 ms 588 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 588 KB Output is correct
29 Correct 2 ms 592 KB Output is correct
30 Correct 2 ms 592 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 320 KB Output is correct
6 Correct 5 ms 592 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 3 ms 592 KB Output is correct
14 Correct 3 ms 588 KB Output is correct
15 Correct 3 ms 588 KB Output is correct
16 Correct 3 ms 596 KB Output is correct
17 Correct 3 ms 596 KB Output is correct
18 Correct 3 ms 588 KB Output is correct
19 Correct 4 ms 596 KB Output is correct
20 Correct 4 ms 596 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 3 ms 596 KB Output is correct
23 Correct 2 ms 604 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 3 ms 688 KB Output is correct
26 Correct 3 ms 588 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 588 KB Output is correct
29 Correct 2 ms 592 KB Output is correct
30 Correct 2 ms 592 KB Output is correct
31 Correct 1555 ms 47152 KB Output is correct
32 Correct 109 ms 10516 KB Output is correct
33 Correct 1211 ms 40768 KB Output is correct
34 Correct 1507 ms 48116 KB Output is correct
35 Correct 1499 ms 45400 KB Output is correct
36 Correct 1236 ms 39724 KB Output is correct
37 Correct 966 ms 41716 KB Output is correct
38 Correct 745 ms 37532 KB Output is correct
39 Correct 632 ms 39520 KB Output is correct
40 Correct 616 ms 37432 KB Output is correct
41 Correct 1164 ms 42588 KB Output is correct
42 Correct 1016 ms 44804 KB Output is correct
43 Correct 102 ms 11652 KB Output is correct
44 Correct 1034 ms 41676 KB Output is correct
45 Correct 969 ms 40744 KB Output is correct
46 Correct 944 ms 38224 KB Output is correct
47 Correct 418 ms 38184 KB Output is correct
48 Correct 472 ms 40016 KB Output is correct
49 Correct 612 ms 41920 KB Output is correct
50 Correct 614 ms 43548 KB Output is correct
51 Correct 643 ms 41260 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4890 ms 290320 KB Output is correct
2 Correct 3653 ms 265304 KB Output is correct
3 Correct 1799 ms 262704 KB Output is correct
4 Correct 4147 ms 299664 KB Output is correct
5 Correct 2879 ms 261004 KB Output is correct
6 Correct 3286 ms 260252 KB Output is correct
7 Correct 1843 ms 267332 KB Output is correct
8 Correct 4970 ms 298056 KB Output is correct
9 Execution timed out 5060 ms 293936 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5091 ms 302848 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 320 KB Output is correct
6 Correct 5 ms 592 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 3 ms 592 KB Output is correct
14 Correct 3 ms 588 KB Output is correct
15 Correct 3 ms 588 KB Output is correct
16 Correct 3 ms 596 KB Output is correct
17 Correct 3 ms 596 KB Output is correct
18 Correct 3 ms 588 KB Output is correct
19 Correct 4 ms 596 KB Output is correct
20 Correct 4 ms 596 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 3 ms 596 KB Output is correct
23 Correct 2 ms 604 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 3 ms 688 KB Output is correct
26 Correct 3 ms 588 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 588 KB Output is correct
29 Correct 2 ms 592 KB Output is correct
30 Correct 2 ms 592 KB Output is correct
31 Correct 1555 ms 47152 KB Output is correct
32 Correct 109 ms 10516 KB Output is correct
33 Correct 1211 ms 40768 KB Output is correct
34 Correct 1507 ms 48116 KB Output is correct
35 Correct 1499 ms 45400 KB Output is correct
36 Correct 1236 ms 39724 KB Output is correct
37 Correct 966 ms 41716 KB Output is correct
38 Correct 745 ms 37532 KB Output is correct
39 Correct 632 ms 39520 KB Output is correct
40 Correct 616 ms 37432 KB Output is correct
41 Correct 1164 ms 42588 KB Output is correct
42 Correct 1016 ms 44804 KB Output is correct
43 Correct 102 ms 11652 KB Output is correct
44 Correct 1034 ms 41676 KB Output is correct
45 Correct 969 ms 40744 KB Output is correct
46 Correct 944 ms 38224 KB Output is correct
47 Correct 418 ms 38184 KB Output is correct
48 Correct 472 ms 40016 KB Output is correct
49 Correct 612 ms 41920 KB Output is correct
50 Correct 614 ms 43548 KB Output is correct
51 Correct 643 ms 41260 KB Output is correct
52 Correct 501 ms 43632 KB Output is correct
53 Correct 536 ms 42076 KB Output is correct
54 Correct 1125 ms 51328 KB Output is correct
55 Correct 1088 ms 42716 KB Output is correct
56 Correct 917 ms 42444 KB Output is correct
57 Correct 1230 ms 43568 KB Output is correct
58 Correct 1041 ms 44964 KB Output is correct
59 Correct 832 ms 44044 KB Output is correct
60 Correct 1049 ms 44364 KB Output is correct
61 Correct 89 ms 13800 KB Output is correct
62 Correct 524 ms 42608 KB Output is correct
63 Correct 865 ms 47532 KB Output is correct
64 Correct 984 ms 47948 KB Output is correct
65 Correct 1185 ms 48536 KB Output is correct
66 Correct 1386 ms 42832 KB Output is correct
67 Incorrect 196 ms 12400 KB Output isn't correct
68 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 320 KB Output is correct
6 Correct 5 ms 592 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 3 ms 592 KB Output is correct
14 Correct 3 ms 588 KB Output is correct
15 Correct 3 ms 588 KB Output is correct
16 Correct 3 ms 596 KB Output is correct
17 Correct 3 ms 596 KB Output is correct
18 Correct 3 ms 588 KB Output is correct
19 Correct 4 ms 596 KB Output is correct
20 Correct 4 ms 596 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 3 ms 596 KB Output is correct
23 Correct 2 ms 604 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 3 ms 688 KB Output is correct
26 Correct 3 ms 588 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 588 KB Output is correct
29 Correct 2 ms 592 KB Output is correct
30 Correct 2 ms 592 KB Output is correct
31 Correct 1555 ms 47152 KB Output is correct
32 Correct 109 ms 10516 KB Output is correct
33 Correct 1211 ms 40768 KB Output is correct
34 Correct 1507 ms 48116 KB Output is correct
35 Correct 1499 ms 45400 KB Output is correct
36 Correct 1236 ms 39724 KB Output is correct
37 Correct 966 ms 41716 KB Output is correct
38 Correct 745 ms 37532 KB Output is correct
39 Correct 632 ms 39520 KB Output is correct
40 Correct 616 ms 37432 KB Output is correct
41 Correct 1164 ms 42588 KB Output is correct
42 Correct 1016 ms 44804 KB Output is correct
43 Correct 102 ms 11652 KB Output is correct
44 Correct 1034 ms 41676 KB Output is correct
45 Correct 969 ms 40744 KB Output is correct
46 Correct 944 ms 38224 KB Output is correct
47 Correct 418 ms 38184 KB Output is correct
48 Correct 472 ms 40016 KB Output is correct
49 Correct 612 ms 41920 KB Output is correct
50 Correct 614 ms 43548 KB Output is correct
51 Correct 643 ms 41260 KB Output is correct
52 Correct 4890 ms 290320 KB Output is correct
53 Correct 3653 ms 265304 KB Output is correct
54 Correct 1799 ms 262704 KB Output is correct
55 Correct 4147 ms 299664 KB Output is correct
56 Correct 2879 ms 261004 KB Output is correct
57 Correct 3286 ms 260252 KB Output is correct
58 Correct 1843 ms 267332 KB Output is correct
59 Correct 4970 ms 298056 KB Output is correct
60 Execution timed out 5060 ms 293936 KB Time limit exceeded
61 Halted 0 ms 0 KB -