oj.uz

Submission #560311

# Submission time Handle Problem Language Result Execution time Memory
560311 2022-05-11T09:15:40 Z hoanghq2004 New Home (APIO18_new_home) C++14
12 / 100
 4438 ms 1048576 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 3e5 + 10;

int n, k, q;
multiset <int> s[N];
int ans[N];
int cnt, nNode = 1;

void go(int& x) {
    if (!x) x = ++nNode;
}

struct node {
    int lhs, rhs;
    multiset <int> lft, rgt;
} st[N * 30];

int ok;

void upd(int id, int L, int R, int u, int v, int a, int b, int mode) {
    if (u > R || L > v) return;
    if (u <= L && R <= v) {
        if (a < 0) {
            if (mode > 0) st[id].lft.insert(b);
            else st[id].lft.erase(st[id].lft.find(b));
        } else {
            if (mode > 0) st[id].rgt.insert(b);
            else st[id].rgt.erase(st[id].rgt.find(b));
        }
        return;
    }
    int mid = L + R >> 1;
    if (u <= mid) {
        go(st[id].lhs);
        upd(st[id].lhs, L, mid, u, v, a, b, mode);
    }
    if (v > mid) {
        go(st[id].rhs);
        upd(st[id].rhs, mid + 1, R, u, v, a, b, mode);
    }
}

void solve(int id, int L, int R, int x, int &ans) {
    if (st[id].rgt.size()) ans = max(ans, x / 2 + *(--st[id].rgt.end()));
    if (st[id].lft.size()) ans = max(ans, - x / 2 + *(--st[id].lft.end()));
    if (L == R) return;
    int mid = L + R >> 1;
    if (x <= mid) {
        if (st[id].lhs) solve(st[id].lhs, L, mid, x, ans);
    } else {
        if (st[id].rhs) solve(st[id].rhs, mid + 1, R, x, ans);
    }
}

void add(int t, int x) {
    cnt -= (s[t].size() == 2);
    int L = *(--s[t].upper_bound(x));
    int R = *s[t].upper_bound(x);
    upd(1, - 4e8, 4e8, L * 2, L + R, 1, - L, -1);
    upd(1, - 4e8, 4e8, L + R, R * 2, -1, R, -1);
    upd(1, - 4e8, 4e8, L * 2, L + x, 1, - L, 1);
    upd(1, - 4e8, 4e8, L + x, x * 2, -1, x, 1);
    upd(1, - 4e8, 4e8, x * 2, x + R, 1, - x, 1);
    upd(1, - 4e8, 4e8, x + R, R * 2, -1, R, 1);
    s[t].insert(x);
}

void rev(int t, int x) {
    s[t].erase(s[t].find(x));
    int L = *(--s[t].upper_bound(x));
    int R = *s[t].upper_bound(x);
    upd(1, - 4e8, 4e8, L * 2, L + R, 1, - L, 1);
    upd(1, - 4e8, 4e8, L + R, R * 2, -1, R, 1);
    upd(1, - 4e8, 4e8, L * 2, L + x, 1, - L, -1);
    upd(1, - 4e8, 4e8, L + x, x * 2, -1, x, -1);
    upd(1, - 4e8, 4e8, x * 2, x + R, 1, - x, -1);
    upd(1, - 4e8, 4e8, x + R, R * 2, -1, R, -1);
    cnt += (s[t].size() == 2);
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    vector <tuple <int, int, int, int> > events;
    cin >> n >> k >> q;
    for (int i = 0; i < n; ++i) {
        int x, t, a, b;
        cin >> x >> t >> a >> b;
        events.push_back({a, -1, x, t});
        events.push_back({b + 1, 1, x, t});
    }
    for (int i = 1; i <= k; ++i) {
        int L = - 2e8, R = 2e8;
        s[i].insert(L), s[i].insert(R);
        upd(1, - 4e8, 4e8, L * 2, L + R, 1, - L, 1);
        upd(1, - 4e8, 4e8, L + R, R * 2, - 1, R, 1);
    }
    cnt = k;
    vector <tuple <int, int, int> > work;
    for (int i = 1; i <= q; ++i) {
        int x, y;
        cin >> x >> y;
        work.push_back({y, x * 2, i});
    }
    sort(events.begin(), events.end());
    sort(work.begin(), work.end());
    int i = 0;
    for (auto [y, x, id]: work) {
        while (i < events.size() && get<0>(events[i]) <= y) {
            auto [_, cmd, x, t] = events[i];
            if (cmd == -1) add(t, x);
            else rev(t, x);
            ++i;
        }
        if (cnt) ans[id] = -1;
        else solve(1, - 4e8, 4e8, x, ans[id]);
    }
    for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}

Compilation message

new_home.cpp: In function 'void upd(int, int, int, int, int, int, int, int)':
new_home.cpp:43:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int mid = L + R >> 1;
      |               ~~^~~
new_home.cpp: In function 'void solve(int, int, int, int, int&)':
new_home.cpp:58:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |     int mid = L + R >> 1;
      |               ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:118:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |     for (auto [y, x, id]: work) {
      |               ^
new_home.cpp:119:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         while (i < events.size() && get<0>(events[i]) <= y) {
      |                ~~^~~~~~~~~~~~~~~
new_home.cpp:120:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |             auto [_, cmd, x, t] = events[i];
      |                  ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 930272 KB Output is correct
2 Correct 434 ms 930320 KB Output is correct
3 Correct 407 ms 930292 KB Output is correct
4 Correct 426 ms 930312 KB Output is correct
5 Correct 400 ms 930340 KB Output is correct
6 Correct 436 ms 930696 KB Output is correct
7 Correct 411 ms 930960 KB Output is correct
8 Correct 421 ms 931444 KB Output is correct
9 Correct 428 ms 931872 KB Output is correct
10 Correct 455 ms 931104 KB Output is correct
11 Correct 405 ms 930344 KB Output is correct
12 Correct 410 ms 930340 KB Output is correct
13 Correct 427 ms 930220 KB Output is correct
14 Correct 402 ms 930332 KB Output is correct
15 Correct 420 ms 931040 KB Output is correct
16 Correct 421 ms 931148 KB Output is correct
17 Correct 452 ms 930508 KB Output is correct
18 Correct 401 ms 930944 KB Output is correct
19 Correct 424 ms 931372 KB Output is correct
20 Correct 410 ms 930660 KB Output is correct
21 Correct 408 ms 930660 KB Output is correct
22 Correct 432 ms 931916 KB Output is correct
23 Correct 433 ms 931524 KB Output is correct
24 Correct 412 ms 931168 KB Output is correct
25 Correct 425 ms 930536 KB Output is correct
26 Correct 409 ms 930368 KB Output is correct
27 Correct 402 ms 930508 KB Output is correct
28 Correct 440 ms 930304 KB Output is correct
29 Correct 419 ms 930344 KB Output is correct
30 Correct 437 ms 930376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 930272 KB Output is correct
2 Correct 434 ms 930320 KB Output is correct
3 Correct 407 ms 930292 KB Output is correct
4 Correct 426 ms 930312 KB Output is correct
5 Correct 400 ms 930340 KB Output is correct
6 Correct 436 ms 930696 KB Output is correct
7 Correct 411 ms 930960 KB Output is correct
8 Correct 421 ms 931444 KB Output is correct
9 Correct 428 ms 931872 KB Output is correct
10 Correct 455 ms 931104 KB Output is correct
11 Correct 405 ms 930344 KB Output is correct
12 Correct 410 ms 930340 KB Output is correct
13 Correct 427 ms 930220 KB Output is correct
14 Correct 402 ms 930332 KB Output is correct
15 Correct 420 ms 931040 KB Output is correct
16 Correct 421 ms 931148 KB Output is correct
17 Correct 452 ms 930508 KB Output is correct
18 Correct 401 ms 930944 KB Output is correct
19 Correct 424 ms 931372 KB Output is correct
20 Correct 410 ms 930660 KB Output is correct
21 Correct 408 ms 930660 KB Output is correct
22 Correct 432 ms 931916 KB Output is correct
23 Correct 433 ms 931524 KB Output is correct
24 Correct 412 ms 931168 KB Output is correct
25 Correct 425 ms 930536 KB Output is correct
26 Correct 409 ms 930368 KB Output is correct
27 Correct 402 ms 930508 KB Output is correct
28 Correct 440 ms 930304 KB Output is correct
29 Correct 419 ms 930344 KB Output is correct
30 Correct 437 ms 930376 KB Output is correct
31 Correct 4293 ms 1041484 KB Output is correct
32 Correct 709 ms 937408 KB Output is correct
33 Correct 2508 ms 965112 KB Output is correct
34 Correct 4438 ms 976748 KB Output is correct
35 Correct 3584 ms 1032220 KB Output is correct
36 Correct 2406 ms 1011636 KB Output is correct
37 Correct 2380 ms 940328 KB Output is correct
38 Correct 1863 ms 939168 KB Output is correct
39 Correct 1208 ms 934320 KB Output is correct
40 Correct 1306 ms 934532 KB Output is correct
41 Correct 2577 ms 935272 KB Output is correct
42 Correct 2760 ms 935792 KB Output is correct
43 Correct 543 ms 942204 KB Output is correct
44 Correct 2391 ms 934968 KB Output is correct
45 Correct 1959 ms 934424 KB Output is correct
46 Correct 1589 ms 934396 KB Output is correct
47 Correct 1198 ms 934052 KB Output is correct
48 Correct 1176 ms 934208 KB Output is correct
49 Correct 1347 ms 934192 KB Output is correct
50 Correct 2156 ms 934708 KB Output is correct
51 Correct 1305 ms 934296 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1108 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1805 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 930272 KB Output is correct
2 Correct 434 ms 930320 KB Output is correct
3 Correct 407 ms 930292 KB Output is correct
4 Correct 426 ms 930312 KB Output is correct
5 Correct 400 ms 930340 KB Output is correct
6 Correct 436 ms 930696 KB Output is correct
7 Correct 411 ms 930960 KB Output is correct
8 Correct 421 ms 931444 KB Output is correct
9 Correct 428 ms 931872 KB Output is correct
10 Correct 455 ms 931104 KB Output is correct
11 Correct 405 ms 930344 KB Output is correct
12 Correct 410 ms 930340 KB Output is correct
13 Correct 427 ms 930220 KB Output is correct
14 Correct 402 ms 930332 KB Output is correct
15 Correct 420 ms 931040 KB Output is correct
16 Correct 421 ms 931148 KB Output is correct
17 Correct 452 ms 930508 KB Output is correct
18 Correct 401 ms 930944 KB Output is correct
19 Correct 424 ms 931372 KB Output is correct
20 Correct 410 ms 930660 KB Output is correct
21 Correct 408 ms 930660 KB Output is correct
22 Correct 432 ms 931916 KB Output is correct
23 Correct 433 ms 931524 KB Output is correct
24 Correct 412 ms 931168 KB Output is correct
25 Correct 425 ms 930536 KB Output is correct
26 Correct 409 ms 930368 KB Output is correct
27 Correct 402 ms 930508 KB Output is correct
28 Correct 440 ms 930304 KB Output is correct
29 Correct 419 ms 930344 KB Output is correct
30 Correct 437 ms 930376 KB Output is correct
31 Correct 4293 ms 1041484 KB Output is correct
32 Correct 709 ms 937408 KB Output is correct
33 Correct 2508 ms 965112 KB Output is correct
34 Correct 4438 ms 976748 KB Output is correct
35 Correct 3584 ms 1032220 KB Output is correct
36 Correct 2406 ms 1011636 KB Output is correct
37 Correct 2380 ms 940328 KB Output is correct
38 Correct 1863 ms 939168 KB Output is correct
39 Correct 1208 ms 934320 KB Output is correct
40 Correct 1306 ms 934532 KB Output is correct
41 Correct 2577 ms 935272 KB Output is correct
42 Correct 2760 ms 935792 KB Output is correct
43 Correct 543 ms 942204 KB Output is correct
44 Correct 2391 ms 934968 KB Output is correct
45 Correct 1959 ms 934424 KB Output is correct
46 Correct 1589 ms 934396 KB Output is correct
47 Correct 1198 ms 934052 KB Output is correct
48 Correct 1176 ms 934208 KB Output is correct
49 Correct 1347 ms 934192 KB Output is correct
50 Correct 2156 ms 934708 KB Output is correct
51 Correct 1305 ms 934296 KB Output is correct
52 Runtime error 1094 ms 1048576 KB Execution killed with signal 9
53 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 930272 KB Output is correct
2 Correct 434 ms 930320 KB Output is correct
3 Correct 407 ms 930292 KB Output is correct
4 Correct 426 ms 930312 KB Output is correct
5 Correct 400 ms 930340 KB Output is correct
6 Correct 436 ms 930696 KB Output is correct
7 Correct 411 ms 930960 KB Output is correct
8 Correct 421 ms 931444 KB Output is correct
9 Correct 428 ms 931872 KB Output is correct
10 Correct 455 ms 931104 KB Output is correct
11 Correct 405 ms 930344 KB Output is correct
12 Correct 410 ms 930340 KB Output is correct
13 Correct 427 ms 930220 KB Output is correct
14 Correct 402 ms 930332 KB Output is correct
15 Correct 420 ms 931040 KB Output is correct
16 Correct 421 ms 931148 KB Output is correct
17 Correct 452 ms 930508 KB Output is correct
18 Correct 401 ms 930944 KB Output is correct
19 Correct 424 ms 931372 KB Output is correct
20 Correct 410 ms 930660 KB Output is correct
21 Correct 408 ms 930660 KB Output is correct
22 Correct 432 ms 931916 KB Output is correct
23 Correct 433 ms 931524 KB Output is correct
24 Correct 412 ms 931168 KB Output is correct
25 Correct 425 ms 930536 KB Output is correct
26 Correct 409 ms 930368 KB Output is correct
27 Correct 402 ms 930508 KB Output is correct
28 Correct 440 ms 930304 KB Output is correct
29 Correct 419 ms 930344 KB Output is correct
30 Correct 437 ms 930376 KB Output is correct
31 Correct 4293 ms 1041484 KB Output is correct
32 Correct 709 ms 937408 KB Output is correct
33 Correct 2508 ms 965112 KB Output is correct
34 Correct 4438 ms 976748 KB Output is correct
35 Correct 3584 ms 1032220 KB Output is correct
36 Correct 2406 ms 1011636 KB Output is correct
37 Correct 2380 ms 940328 KB Output is correct
38 Correct 1863 ms 939168 KB Output is correct
39 Correct 1208 ms 934320 KB Output is correct
40 Correct 1306 ms 934532 KB Output is correct
41 Correct 2577 ms 935272 KB Output is correct
42 Correct 2760 ms 935792 KB Output is correct
43 Correct 543 ms 942204 KB Output is correct
44 Correct 2391 ms 934968 KB Output is correct
45 Correct 1959 ms 934424 KB Output is correct
46 Correct 1589 ms 934396 KB Output is correct
47 Correct 1198 ms 934052 KB Output is correct
48 Correct 1176 ms 934208 KB Output is correct
49 Correct 1347 ms 934192 KB Output is correct
50 Correct 2156 ms 934708 KB Output is correct
51 Correct 1305 ms 934296 KB Output is correct
52 Runtime error 1108 ms 1048576 KB Execution killed with signal 9
53 Halted 0 ms 0 KB -