oj.uz

Submission #560323

# Submission time Handle Problem Language Result Execution time Memory
560323 2022-05-11T09:42:56 Z hoanghq2004 New Home (APIO18_new_home) C++14
12 / 100
 4144 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;
const int M = 3e8 + 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 + *(--st[id].rgt.end()));
    if (st[id].lft.size()) ans = max(ans, - x + *(--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, 0, M, L, (L + R) / 2, 1, - L, -1);
    upd(1, 0, M, (L + R) / 2 + 1, R, - 1, R, -1);

    upd(1, 0, M, L, (L + x) / 2, 1, - L, 1);
    upd(1, 0, M, (L + x) / 2 + 1, x, - 1, x, 1);

    upd(1, 0, M, x, (x + R) / 2, 1, - x, 1);
    upd(1, 0, M, (x + R) / 2 + 1, R, - 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, 0, M, L, (L + R) / 2, 1, - L, 1);
    upd(1, 0, M, (L + R) / 2 + 1, R, - 1, R, 1);

    upd(1, 0, M, L, (L + x) / 2, 1, - L, -1);
    upd(1, 0, M, (L + x) / 2 + 1, x, - 1, x, -1);

    upd(1, 0, M, x, (x + R) / 2, 1, - x, -1);
    upd(1, 0, M, (x + R) / 2 + 1, R, - 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;
        x += 1e8 + 5;
        events.push_back({a, -1, x, t});
        events.push_back({b + 1, 1, x, t});
    }
    for (int i = 1; i <= k; ++i) {
        s[i].insert(0), s[i].insert(M);
        int L = 0, R = M;
        upd(1, 0, M, L, (L + R) / 2, 1, - L, 1);
        upd(1, 0, M, (L + R) / 2 + 1, R, - 1, R, 1);
    }
    cnt = k;
    vector <tuple <int, int, int> > work;
    for (int i = 1; i <= q; ++i) {
        int x, y;
        cin >> x >> y;
        x += 1e8 + 5;
        work.push_back({y, x, 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, 0, M, 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:44:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     int mid = L + R >> 1;
      |               ~~^~~
new_home.cpp: In function 'void solve(int, int, int, int, int&)':
new_home.cpp:59:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |     int mid = L + R >> 1;
      |               ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:125:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  125 |     for (auto [y, x, id]: work) {
      |               ^
new_home.cpp:126: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]
  126 |         while (i < events.size() && get<0>(events[i]) <= y) {
      |                ~~^~~~~~~~~~~~~~~
new_home.cpp:127:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  127 |             auto [_, cmd, x, t] = events[i];
      |                  ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 930224 KB Output is correct
2 Correct 431 ms 930248 KB Output is correct
3 Correct 423 ms 930364 KB Output is correct
4 Correct 457 ms 930216 KB Output is correct
5 Correct 431 ms 930256 KB Output is correct
6 Correct 424 ms 930760 KB Output is correct
7 Correct 428 ms 930828 KB Output is correct
8 Correct 448 ms 931368 KB Output is correct
9 Correct 418 ms 931760 KB Output is correct
10 Correct 448 ms 931252 KB Output is correct
11 Correct 454 ms 930328 KB Output is correct
12 Correct 427 ms 930392 KB Output is correct
13 Correct 443 ms 930408 KB Output is correct
14 Correct 448 ms 930288 KB Output is correct
15 Correct 445 ms 930936 KB Output is correct
16 Correct 433 ms 931164 KB Output is correct
17 Correct 431 ms 930660 KB Output is correct
18 Correct 441 ms 930896 KB Output is correct
19 Correct 431 ms 931300 KB Output is correct
20 Correct 438 ms 930688 KB Output is correct
21 Correct 446 ms 931916 KB Output is correct
22 Correct 440 ms 931860 KB Output is correct
23 Correct 444 ms 931520 KB Output is correct
24 Correct 449 ms 931144 KB Output is correct
25 Correct 454 ms 930516 KB Output is correct
26 Correct 440 ms 930428 KB Output is correct
27 Correct 425 ms 930476 KB Output is correct
28 Correct 445 ms 930368 KB Output is correct
29 Correct 460 ms 930372 KB Output is correct
30 Correct 474 ms 930276 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 930224 KB Output is correct
2 Correct 431 ms 930248 KB Output is correct
3 Correct 423 ms 930364 KB Output is correct
4 Correct 457 ms 930216 KB Output is correct
5 Correct 431 ms 930256 KB Output is correct
6 Correct 424 ms 930760 KB Output is correct
7 Correct 428 ms 930828 KB Output is correct
8 Correct 448 ms 931368 KB Output is correct
9 Correct 418 ms 931760 KB Output is correct
10 Correct 448 ms 931252 KB Output is correct
11 Correct 454 ms 930328 KB Output is correct
12 Correct 427 ms 930392 KB Output is correct
13 Correct 443 ms 930408 KB Output is correct
14 Correct 448 ms 930288 KB Output is correct
15 Correct 445 ms 930936 KB Output is correct
16 Correct 433 ms 931164 KB Output is correct
17 Correct 431 ms 930660 KB Output is correct
18 Correct 441 ms 930896 KB Output is correct
19 Correct 431 ms 931300 KB Output is correct
20 Correct 438 ms 930688 KB Output is correct
21 Correct 446 ms 931916 KB Output is correct
22 Correct 440 ms 931860 KB Output is correct
23 Correct 444 ms 931520 KB Output is correct
24 Correct 449 ms 931144 KB Output is correct
25 Correct 454 ms 930516 KB Output is correct
26 Correct 440 ms 930428 KB Output is correct
27 Correct 425 ms 930476 KB Output is correct
28 Correct 445 ms 930368 KB Output is correct
29 Correct 460 ms 930372 KB Output is correct
30 Correct 474 ms 930276 KB Output is correct
31 Correct 4144 ms 1035868 KB Output is correct
32 Correct 665 ms 935956 KB Output is correct
33 Correct 2438 ms 963112 KB Output is correct
34 Correct 4108 ms 974736 KB Output is correct
35 Correct 3352 ms 1026372 KB Output is correct
36 Correct 2359 ms 1005892 KB Output is correct
37 Correct 2224 ms 940016 KB Output is correct
38 Correct 1769 ms 938700 KB Output is correct
39 Correct 1242 ms 934224 KB Output is correct
40 Correct 1435 ms 934372 KB Output is correct
41 Correct 3167 ms 935328 KB Output is correct
42 Correct 3334 ms 935696 KB Output is correct
43 Correct 1008 ms 940992 KB Output is correct
44 Correct 2925 ms 935040 KB Output is correct
45 Correct 2283 ms 934532 KB Output is correct
46 Correct 1640 ms 934524 KB Output is correct
47 Correct 1245 ms 934264 KB Output is correct
48 Correct 1159 ms 934276 KB Output is correct
49 Correct 1329 ms 934348 KB Output is correct
50 Correct 1896 ms 934956 KB Output is correct
51 Correct 1344 ms 934312 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1144 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 1806 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 464 ms 930224 KB Output is correct
2 Correct 431 ms 930248 KB Output is correct
3 Correct 423 ms 930364 KB Output is correct
4 Correct 457 ms 930216 KB Output is correct
5 Correct 431 ms 930256 KB Output is correct
6 Correct 424 ms 930760 KB Output is correct
7 Correct 428 ms 930828 KB Output is correct
8 Correct 448 ms 931368 KB Output is correct
9 Correct 418 ms 931760 KB Output is correct
10 Correct 448 ms 931252 KB Output is correct
11 Correct 454 ms 930328 KB Output is correct
12 Correct 427 ms 930392 KB Output is correct
13 Correct 443 ms 930408 KB Output is correct
14 Correct 448 ms 930288 KB Output is correct
15 Correct 445 ms 930936 KB Output is correct
16 Correct 433 ms 931164 KB Output is correct
17 Correct 431 ms 930660 KB Output is correct
18 Correct 441 ms 930896 KB Output is correct
19 Correct 431 ms 931300 KB Output is correct
20 Correct 438 ms 930688 KB Output is correct
21 Correct 446 ms 931916 KB Output is correct
22 Correct 440 ms 931860 KB Output is correct
23 Correct 444 ms 931520 KB Output is correct
24 Correct 449 ms 931144 KB Output is correct
25 Correct 454 ms 930516 KB Output is correct
26 Correct 440 ms 930428 KB Output is correct
27 Correct 425 ms 930476 KB Output is correct
28 Correct 445 ms 930368 KB Output is correct
29 Correct 460 ms 930372 KB Output is correct
30 Correct 474 ms 930276 KB Output is correct
31 Correct 4144 ms 1035868 KB Output is correct
32 Correct 665 ms 935956 KB Output is correct
33 Correct 2438 ms 963112 KB Output is correct
34 Correct 4108 ms 974736 KB Output is correct
35 Correct 3352 ms 1026372 KB Output is correct
36 Correct 2359 ms 1005892 KB Output is correct
37 Correct 2224 ms 940016 KB Output is correct
38 Correct 1769 ms 938700 KB Output is correct
39 Correct 1242 ms 934224 KB Output is correct
40 Correct 1435 ms 934372 KB Output is correct
41 Correct 3167 ms 935328 KB Output is correct
42 Correct 3334 ms 935696 KB Output is correct
43 Correct 1008 ms 940992 KB Output is correct
44 Correct 2925 ms 935040 KB Output is correct
45 Correct 2283 ms 934532 KB Output is correct
46 Correct 1640 ms 934524 KB Output is correct
47 Correct 1245 ms 934264 KB Output is correct
48 Correct 1159 ms 934276 KB Output is correct
49 Correct 1329 ms 934348 KB Output is correct
50 Correct 1896 ms 934956 KB Output is correct
51 Correct 1344 ms 934312 KB Output is correct
52 Runtime error 1034 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 464 ms 930224 KB Output is correct
2 Correct 431 ms 930248 KB Output is correct
3 Correct 423 ms 930364 KB Output is correct
4 Correct 457 ms 930216 KB Output is correct
5 Correct 431 ms 930256 KB Output is correct
6 Correct 424 ms 930760 KB Output is correct
7 Correct 428 ms 930828 KB Output is correct
8 Correct 448 ms 931368 KB Output is correct
9 Correct 418 ms 931760 KB Output is correct
10 Correct 448 ms 931252 KB Output is correct
11 Correct 454 ms 930328 KB Output is correct
12 Correct 427 ms 930392 KB Output is correct
13 Correct 443 ms 930408 KB Output is correct
14 Correct 448 ms 930288 KB Output is correct
15 Correct 445 ms 930936 KB Output is correct
16 Correct 433 ms 931164 KB Output is correct
17 Correct 431 ms 930660 KB Output is correct
18 Correct 441 ms 930896 KB Output is correct
19 Correct 431 ms 931300 KB Output is correct
20 Correct 438 ms 930688 KB Output is correct
21 Correct 446 ms 931916 KB Output is correct
22 Correct 440 ms 931860 KB Output is correct
23 Correct 444 ms 931520 KB Output is correct
24 Correct 449 ms 931144 KB Output is correct
25 Correct 454 ms 930516 KB Output is correct
26 Correct 440 ms 930428 KB Output is correct
27 Correct 425 ms 930476 KB Output is correct
28 Correct 445 ms 930368 KB Output is correct
29 Correct 460 ms 930372 KB Output is correct
30 Correct 474 ms 930276 KB Output is correct
31 Correct 4144 ms 1035868 KB Output is correct
32 Correct 665 ms 935956 KB Output is correct
33 Correct 2438 ms 963112 KB Output is correct
34 Correct 4108 ms 974736 KB Output is correct
35 Correct 3352 ms 1026372 KB Output is correct
36 Correct 2359 ms 1005892 KB Output is correct
37 Correct 2224 ms 940016 KB Output is correct
38 Correct 1769 ms 938700 KB Output is correct
39 Correct 1242 ms 934224 KB Output is correct
40 Correct 1435 ms 934372 KB Output is correct
41 Correct 3167 ms 935328 KB Output is correct
42 Correct 3334 ms 935696 KB Output is correct
43 Correct 1008 ms 940992 KB Output is correct
44 Correct 2925 ms 935040 KB Output is correct
45 Correct 2283 ms 934532 KB Output is correct
46 Correct 1640 ms 934524 KB Output is correct
47 Correct 1245 ms 934264 KB Output is correct
48 Correct 1159 ms 934276 KB Output is correct
49 Correct 1329 ms 934348 KB Output is correct
50 Correct 1896 ms 934956 KB Output is correct
51 Correct 1344 ms 934312 KB Output is correct
52 Runtime error 1144 ms 1048576 KB Execution killed with signal 9
53 Halted 0 ms 0 KB -