oj.uz

Submission #925044

# Submission time Handle Problem Language Result Execution time Memory
925044 2024-02-10T13:57:02 Z Camillus New Home (APIO18_new_home) C++17
80 / 100
 5000 ms 807520 KB 
#include "bits/stdc++.h"
#pragma GCC optimize("O3")
using namespace std;

constexpr int INF = 1e9;

struct Event {
    static constexpr int OPEN = 0;
    static constexpr int CLOSE = 1;
    static constexpr int QUERY = 2;

    int type = OPEN;
    int ind = 0;

    Event() = default;

    Event(int type, int ind) : type(type), ind(ind) {
    }

    bool operator<(const Event&other) const {
        return type < other.type;
    }
};

namespace st {
    static constexpr int size = 1 << 21;

    multiset<int> tree[size * 2 - 1];

    void add(int i, int v) {
        int x = size + i - 1;
        tree[x].insert(v);

        while (x) {
            x = (x - 1) / 2;
            tree[x].insert(v);
        }
    }

    void del(int i, int v) {
        int x = size + i - 1;
        tree[x].erase(tree[x].find(v));

        while (x) {
            x = (x - 1) / 2;
            tree[x].erase(tree[x].find(v));
        }
    }

    int get(int l, int r, int x = 0, int lx = 0, int rx = size) {
        if (tree[x].empty() || l >= rx || lx >= r) {
            return 0;
        }

        if (l <= lx && rx <= r) {
            return *prev(tree[x].end());
        }

        return max(
            get(l, r, x * 2 + 1, lx, (lx + rx) / 2),
            get(l, r, x * 2 + 2, (lx + rx) / 2, rx)
        );
    }
}

namespace st2 {
    static constexpr int size = 1 << 21;

    int tree[size * 2 - 1];

    void set(int i, int v) {
        int x = size + i - 1;
        tree[x] = max(tree[x], v);
        while (x) {
            x = (x - 1) / 2;
            tree[x] = max(tree[x * 2 + 1], tree[x * 2 + 2]);
        }
    }

    int get(int l, int r, int x = 0, int lx = 0, int rx = size) {
        if (l <= lx && rx <= r) {
            return tree[x];
        }

        if (l >= rx || lx >= r) {
            return 0;
        }

        return max(
            get(l, r, x * 2 + 1, lx, (lx + rx) / 2),
            get(l, r, x * 2 + 2, (lx + rx) / 2, rx)
        );
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, q;
    cin >> n >> k >> q;

    map<int, vector<Event>> events;

    vector<int> P = {-INF + 1, INF - 1};

    bool ok = true;

    vector<int> x(n), t(n), a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> t[i] >> a[i] >> b[i];
        t[i]--;

        if (a[i] != 1) {
            ok = false;
        }

        P.push_back(x[i] + 1);
        P.push_back(x[i] - 1);

        events[a[i]].emplace_back(Event::OPEN, i);
        events[b[i] + 1].emplace_back(Event::CLOSE, i);
    }

    vector<int> l(q), y(q);
    vector<int> ans(q);

    for (int i = 0; i < q; i++) {
        cin >> l[i] >> y[i];

        P.push_back(l[i] + 1);
        P.push_back(l[i] - 1);

        events[y[i]].emplace_back(Event::QUERY, i);
    }

    sort(P.begin(), P.end());
    P.erase(unique(P.begin(), P.end()), P.end());

    vector<multiset<int>> pos(k);

    if (!ok) {
        for (int i = 0; i < k; i++) {
            pos[i] = {-INF, INF};
            st::add(0, INF - 1);
        }

        for (auto [cur_pos, cur_events]: events) {
            for (const auto&event: cur_events) {
                if (event.type == Event::OPEN) {
                    auto it = pos[t[event.ind]].insert(x[event.ind]);

                    int R = *next(it);
                    int L = *prev(it);
                    int M = *it;

                    if (L + 1 <= R - 1) {
                        int j = lower_bound(P.begin(), P.end(), L + 1) - P.begin();
                        st::del(j, R - 1);
                    }

                    if (L + 1 <= M - 1) {
                        int j = lower_bound(P.begin(), P.end(), L + 1) - P.begin();
                        st::add(j, M - 1);
                    }

                    if (M + 1 <= R - 1) {
                        int j = lower_bound(P.begin(), P.end(), M + 1) - P.begin();
                        st::add(j, R - 1);
                    }
                } else if (event.type == Event::CLOSE) {
                    auto it = pos[t[event.ind]].find(x[event.ind]);

                    int R = *next(it);
                    int L = *prev(it);
                    int M = *it;

                    if (L + 1 <= R - 1) {
                        int j = lower_bound(P.begin(), P.end(), L + 1) - P.begin();
                        st::add(j, R - 1);
                    }

                    if (L + 1 <= M - 1) {
                        int j = lower_bound(P.begin(), P.end(), L + 1) - P.begin();
                        st::del(j, M - 1);
                    }

                    if (M + 1 <= R - 1) {
                        int j = lower_bound(P.begin(), P.end(), M + 1) - P.begin();
                        st::del(j, R - 1);
                    }

                    pos[t[event.ind]].erase(it);
                } else {
                    int loc = l[event.ind];

                    int L = -1, R = 1e8 + 5;

                    while (R - L > 1) {
                        int M = (L + R) / 2;

                        int left = loc - M;
                        int right = loc + M;

                        int j = upper_bound(P.begin(), P.end(), left) - P.begin();
                        if (st::get(0, j) < right) {
                            R = M;
                        }
                        else {
                            L = M;
                        }
                    }

                    if (R == 1e8 + 5) {
                        ans[event.ind] = -1;
                    } else {
                        ans[event.ind] = R;
                    }
                }
            }
        }

        for (int i = 0; i < q; i++) {
            cout << ans[i] << '\n';
        }
    } else {
        for (int i = 0; i < k; i++) {
            pos[i] = {-INF, INF};
        }

        for (int i = 0; i < n; i++) {
            pos[t[i]].insert(x[i]);
        }

        for (int i = 0; i < k; i++) {
            for (auto it = pos[i].begin(); it != pos[i].end() && next(it) != pos[i].end(); it = next(it)) {
                int L = *it;
                int R = *next(it);
                int j = lower_bound(P.begin(), P.end(), L + 1) - P.begin();
                st2::set(j, R - 1);
            }
        }

        for (auto [cur_pos, cur_events]: events) {
            for (const auto&event: cur_events) {
                if (event.type == Event::OPEN) {
                } else if (event.type == Event::CLOSE) {
                    auto it = pos[t[event.ind]].find(x[event.ind]);

                    int R = *next(it);
                    int L = *prev(it);
                    int M = *it;

                    if (L + 1 <= R - 1) {
                        int j = lower_bound(P.begin(), P.end(), L + 1) - P.begin();
                        st2::set(j, R - 1);
                    }

                    pos[t[event.ind]].erase(it);
                } else {
                    int loc = l[event.ind];

                    int L = -1, R = 1e8 + 5;

                    while (R - L > 1) {
                        int M = (L + R) / 2;

                        int left = loc - M;
                        int right = loc + M;

                        int j = upper_bound(P.begin(), P.end(), left) - P.begin();
                        if (st2::get(0, j) < right) {
                            R = M;
                        }
                        else {
                            L = M;
                        }
                    }

                    if (R == 1e8 + 5) {
                        ans[event.ind] = -1;
                    } else {
                        ans[event.ind] = R;
                    }
                }
            }
        }

        for (int i = 0; i < q; i++) {
            cout << ans[i] << '\n';
        }
    }
    return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:251:25: warning: unused variable 'M' [-Wunused-variable]
  251 |                     int M = *it;
      |                         ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 199504 KB Output is correct
2 Correct 57 ms 199312 KB Output is correct
3 Correct 56 ms 199256 KB Output is correct
4 Correct 56 ms 199328 KB Output is correct
5 Correct 61 ms 199412 KB Output is correct
6 Correct 65 ms 199688 KB Output is correct
7 Correct 63 ms 200020 KB Output is correct
8 Correct 62 ms 199904 KB Output is correct
9 Correct 65 ms 200244 KB Output is correct
10 Correct 64 ms 199828 KB Output is correct
11 Correct 62 ms 199376 KB Output is correct
12 Correct 61 ms 199540 KB Output is correct
13 Correct 63 ms 199500 KB Output is correct
14 Correct 61 ms 199328 KB Output is correct
15 Correct 65 ms 199764 KB Output is correct
16 Correct 65 ms 199764 KB Output is correct
17 Correct 72 ms 199508 KB Output is correct
18 Correct 64 ms 199720 KB Output is correct
19 Correct 65 ms 199932 KB Output is correct
20 Correct 75 ms 199508 KB Output is correct
21 Correct 63 ms 199512 KB Output is correct
22 Correct 68 ms 200280 KB Output is correct
23 Correct 65 ms 200012 KB Output is correct
24 Correct 63 ms 199764 KB Output is correct
25 Correct 71 ms 199508 KB Output is correct
26 Correct 62 ms 199516 KB Output is correct
27 Correct 61 ms 199512 KB Output is correct
28 Correct 72 ms 199292 KB Output is correct
29 Correct 61 ms 199516 KB Output is correct
30 Correct 64 ms 199248 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 199504 KB Output is correct
2 Correct 57 ms 199312 KB Output is correct
3 Correct 56 ms 199256 KB Output is correct
4 Correct 56 ms 199328 KB Output is correct
5 Correct 61 ms 199412 KB Output is correct
6 Correct 65 ms 199688 KB Output is correct
7 Correct 63 ms 200020 KB Output is correct
8 Correct 62 ms 199904 KB Output is correct
9 Correct 65 ms 200244 KB Output is correct
10 Correct 64 ms 199828 KB Output is correct
11 Correct 62 ms 199376 KB Output is correct
12 Correct 61 ms 199540 KB Output is correct
13 Correct 63 ms 199500 KB Output is correct
14 Correct 61 ms 199328 KB Output is correct
15 Correct 65 ms 199764 KB Output is correct
16 Correct 65 ms 199764 KB Output is correct
17 Correct 72 ms 199508 KB Output is correct
18 Correct 64 ms 199720 KB Output is correct
19 Correct 65 ms 199932 KB Output is correct
20 Correct 75 ms 199508 KB Output is correct
21 Correct 63 ms 199512 KB Output is correct
22 Correct 68 ms 200280 KB Output is correct
23 Correct 65 ms 200012 KB Output is correct
24 Correct 63 ms 199764 KB Output is correct
25 Correct 71 ms 199508 KB Output is correct
26 Correct 62 ms 199516 KB Output is correct
27 Correct 61 ms 199512 KB Output is correct
28 Correct 72 ms 199292 KB Output is correct
29 Correct 61 ms 199516 KB Output is correct
30 Correct 64 ms 199248 KB Output is correct
31 Correct 3119 ms 290568 KB Output is correct
32 Correct 329 ms 206016 KB Output is correct
33 Correct 2486 ms 248712 KB Output is correct
34 Correct 2928 ms 249160 KB Output is correct
35 Correct 2901 ms 289764 KB Output is correct
36 Correct 2430 ms 289760 KB Output is correct
37 Correct 1429 ms 229832 KB Output is correct
38 Correct 1405 ms 229576 KB Output is correct
39 Correct 1030 ms 225480 KB Output is correct
40 Correct 1089 ms 225740 KB Output is correct
41 Correct 1176 ms 225876 KB Output is correct
42 Correct 1256 ms 226176 KB Output is correct
43 Correct 223 ms 208836 KB Output is correct
44 Correct 1172 ms 226020 KB Output is correct
45 Correct 945 ms 225476 KB Output is correct
46 Correct 787 ms 225220 KB Output is correct
47 Correct 704 ms 224088 KB Output is correct
48 Correct 626 ms 223784 KB Output is correct
49 Correct 765 ms 224780 KB Output is correct
50 Correct 1083 ms 225356 KB Output is correct
51 Correct 702 ms 224156 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1870 ms 300244 KB Output is correct
2 Correct 2944 ms 290028 KB Output is correct
3 Correct 1877 ms 334260 KB Output is correct
4 Correct 1850 ms 305992 KB Output is correct
5 Correct 2816 ms 289168 KB Output is correct
6 Correct 2879 ms 289388 KB Output is correct
7 Correct 1662 ms 334308 KB Output is correct
8 Correct 1711 ms 306060 KB Output is correct
9 Correct 1923 ms 295968 KB Output is correct
10 Correct 2571 ms 290680 KB Output is correct
11 Correct 1920 ms 289024 KB Output is correct
12 Correct 1997 ms 290548 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3025 ms 322128 KB Output is correct
2 Correct 893 ms 240492 KB Output is correct
3 Correct 3608 ms 319468 KB Output is correct
4 Correct 2212 ms 362608 KB Output is correct
5 Correct 2197 ms 328932 KB Output is correct
6 Correct 2248 ms 334160 KB Output is correct
7 Correct 3531 ms 319168 KB Output is correct
8 Correct 3542 ms 319704 KB Output is correct
9 Correct 2152 ms 363768 KB Output is correct
10 Correct 2305 ms 331920 KB Output is correct
11 Correct 2588 ms 323820 KB Output is correct
12 Correct 3287 ms 320880 KB Output is correct
13 Correct 1908 ms 317092 KB Output is correct
14 Correct 1890 ms 316436 KB Output is correct
15 Correct 2113 ms 318368 KB Output is correct
16 Correct 2317 ms 319972 KB Output is correct
17 Correct 2206 ms 317888 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 199504 KB Output is correct
2 Correct 57 ms 199312 KB Output is correct
3 Correct 56 ms 199256 KB Output is correct
4 Correct 56 ms 199328 KB Output is correct
5 Correct 61 ms 199412 KB Output is correct
6 Correct 65 ms 199688 KB Output is correct
7 Correct 63 ms 200020 KB Output is correct
8 Correct 62 ms 199904 KB Output is correct
9 Correct 65 ms 200244 KB Output is correct
10 Correct 64 ms 199828 KB Output is correct
11 Correct 62 ms 199376 KB Output is correct
12 Correct 61 ms 199540 KB Output is correct
13 Correct 63 ms 199500 KB Output is correct
14 Correct 61 ms 199328 KB Output is correct
15 Correct 65 ms 199764 KB Output is correct
16 Correct 65 ms 199764 KB Output is correct
17 Correct 72 ms 199508 KB Output is correct
18 Correct 64 ms 199720 KB Output is correct
19 Correct 65 ms 199932 KB Output is correct
20 Correct 75 ms 199508 KB Output is correct
21 Correct 63 ms 199512 KB Output is correct
22 Correct 68 ms 200280 KB Output is correct
23 Correct 65 ms 200012 KB Output is correct
24 Correct 63 ms 199764 KB Output is correct
25 Correct 71 ms 199508 KB Output is correct
26 Correct 62 ms 199516 KB Output is correct
27 Correct 61 ms 199512 KB Output is correct
28 Correct 72 ms 199292 KB Output is correct
29 Correct 61 ms 199516 KB Output is correct
30 Correct 64 ms 199248 KB Output is correct
31 Correct 3119 ms 290568 KB Output is correct
32 Correct 329 ms 206016 KB Output is correct
33 Correct 2486 ms 248712 KB Output is correct
34 Correct 2928 ms 249160 KB Output is correct
35 Correct 2901 ms 289764 KB Output is correct
36 Correct 2430 ms 289760 KB Output is correct
37 Correct 1429 ms 229832 KB Output is correct
38 Correct 1405 ms 229576 KB Output is correct
39 Correct 1030 ms 225480 KB Output is correct
40 Correct 1089 ms 225740 KB Output is correct
41 Correct 1176 ms 225876 KB Output is correct
42 Correct 1256 ms 226176 KB Output is correct
43 Correct 223 ms 208836 KB Output is correct
44 Correct 1172 ms 226020 KB Output is correct
45 Correct 945 ms 225476 KB Output is correct
46 Correct 787 ms 225220 KB Output is correct
47 Correct 704 ms 224088 KB Output is correct
48 Correct 626 ms 223784 KB Output is correct
49 Correct 765 ms 224780 KB Output is correct
50 Correct 1083 ms 225356 KB Output is correct
51 Correct 702 ms 224156 KB Output is correct
52 Correct 2721 ms 360188 KB Output is correct
53 Correct 3874 ms 319432 KB Output is correct
54 Correct 3824 ms 313084 KB Output is correct
55 Correct 1975 ms 270880 KB Output is correct
56 Correct 2078 ms 293064 KB Output is correct
57 Correct 1540 ms 239436 KB Output is correct
58 Correct 2589 ms 271020 KB Output is correct
59 Correct 2867 ms 293428 KB Output is correct
60 Correct 1893 ms 239812 KB Output is correct
61 Correct 215 ms 217540 KB Output is correct
62 Correct 2649 ms 360256 KB Output is correct
63 Correct 3525 ms 314268 KB Output is correct
64 Correct 3607 ms 291408 KB Output is correct
65 Correct 3076 ms 247660 KB Output is correct
66 Correct 1356 ms 227140 KB Output is correct
67 Correct 2684 ms 226688 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 199504 KB Output is correct
2 Correct 57 ms 199312 KB Output is correct
3 Correct 56 ms 199256 KB Output is correct
4 Correct 56 ms 199328 KB Output is correct
5 Correct 61 ms 199412 KB Output is correct
6 Correct 65 ms 199688 KB Output is correct
7 Correct 63 ms 200020 KB Output is correct
8 Correct 62 ms 199904 KB Output is correct
9 Correct 65 ms 200244 KB Output is correct
10 Correct 64 ms 199828 KB Output is correct
11 Correct 62 ms 199376 KB Output is correct
12 Correct 61 ms 199540 KB Output is correct
13 Correct 63 ms 199500 KB Output is correct
14 Correct 61 ms 199328 KB Output is correct
15 Correct 65 ms 199764 KB Output is correct
16 Correct 65 ms 199764 KB Output is correct
17 Correct 72 ms 199508 KB Output is correct
18 Correct 64 ms 199720 KB Output is correct
19 Correct 65 ms 199932 KB Output is correct
20 Correct 75 ms 199508 KB Output is correct
21 Correct 63 ms 199512 KB Output is correct
22 Correct 68 ms 200280 KB Output is correct
23 Correct 65 ms 200012 KB Output is correct
24 Correct 63 ms 199764 KB Output is correct
25 Correct 71 ms 199508 KB Output is correct
26 Correct 62 ms 199516 KB Output is correct
27 Correct 61 ms 199512 KB Output is correct
28 Correct 72 ms 199292 KB Output is correct
29 Correct 61 ms 199516 KB Output is correct
30 Correct 64 ms 199248 KB Output is correct
31 Correct 3119 ms 290568 KB Output is correct
32 Correct 329 ms 206016 KB Output is correct
33 Correct 2486 ms 248712 KB Output is correct
34 Correct 2928 ms 249160 KB Output is correct
35 Correct 2901 ms 289764 KB Output is correct
36 Correct 2430 ms 289760 KB Output is correct
37 Correct 1429 ms 229832 KB Output is correct
38 Correct 1405 ms 229576 KB Output is correct
39 Correct 1030 ms 225480 KB Output is correct
40 Correct 1089 ms 225740 KB Output is correct
41 Correct 1176 ms 225876 KB Output is correct
42 Correct 1256 ms 226176 KB Output is correct
43 Correct 223 ms 208836 KB Output is correct
44 Correct 1172 ms 226020 KB Output is correct
45 Correct 945 ms 225476 KB Output is correct
46 Correct 787 ms 225220 KB Output is correct
47 Correct 704 ms 224088 KB Output is correct
48 Correct 626 ms 223784 KB Output is correct
49 Correct 765 ms 224780 KB Output is correct
50 Correct 1083 ms 225356 KB Output is correct
51 Correct 702 ms 224156 KB Output is correct
52 Correct 1870 ms 300244 KB Output is correct
53 Correct 2944 ms 290028 KB Output is correct
54 Correct 1877 ms 334260 KB Output is correct
55 Correct 1850 ms 305992 KB Output is correct
56 Correct 2816 ms 289168 KB Output is correct
57 Correct 2879 ms 289388 KB Output is correct
58 Correct 1662 ms 334308 KB Output is correct
59 Correct 1711 ms 306060 KB Output is correct
60 Correct 1923 ms 295968 KB Output is correct
61 Correct 2571 ms 290680 KB Output is correct
62 Correct 1920 ms 289024 KB Output is correct
63 Correct 1997 ms 290548 KB Output is correct
64 Correct 3025 ms 322128 KB Output is correct
65 Correct 893 ms 240492 KB Output is correct
66 Correct 3608 ms 319468 KB Output is correct
67 Correct 2212 ms 362608 KB Output is correct
68 Correct 2197 ms 328932 KB Output is correct
69 Correct 2248 ms 334160 KB Output is correct
70 Correct 3531 ms 319168 KB Output is correct
71 Correct 3542 ms 319704 KB Output is correct
72 Correct 2152 ms 363768 KB Output is correct
73 Correct 2305 ms 331920 KB Output is correct
74 Correct 2588 ms 323820 KB Output is correct
75 Correct 3287 ms 320880 KB Output is correct
76 Correct 1908 ms 317092 KB Output is correct
77 Correct 1890 ms 316436 KB Output is correct
78 Correct 2113 ms 318368 KB Output is correct
79 Correct 2317 ms 319972 KB Output is correct
80 Correct 2206 ms 317888 KB Output is correct
81 Correct 2721 ms 360188 KB Output is correct
82 Correct 3874 ms 319432 KB Output is correct
83 Correct 3824 ms 313084 KB Output is correct
84 Correct 1975 ms 270880 KB Output is correct
85 Correct 2078 ms 293064 KB Output is correct
86 Correct 1540 ms 239436 KB Output is correct
87 Correct 2589 ms 271020 KB Output is correct
88 Correct 2867 ms 293428 KB Output is correct
89 Correct 1893 ms 239812 KB Output is correct
90 Correct 215 ms 217540 KB Output is correct
91 Correct 2649 ms 360256 KB Output is correct
92 Correct 3525 ms 314268 KB Output is correct
93 Correct 3607 ms 291408 KB Output is correct
94 Correct 3076 ms 247660 KB Output is correct
95 Correct 1356 ms 227140 KB Output is correct
96 Correct 2684 ms 226688 KB Output is correct
97 Execution timed out 5067 ms 807520 KB Time limit exceeded
98 Halted 0 ms 0 KB -