oj.uz

Submission #525017

# Submission time Handle Problem Language Result Execution time Memory
525017 2022-02-10T13:22:54 Z alrad New Home (APIO18_new_home) C++17
100 / 100
 1608 ms 143972 KB 
#include <bits/stdc++.h>
using namespace std;
const int INF = (int)1.01e9;

void print(vector<int> v) {
    for (int x : v) printf("%d\n", x);
}

struct Segtree {
    int n, N;
    vector<int> t;

    Segtree(int _n) {
        n = _n;
        N = 1;
        while (N < n) N <<= 1;
        t.assign(2 * N, INF);
    }

    void upd(int x, int y) {
        x += N;
        t[x] = y;
        while (x > 1) {
            x >>= 1;
            t[x] = min(t[x * 2], t[x * 2 + 1]);
        }
    }

    int get(int l, int r) {
        int ans = INF;
        l += N; r += N;
        while (l <= r) {
            if (l & 1) ans = min(ans, t[l]);
            if (!(r & 1)) ans = min(ans, t[r]);
            l = (l + 1) >> 1;
            r = (r - 1) >> 1;
        }
        return ans;
    }
};

struct Shop {
    int x, type, a, b;
};

struct Query {
    int x, time;
};

vector<int> fast(vector<Shop> a, int k, vector<Query> b) {
    int n = a.size(), m = b.size();
    vector<int> ans(m, 0);
    for (auto &s : a) {
        s.a = s.a * 3;
        s.b = s.b * 3 + 2;
    }
    for (auto &o : b) o.time = o.time * 3 + 1;

    sort(a.begin(), a.end(), [&](const Shop &x, const Shop &y) {
        return x.type < y.type;
    });


    struct Event {
        int time, type, x;
        bool operator< (const Event &e) const {
            return time < e.time;
        }
    };

    struct Update {
        int t1, t2, x1, x2, val;
    };

    vector<Update> vct[2];
    vct[0].reserve(3 * n + k + 10);
    vct[1].reserve(3 * n + k + 10);

    auto addUpdate = [&](int t1, int t2, int l, int r) {
        if (t1 >= t2) return;
        int mid = l + (r - l) / 2;
        vct[0].push_back({ t1, t2, l, mid, l });
        vct[1].push_back({ t1, t2, -r, -(r - (r - l) / 2), -r });
    };

    int ci = 0;
    for (int c = 0; c < k; c++) {
        static multiset<pair<int, int>> st;
        st.clear();
        st.insert({ -INF, -1 });
        st.insert({ +INF, -1 });

        static vector<Event> events;
        events.clear();
        while (ci < n && a[ci].type == c) {
            auto o = a[ci++];
            events.push_back({ o.a, +1, o.x });
            events.push_back({ o.b, -1, o.x });
        }
        sort(events.begin(), events.end());

        for (auto ev : events) {
            if (ev.type == +1) {
                auto it = st.lower_bound({ ev.x, -1 });
                int rightX = it->first;
                int nTime = ev.time;
                if (rightX == ev.x) nTime = it->second;
                it--;
                int leftX = it->first;
                addUpdate(it->second, ev.time, leftX, rightX);
                st.erase(it);
                st.insert({ leftX, ev.time });
                st.insert({ ev.x, nTime });
            }
            else {
                auto it = st.lower_bound({ ev.x, -1 });
                int midX = it->first, midT = it->second;
                st.erase(it);
                it = st.lower_bound({ ev.x, -1 });
                addUpdate(midT, ev.time, midX, it->first);
                it--;
                int leftX = it->first;
                addUpdate(it->second, ev.time, leftX, midX);
                st.erase(it);
                st.insert({ leftX, ev.time });
            }
        }
        assert(st.size() == 2);
        addUpdate(st.begin()->second, INF, -INF, +INF);
    }

    vector<int> perB(m);
    iota(perB.begin(), perB.end(), 0);
    sort(perB.begin(), perB.end(), [&](int i, int j) {
        return b[i].x < b[j].x;
    });
    struct CEvent {
        int time, type, id;
        bool operator< (const CEvent &rhs) const {
            return time < rhs.time;
        }
    };
    vector<CEvent> events;
    events.reserve(m + vct[0].size() * 2);
    for (int i = 0; i < (int)vct[0].size(); i++) {
        events.push_back({ vct[0][i].t1, 1, i });
        events.push_back({ vct[0][i].t2, 2, i });
    }
    for (int i = 0; i < m; i++) events.push_back({ b[i].time, 0, i });
    sort(events.begin(), events.end());
    Segtree tr(vct[0].size());

    for (int ii = 0; ii < 2; ii++) {
        static vector<pair<int, int>> vv;
        vv.clear();
        for (int i = 0; i < (int)vct[ii].size(); i++) vv.push_back({ vct[ii][i].x2, i });

        sort(vv.begin(), vv.end());
        vector<int> lb1(vct[ii].size());
        for (int i = 0; i < (int)vv.size(); i++) lb1[vv[i].second] = i;
        vector<int> lb2(m);
        int ci = 0;
        for (int i = 0; i < m; i++) {
            while (ci < (int)vv.size() && vv[ci].first < b[perB[i]].x) ci++;
            lb2[perB[i]] = ci;
        }

        for (auto ev : events) {
            if (ev.type == 0) {
                int id = lb2[ev.id];
                ans[ev.id] = max(ans[ev.id], b[ev.id].x - tr.get(id, tr.n - 1));
            }
            if (ev.type == 1) {
                int id = lb1[ev.id];
                tr.upd(id, vct[ii][ev.id].x1);
            }
            if (ev.type == 2) {
                int id = lb1[ev.id];
                tr.upd(id, INF);
            }
        }

        for (auto &o : b) o.x *= -1;
        reverse(perB.begin(), perB.end());
    }

    for (int &x : ans) if (x >= INF / 2) x = -1;
    return ans;
}

int main() {
    int n, k, q;
    scanf("%d%d%d", &n, &k, &q);
    vector<Shop> a(n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d%d", &a[i].x, &a[i].type, &a[i].a, &a[i].b);
        a[i].type--;
    }
    vector<Query> b(q);
    for (int i = 0; i < q; i++) scanf("%d%d", &b[i].x, &b[i].time);

    print(fast(a, k, b));
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:193:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  193 |     scanf("%d%d%d", &n, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:196:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  196 |         scanf("%d%d%d%d", &a[i].x, &a[i].type, &a[i].a, &a[i].b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:200:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  200 |     for (int i = 0; i < q; i++) scanf("%d%d", &b[i].x, &b[i].time);
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 0 ms 292 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 424 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 2 ms 324 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 2 ms 448 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 1 ms 460 KB Output is correct
26 Correct 2 ms 464 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 460 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 0 ms 292 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 424 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 2 ms 324 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 2 ms 448 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 1 ms 460 KB Output is correct
26 Correct 2 ms 464 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 460 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 218 ms 22836 KB Output is correct
32 Correct 120 ms 11100 KB Output is correct
33 Correct 224 ms 22968 KB Output is correct
34 Correct 216 ms 22864 KB Output is correct
35 Correct 224 ms 22832 KB Output is correct
36 Correct 225 ms 23192 KB Output is correct
37 Correct 204 ms 23040 KB Output is correct
38 Correct 209 ms 23596 KB Output is correct
39 Correct 187 ms 23088 KB Output is correct
40 Correct 192 ms 23468 KB Output is correct
41 Correct 187 ms 22836 KB Output is correct
42 Correct 200 ms 22992 KB Output is correct
43 Correct 82 ms 11924 KB Output is correct
44 Correct 183 ms 22936 KB Output is correct
45 Correct 188 ms 23080 KB Output is correct
46 Correct 178 ms 23188 KB Output is correct
47 Correct 157 ms 22200 KB Output is correct
48 Correct 151 ms 22152 KB Output is correct
49 Correct 158 ms 22480 KB Output is correct
50 Correct 169 ms 22888 KB Output is correct
51 Correct 161 ms 22228 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 712 ms 74768 KB Output is correct
2 Correct 764 ms 61968 KB Output is correct
3 Correct 1090 ms 142160 KB Output is correct
4 Correct 785 ms 88068 KB Output is correct
5 Correct 1004 ms 73656 KB Output is correct
6 Correct 812 ms 64532 KB Output is correct
7 Correct 1092 ms 142304 KB Output is correct
8 Correct 788 ms 88052 KB Output is correct
9 Correct 651 ms 68172 KB Output is correct
10 Correct 670 ms 60940 KB Output is correct
11 Correct 622 ms 60660 KB Output is correct
12 Correct 628 ms 60824 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1056 ms 88144 KB Output is correct
2 Correct 530 ms 53084 KB Output is correct
3 Correct 1135 ms 88556 KB Output is correct
4 Correct 1370 ms 141912 KB Output is correct
5 Correct 1109 ms 96452 KB Output is correct
6 Correct 1124 ms 102608 KB Output is correct
7 Correct 1379 ms 102792 KB Output is correct
8 Correct 1161 ms 90804 KB Output is correct
9 Correct 1297 ms 142044 KB Output is correct
10 Correct 1122 ms 98764 KB Output is correct
11 Correct 1110 ms 89592 KB Output is correct
12 Correct 1115 ms 87168 KB Output is correct
13 Correct 775 ms 86604 KB Output is correct
14 Correct 779 ms 87988 KB Output is correct
15 Correct 811 ms 86336 KB Output is correct
16 Correct 854 ms 86652 KB Output is correct
17 Correct 863 ms 86992 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 0 ms 292 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 424 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 2 ms 324 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 2 ms 448 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 1 ms 460 KB Output is correct
26 Correct 2 ms 464 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 460 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 218 ms 22836 KB Output is correct
32 Correct 120 ms 11100 KB Output is correct
33 Correct 224 ms 22968 KB Output is correct
34 Correct 216 ms 22864 KB Output is correct
35 Correct 224 ms 22832 KB Output is correct
36 Correct 225 ms 23192 KB Output is correct
37 Correct 204 ms 23040 KB Output is correct
38 Correct 209 ms 23596 KB Output is correct
39 Correct 187 ms 23088 KB Output is correct
40 Correct 192 ms 23468 KB Output is correct
41 Correct 187 ms 22836 KB Output is correct
42 Correct 200 ms 22992 KB Output is correct
43 Correct 82 ms 11924 KB Output is correct
44 Correct 183 ms 22936 KB Output is correct
45 Correct 188 ms 23080 KB Output is correct
46 Correct 178 ms 23188 KB Output is correct
47 Correct 157 ms 22200 KB Output is correct
48 Correct 151 ms 22152 KB Output is correct
49 Correct 158 ms 22480 KB Output is correct
50 Correct 169 ms 22888 KB Output is correct
51 Correct 161 ms 22228 KB Output is correct
52 Correct 233 ms 27440 KB Output is correct
53 Correct 238 ms 27524 KB Output is correct
54 Correct 219 ms 24500 KB Output is correct
55 Correct 195 ms 24492 KB Output is correct
56 Correct 208 ms 25288 KB Output is correct
57 Correct 196 ms 23492 KB Output is correct
58 Correct 213 ms 24500 KB Output is correct
59 Correct 218 ms 25256 KB Output is correct
60 Correct 189 ms 23468 KB Output is correct
61 Correct 164 ms 26916 KB Output is correct
62 Correct 221 ms 27504 KB Output is correct
63 Correct 217 ms 25268 KB Output is correct
64 Correct 214 ms 24388 KB Output is correct
65 Correct 212 ms 23648 KB Output is correct
66 Correct 187 ms 22964 KB Output is correct
67 Correct 170 ms 21600 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 0 ms 292 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 424 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 2 ms 324 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 2 ms 448 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 1 ms 460 KB Output is correct
26 Correct 2 ms 464 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 460 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 218 ms 22836 KB Output is correct
32 Correct 120 ms 11100 KB Output is correct
33 Correct 224 ms 22968 KB Output is correct
34 Correct 216 ms 22864 KB Output is correct
35 Correct 224 ms 22832 KB Output is correct
36 Correct 225 ms 23192 KB Output is correct
37 Correct 204 ms 23040 KB Output is correct
38 Correct 209 ms 23596 KB Output is correct
39 Correct 187 ms 23088 KB Output is correct
40 Correct 192 ms 23468 KB Output is correct
41 Correct 187 ms 22836 KB Output is correct
42 Correct 200 ms 22992 KB Output is correct
43 Correct 82 ms 11924 KB Output is correct
44 Correct 183 ms 22936 KB Output is correct
45 Correct 188 ms 23080 KB Output is correct
46 Correct 178 ms 23188 KB Output is correct
47 Correct 157 ms 22200 KB Output is correct
48 Correct 151 ms 22152 KB Output is correct
49 Correct 158 ms 22480 KB Output is correct
50 Correct 169 ms 22888 KB Output is correct
51 Correct 161 ms 22228 KB Output is correct
52 Correct 712 ms 74768 KB Output is correct
53 Correct 764 ms 61968 KB Output is correct
54 Correct 1090 ms 142160 KB Output is correct
55 Correct 785 ms 88068 KB Output is correct
56 Correct 1004 ms 73656 KB Output is correct
57 Correct 812 ms 64532 KB Output is correct
58 Correct 1092 ms 142304 KB Output is correct
59 Correct 788 ms 88052 KB Output is correct
60 Correct 651 ms 68172 KB Output is correct
61 Correct 670 ms 60940 KB Output is correct
62 Correct 622 ms 60660 KB Output is correct
63 Correct 628 ms 60824 KB Output is correct
64 Correct 1056 ms 88144 KB Output is correct
65 Correct 530 ms 53084 KB Output is correct
66 Correct 1135 ms 88556 KB Output is correct
67 Correct 1370 ms 141912 KB Output is correct
68 Correct 1109 ms 96452 KB Output is correct
69 Correct 1124 ms 102608 KB Output is correct
70 Correct 1379 ms 102792 KB Output is correct
71 Correct 1161 ms 90804 KB Output is correct
72 Correct 1297 ms 142044 KB Output is correct
73 Correct 1122 ms 98764 KB Output is correct
74 Correct 1110 ms 89592 KB Output is correct
75 Correct 1115 ms 87168 KB Output is correct
76 Correct 775 ms 86604 KB Output is correct
77 Correct 779 ms 87988 KB Output is correct
78 Correct 811 ms 86336 KB Output is correct
79 Correct 854 ms 86652 KB Output is correct
80 Correct 863 ms 86992 KB Output is correct
81 Correct 233 ms 27440 KB Output is correct
82 Correct 238 ms 27524 KB Output is correct
83 Correct 219 ms 24500 KB Output is correct
84 Correct 195 ms 24492 KB Output is correct
85 Correct 208 ms 25288 KB Output is correct
86 Correct 196 ms 23492 KB Output is correct
87 Correct 213 ms 24500 KB Output is correct
88 Correct 218 ms 25256 KB Output is correct
89 Correct 189 ms 23468 KB Output is correct
90 Correct 164 ms 26916 KB Output is correct
91 Correct 221 ms 27504 KB Output is correct
92 Correct 217 ms 25268 KB Output is correct
93 Correct 214 ms 24388 KB Output is correct
94 Correct 212 ms 23648 KB Output is correct
95 Correct 187 ms 22964 KB Output is correct
96 Correct 170 ms 21600 KB Output is correct
97 Correct 1608 ms 143940 KB Output is correct
98 Correct 600 ms 55144 KB Output is correct
99 Correct 1528 ms 111972 KB Output is correct
100 Correct 1583 ms 143964 KB Output is correct
101 Correct 1514 ms 119376 KB Output is correct
102 Correct 1562 ms 113120 KB Output is correct
103 Correct 1196 ms 111392 KB Output is correct
104 Correct 1186 ms 113632 KB Output is correct
105 Correct 1026 ms 112240 KB Output is correct
106 Correct 1092 ms 113120 KB Output is correct
107 Correct 1262 ms 119548 KB Output is correct
108 Correct 1325 ms 134180 KB Output is correct
109 Correct 1210 ms 114092 KB Output is correct
110 Correct 1346 ms 119636 KB Output is correct
111 Correct 1454 ms 134484 KB Output is correct
112 Correct 1247 ms 114276 KB Output is correct
113 Correct 897 ms 140988 KB Output is correct
114 Correct 1528 ms 143972 KB Output is correct
115 Correct 1508 ms 134352 KB Output is correct
116 Correct 1476 ms 119384 KB Output is correct
117 Correct 1441 ms 114492 KB Output is correct
118 Correct 1291 ms 111708 KB Output is correct
119 Correct 1238 ms 105272 KB Output is correct
120 Correct 761 ms 104048 KB Output is correct
121 Correct 831 ms 108256 KB Output is correct
122 Correct 815 ms 107816 KB Output is correct
123 Correct 858 ms 109204 KB Output is correct
124 Correct 903 ms 110836 KB Output is correct
125 Correct 893 ms 109676 KB Output is correct
126 Correct 966 ms 111104 KB Output is correct