oj.uz

Submission #560537

# Submission time Handle Problem Language Result Execution time Memory
560537 2022-05-11T16:37:12 Z hoanghq2004 New Home (APIO18_new_home) C++14
57 / 100
 5000 ms 685444 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, m;
multiset <int> s[N];
int ans[N];
int cnt;
int dta[N * 20];

void fake_add(int t, int x) {
    int L = *(--s[t].upper_bound(x));
    int R = *s[t].upper_bound(x);
    dta[m++] = (L + R) / 2;
    dta[m++] = (L + x) / 2;
    dta[m++] = (x + R) / 2;
    s[t].insert(x);
}

void fake_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);
    dta[m++] = (L + R) / 2;
    dta[m++] = (L + x) / 2;
    dta[m++] = (x + R) / 2;
}

map <pair <int, int>, vector <int> > id[N];
int ti;

vector <tuple <int, int, int, int> > work[N * 4];

void push(int id, int L, int R, int u, int v, int x, int y, int a, int b) {
    if (u > R || L > v || u > v) return;
    if (u <= L && R <= v) {
        work[id].push_back({x, y, a, b});
        return;
    }
    int mid = L + R >> 1;
    push(id * 2, L, mid, u, v, x, y, a, b);
    push(id * 2 + 1, mid + 1, R, u, v, x, y, a, b);
}

inline 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);

    int l = lower_bound(dta, dta + m, L) - dta;
    int r = lower_bound(dta, dta + m, R) - dta;
    int lr = lower_bound(dta, dta + m, (L + R) / 2) - dta;

    int i = id[t][{L, R}].back();
    id[t][{L, R}].pop_back();
    push(1, 1, q, i, ti - 1, l, lr, 1, - L);
    push(1, 1, q, i, ti - 1, lr + 1, r, -1, R);

    id[t][{L, X}].push_back(ti);
    id[t][{X, R}].push_back(ti);
    s[t].insert(X);
}

inline 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);
    int l = lower_bound(dta, dta + m, L) - dta;
    int r = lower_bound(dta, dta + m, R) - dta;
    int x = lower_bound(dta, dta + m, X) - dta;
    int lx = lower_bound(dta, dta + m, (L + X) / 2) - dta;
    int rx = lower_bound(dta, dta + m, (X + R) / 2) - dta;

    id[t][{L, R}].push_back(ti);
    int i = id[t][{L, X}].back();
    id[t][{L, X}].pop_back();
    push(1, 1, q, i, ti - 1, l, lx, 1, - L);
    push(1, 1, q, i, ti - 1, lx + 1, x, - 1, X);
    i = id[t][{X, R}].back();
    id[t][{X, R}].pop_back();
    push(1, 1, q, i, ti - 1, x, rx, 1, - X);
    push(1, 1, q, i, ti - 1, rx + 1, r, - 1, R);
    cnt += (s[t].size() == 2);
}

struct SegmentTree {
    int st[N * 30];
    int m, ti;
    tuple <int, int, int> old[N * 20];
    SegmentTree() {
        memset(st, - 60, sizeof(st));
    }
    inline void add(int id, int L, int R, int u, int v, int val) {
        if (u > R || L > v) return;
        if (u <= L && R <= v) {
            if (st[id] < val) {
                old[m++] = {ti, id, st[id]};
                st[id] = max(st[id], val);
            }
            return;
        }
        int mid = L + R >> 1;
        add(id * 2, L, mid, u, v, val);
        add(id * 2 + 1, mid + 1, R, u, v, val);
    }
    inline void Set() {
        ++ti;
    }
    inline void rollback() {
        while (m > 0 && get<0>(old[m - 1]) == ti) {
            st[get<1>(old[m - 1])] = get<2>(old[m - 1]);
            --m;
        }
        --ti;
    }
    inline int calc(int id, int L, int R, int i) {
        int ans = st[id];
        if (L == R) return ans;
        int mid = L + R >> 1;
        if (i <= mid) return max(calc(id * 2, L, mid, i), ans);
        else return max(calc(id * 2 + 1, mid + 1, R, i), ans);
    }
} lft, rgt;

int ask[N], wh[N];

inline void solve(int id, int L, int R) {
    lft.Set(), rgt.Set();
    for (auto [u, v, a, b]: work[id]) {
        if (a < 0) lft.add(1, 0, m - 1, u, v, b);
        else rgt.add(1, 0, m - 1, u, v, b);
    }
    if (L == R) {
        if (wh[L]) {
            ans[wh[L]] = max(- dta[ask[L]] + lft.calc(1, 0, m - 1, ask[L]), dta[ask[L]] + rgt.calc(1, 0, m - 1, ask[L]));
        }
    } else {
        int mid = L + R >> 1;
        solve(id * 2, L, mid);
        solve(id * 2 + 1, mid + 1, R);
    }
    lft.rollback(), rgt.rollback();
}

int main() {
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    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;
        dta[m++] = x;
        events.push_back({a, -1, x, t});
        events.push_back({b + 1, 1, x, t});
    }
    sort(events.begin(), events.end());
    for (int i = 1; i <= k; ++i) {
        s[i].insert(0), s[i].insert(M);
        int L = 0, R = M;
        dta[m++] = L, dta[m++] = R, dta[m++] = (L + R) / 2;
    }
    for (auto [_, cmd, x, t]: events) {
        if (cmd == -1) fake_add(t, x);
        else fake_rev(t, x);
    }
    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});
        dta[m++] = x;
    }
    sort(work.begin(), work.end());
    sort(dta, dta + m);
    m = unique(dta, dta + m) - dta;

    for (int i = 1; i <= k; ++i) {
        int L = 0, R = M;
        id[i][{L, R}].push_back(1);
    }
    int i = 0;
    for (auto [y, x, id]: work) {
        ++ti;
        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;
        }
        x = lower_bound(dta, dta + m, x) - dta;
        ask[ti] = x;
        wh[ti] = id;
        if (cnt) ans[id] = -1, ask[ti] = 0, wh[ti] = 0;
    }
    ++ti;
    while (i < events.size()) {
        auto [_, cmd, x, t] = events[i];
        if (cmd == -1) add(t, x);
        else rev(t, x);
        ++i;
    }
    for (int i = 1; i <= k; ++i) {
        int L = 0, R = M;
        int l = 0, r = m - 1;
        int m = lower_bound(dta, dta + m, (L + R) / 2) - dta;
        int _i = id[i][{L, R}].back();
        id[i][{L, R}].pop_back();
        push(1, 1, q, _i, ti - 1, l, m, 1, - L);
        push(1, 1, q, _i, ti - 1, m + 1, r, -1, R);
    }
    solve(1, 1, q);
    for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}

Compilation message

new_home.cpp: In function 'void push(int, int, int, int, int, int, int, int, int)':
new_home.cpp:51:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     int mid = L + R >> 1;
      |               ~~^~~
new_home.cpp: In member function 'void SegmentTree::add(int, int, int, int, int, int)':
new_home.cpp:113:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  113 |         int mid = L + R >> 1;
      |                   ~~^~~
new_home.cpp: In member function 'int SegmentTree::calc(int, int, int, int)':
new_home.cpp:130:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  130 |         int mid = L + R >> 1;
      |                   ~~^~~
new_home.cpp: In function 'void solve(int, int, int)':
new_home.cpp:140:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  140 |     for (auto [u, v, a, b]: work[id]) {
      |               ^
new_home.cpp:149:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  149 |         int mid = L + R >> 1;
      |                   ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:176:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  176 |     for (auto [_, cmd, x, t]: events) {
      |               ^
new_home.cpp:198:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  198 |     for (auto [y, x, id]: work) {
      |               ^
new_home.cpp:200: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]
  200 |         while (i < events.size() && get<0>(events[i]) <= y) {
      |                ~~^~~~~~~~~~~~~~~
new_home.cpp:201:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  201 |             auto [_, cmd, x, t] = events[i];
      |                  ^
new_home.cpp:212:14: 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]
  212 |     while (i < events.size()) {
      |            ~~^~~~~~~~~~~~~~~
new_home.cpp:213:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  213 |         auto [_, cmd, x, t] = events[i];
      |              ^
new_home.cpp:221:40: warning: 'm' may be used uninitialized in this function [-Wmaybe-uninitialized]
  221 |         int m = lower_bound(dta, dta + m, (L + R) / 2) - dta;
      |                                        ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 267972 KB Output is correct
2 Correct 126 ms 268040 KB Output is correct
3 Correct 103 ms 268032 KB Output is correct
4 Correct 120 ms 268000 KB Output is correct
5 Correct 113 ms 268228 KB Output is correct
6 Correct 106 ms 268364 KB Output is correct
7 Correct 107 ms 268616 KB Output is correct
8 Correct 113 ms 268604 KB Output is correct
9 Correct 109 ms 268608 KB Output is correct
10 Correct 115 ms 268512 KB Output is correct
11 Correct 111 ms 268368 KB Output is correct
12 Correct 112 ms 268244 KB Output is correct
13 Correct 104 ms 268236 KB Output is correct
14 Correct 107 ms 268200 KB Output is correct
15 Correct 125 ms 268544 KB Output is correct
16 Correct 110 ms 268492 KB Output is correct
17 Correct 119 ms 268420 KB Output is correct
18 Correct 106 ms 268460 KB Output is correct
19 Correct 116 ms 268540 KB Output is correct
20 Correct 116 ms 268460 KB Output is correct
21 Correct 105 ms 268340 KB Output is correct
22 Correct 117 ms 268708 KB Output is correct
23 Correct 107 ms 268580 KB Output is correct
24 Correct 114 ms 268512 KB Output is correct
25 Correct 110 ms 268428 KB Output is correct
26 Correct 116 ms 268300 KB Output is correct
27 Correct 106 ms 268444 KB Output is correct
28 Correct 108 ms 268236 KB Output is correct
29 Correct 123 ms 268232 KB Output is correct
30 Correct 105 ms 268188 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 267972 KB Output is correct
2 Correct 126 ms 268040 KB Output is correct
3 Correct 103 ms 268032 KB Output is correct
4 Correct 120 ms 268000 KB Output is correct
5 Correct 113 ms 268228 KB Output is correct
6 Correct 106 ms 268364 KB Output is correct
7 Correct 107 ms 268616 KB Output is correct
8 Correct 113 ms 268604 KB Output is correct
9 Correct 109 ms 268608 KB Output is correct
10 Correct 115 ms 268512 KB Output is correct
11 Correct 111 ms 268368 KB Output is correct
12 Correct 112 ms 268244 KB Output is correct
13 Correct 104 ms 268236 KB Output is correct
14 Correct 107 ms 268200 KB Output is correct
15 Correct 125 ms 268544 KB Output is correct
16 Correct 110 ms 268492 KB Output is correct
17 Correct 119 ms 268420 KB Output is correct
18 Correct 106 ms 268460 KB Output is correct
19 Correct 116 ms 268540 KB Output is correct
20 Correct 116 ms 268460 KB Output is correct
21 Correct 105 ms 268340 KB Output is correct
22 Correct 117 ms 268708 KB Output is correct
23 Correct 107 ms 268580 KB Output is correct
24 Correct 114 ms 268512 KB Output is correct
25 Correct 110 ms 268428 KB Output is correct
26 Correct 116 ms 268300 KB Output is correct
27 Correct 106 ms 268444 KB Output is correct
28 Correct 108 ms 268236 KB Output is correct
29 Correct 123 ms 268232 KB Output is correct
30 Correct 105 ms 268188 KB Output is correct
31 Correct 2449 ms 381156 KB Output is correct
32 Correct 229 ms 288336 KB Output is correct
33 Correct 1915 ms 374488 KB Output is correct
34 Correct 2168 ms 375372 KB Output is correct
35 Correct 2171 ms 381260 KB Output is correct
36 Correct 1946 ms 381184 KB Output is correct
37 Correct 1443 ms 360472 KB Output is correct
38 Correct 1283 ms 360044 KB Output is correct
39 Correct 903 ms 336700 KB Output is correct
40 Correct 982 ms 342636 KB Output is correct
41 Correct 1521 ms 353728 KB Output is correct
42 Correct 1537 ms 355204 KB Output is correct
43 Correct 191 ms 280172 KB Output is correct
44 Correct 1468 ms 351712 KB Output is correct
45 Correct 1262 ms 337420 KB Output is correct
46 Correct 869 ms 314140 KB Output is correct
47 Correct 607 ms 313004 KB Output is correct
48 Correct 645 ms 307644 KB Output is correct
49 Correct 767 ms 322600 KB Output is correct
50 Correct 1120 ms 349164 KB Output is correct
51 Correct 758 ms 315776 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2376 ms 428836 KB Output is correct
2 Correct 1749 ms 430852 KB Output is correct
3 Correct 1769 ms 486592 KB Output is correct
4 Correct 2223 ms 448976 KB Output is correct
5 Correct 1630 ms 430424 KB Output is correct
6 Correct 1670 ms 430748 KB Output is correct
7 Correct 1731 ms 486500 KB Output is correct
8 Correct 2181 ms 449268 KB Output is correct
9 Correct 2479 ms 437884 KB Output is correct
10 Correct 2039 ms 432088 KB Output is correct
11 Correct 1543 ms 428624 KB Output is correct
12 Correct 1823 ms 431132 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 267972 KB Output is correct
2 Correct 126 ms 268040 KB Output is correct
3 Correct 103 ms 268032 KB Output is correct
4 Correct 120 ms 268000 KB Output is correct
5 Correct 113 ms 268228 KB Output is correct
6 Correct 106 ms 268364 KB Output is correct
7 Correct 107 ms 268616 KB Output is correct
8 Correct 113 ms 268604 KB Output is correct
9 Correct 109 ms 268608 KB Output is correct
10 Correct 115 ms 268512 KB Output is correct
11 Correct 111 ms 268368 KB Output is correct
12 Correct 112 ms 268244 KB Output is correct
13 Correct 104 ms 268236 KB Output is correct
14 Correct 107 ms 268200 KB Output is correct
15 Correct 125 ms 268544 KB Output is correct
16 Correct 110 ms 268492 KB Output is correct
17 Correct 119 ms 268420 KB Output is correct
18 Correct 106 ms 268460 KB Output is correct
19 Correct 116 ms 268540 KB Output is correct
20 Correct 116 ms 268460 KB Output is correct
21 Correct 105 ms 268340 KB Output is correct
22 Correct 117 ms 268708 KB Output is correct
23 Correct 107 ms 268580 KB Output is correct
24 Correct 114 ms 268512 KB Output is correct
25 Correct 110 ms 268428 KB Output is correct
26 Correct 116 ms 268300 KB Output is correct
27 Correct 106 ms 268444 KB Output is correct
28 Correct 108 ms 268236 KB Output is correct
29 Correct 123 ms 268232 KB Output is correct
30 Correct 105 ms 268188 KB Output is correct
31 Correct 2449 ms 381156 KB Output is correct
32 Correct 229 ms 288336 KB Output is correct
33 Correct 1915 ms 374488 KB Output is correct
34 Correct 2168 ms 375372 KB Output is correct
35 Correct 2171 ms 381260 KB Output is correct
36 Correct 1946 ms 381184 KB Output is correct
37 Correct 1443 ms 360472 KB Output is correct
38 Correct 1283 ms 360044 KB Output is correct
39 Correct 903 ms 336700 KB Output is correct
40 Correct 982 ms 342636 KB Output is correct
41 Correct 1521 ms 353728 KB Output is correct
42 Correct 1537 ms 355204 KB Output is correct
43 Correct 191 ms 280172 KB Output is correct
44 Correct 1468 ms 351712 KB Output is correct
45 Correct 1262 ms 337420 KB Output is correct
46 Correct 869 ms 314140 KB Output is correct
47 Correct 607 ms 313004 KB Output is correct
48 Correct 645 ms 307644 KB Output is correct
49 Correct 767 ms 322600 KB Output is correct
50 Correct 1120 ms 349164 KB Output is correct
51 Correct 758 ms 315776 KB Output is correct
52 Correct 1595 ms 407596 KB Output is correct
53 Correct 1476 ms 402480 KB Output is correct
54 Correct 1982 ms 393100 KB Output is correct
55 Correct 1674 ms 382696 KB Output is correct
56 Correct 1765 ms 389932 KB Output is correct
57 Correct 1565 ms 363764 KB Output is correct
58 Correct 1622 ms 377580 KB Output is correct
59 Correct 1639 ms 387956 KB Output is correct
60 Correct 1582 ms 363900 KB Output is correct
61 Correct 223 ms 309248 KB Output is correct
62 Correct 1634 ms 412600 KB Output is correct
63 Correct 1936 ms 399332 KB Output is correct
64 Correct 2024 ms 395848 KB Output is correct
65 Correct 2045 ms 385308 KB Output is correct
66 Correct 1685 ms 364624 KB Output is correct
67 Correct 667 ms 367756 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 267972 KB Output is correct
2 Correct 126 ms 268040 KB Output is correct
3 Correct 103 ms 268032 KB Output is correct
4 Correct 120 ms 268000 KB Output is correct
5 Correct 113 ms 268228 KB Output is correct
6 Correct 106 ms 268364 KB Output is correct
7 Correct 107 ms 268616 KB Output is correct
8 Correct 113 ms 268604 KB Output is correct
9 Correct 109 ms 268608 KB Output is correct
10 Correct 115 ms 268512 KB Output is correct
11 Correct 111 ms 268368 KB Output is correct
12 Correct 112 ms 268244 KB Output is correct
13 Correct 104 ms 268236 KB Output is correct
14 Correct 107 ms 268200 KB Output is correct
15 Correct 125 ms 268544 KB Output is correct
16 Correct 110 ms 268492 KB Output is correct
17 Correct 119 ms 268420 KB Output is correct
18 Correct 106 ms 268460 KB Output is correct
19 Correct 116 ms 268540 KB Output is correct
20 Correct 116 ms 268460 KB Output is correct
21 Correct 105 ms 268340 KB Output is correct
22 Correct 117 ms 268708 KB Output is correct
23 Correct 107 ms 268580 KB Output is correct
24 Correct 114 ms 268512 KB Output is correct
25 Correct 110 ms 268428 KB Output is correct
26 Correct 116 ms 268300 KB Output is correct
27 Correct 106 ms 268444 KB Output is correct
28 Correct 108 ms 268236 KB Output is correct
29 Correct 123 ms 268232 KB Output is correct
30 Correct 105 ms 268188 KB Output is correct
31 Correct 2449 ms 381156 KB Output is correct
32 Correct 229 ms 288336 KB Output is correct
33 Correct 1915 ms 374488 KB Output is correct
34 Correct 2168 ms 375372 KB Output is correct
35 Correct 2171 ms 381260 KB Output is correct
36 Correct 1946 ms 381184 KB Output is correct
37 Correct 1443 ms 360472 KB Output is correct
38 Correct 1283 ms 360044 KB Output is correct
39 Correct 903 ms 336700 KB Output is correct
40 Correct 982 ms 342636 KB Output is correct
41 Correct 1521 ms 353728 KB Output is correct
42 Correct 1537 ms 355204 KB Output is correct
43 Correct 191 ms 280172 KB Output is correct
44 Correct 1468 ms 351712 KB Output is correct
45 Correct 1262 ms 337420 KB Output is correct
46 Correct 869 ms 314140 KB Output is correct
47 Correct 607 ms 313004 KB Output is correct
48 Correct 645 ms 307644 KB Output is correct
49 Correct 767 ms 322600 KB Output is correct
50 Correct 1120 ms 349164 KB Output is correct
51 Correct 758 ms 315776 KB Output is correct
52 Correct 2376 ms 428836 KB Output is correct
53 Correct 1749 ms 430852 KB Output is correct
54 Correct 1769 ms 486592 KB Output is correct
55 Correct 2223 ms 448976 KB Output is correct
56 Correct 1630 ms 430424 KB Output is correct
57 Correct 1670 ms 430748 KB Output is correct
58 Correct 1731 ms 486500 KB Output is correct
59 Correct 2181 ms 449268 KB Output is correct
60 Correct 2479 ms 437884 KB Output is correct
61 Correct 2039 ms 432088 KB Output is correct
62 Correct 1543 ms 428624 KB Output is correct
63 Correct 1823 ms 431132 KB Output is correct
64 Execution timed out 5097 ms 685444 KB Time limit exceeded
65 Halted 0 ms 0 KB -