oj.uz

Submission #560407

# Submission time Handle Problem Language Result Execution time Memory
560407 2022-05-11T11:07:35 Z hoanghq2004 New Home (APIO18_new_home) C++14
12 / 100
 5000 ms 639712 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 * 10];

vector <int> dta;

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, dta[x] + *(--st[id].rgt.end()));
    if (st[id].lft.size()) ans = max(ans, - dta[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 fake_add(int t, int x) {
    int L = *(--s[t].upper_bound(x));
    int R = *s[t].upper_bound(x);
    dta.push_back(L);
    dta.push_back(R);
    dta.push_back(x);
    dta.push_back((L + R) / 2);
    dta.push_back((L + x) / 2);
    dta.push_back((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.push_back(L);
    dta.push_back(R);
    dta.push_back(x);
    dta.push_back((L + R) / 2);
    dta.push_back((L + x) / 2);
    dta.push_back((x + R) / 2);
}

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.begin(), dta.end(), L) - dta.begin();
    int r = lower_bound(dta.begin(), dta.end(), R) - dta.begin();
    int x = lower_bound(dta.begin(), dta.end(), X) - dta.begin();
    int lr = lower_bound(dta.begin(), dta.end(), (L + R) / 2) - dta.begin();
    int lx = lower_bound(dta.begin(), dta.end(), (L + X) / 2) - dta.begin();
    int rx = lower_bound(dta.begin(), dta.end(), (X + R) / 2) - dta.begin();

    upd(1, 0, dta.size() - 1, l, lr, 1, - L, -1);
    upd(1, 0, dta.size() - 1, lr + 1, r, - 1, R, -1);
    upd(1, 0, dta.size() - 1, l, lx, 1, - L, 1);
    upd(1, 0, dta.size() - 1, lx + 1, x, - 1, X, 1);

    upd(1, 0, dta.size() - 1, x, rx, 1, - X, 1);
    upd(1, 0, dta.size() - 1, rx + 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);
    int l = lower_bound(dta.begin(), dta.end(), L) - dta.begin();
    int r = lower_bound(dta.begin(), dta.end(), R) - dta.begin();
    int x = lower_bound(dta.begin(), dta.end(), X) - dta.begin();
    int lr = lower_bound(dta.begin(), dta.end(), (L + R) / 2) - dta.begin();
    int lx = lower_bound(dta.begin(), dta.end(), (L + X) / 2) - dta.begin();
    int rx = lower_bound(dta.begin(), dta.end(), (X + R) / 2) - dta.begin();

    upd(1, 0, dta.size() - 1, l, lr, 1, - L, 1);
    upd(1, 0, dta.size() - 1, lr + 1, r, - 1, R, 1);

    upd(1, 0, dta.size() - 1, l, lx, 1, - L, -1);
    upd(1, 0, dta.size() - 1, lx + 1, x, - 1, X, -1);

    upd(1, 0, dta.size() - 1, x, rx, 1, - X, -1);
    upd(1, 0, dta.size() - 1, rx + 1, r, - 1, R, -1);
    cnt += (s[t].size() == 2);
}

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;
        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.push_back(L), dta.push_back(R);
        dta.push_back((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.push_back(x);
    }
    sort(work.begin(), work.end());
    sort(dta.begin(), dta.end());
    dta.erase(unique(dta.begin(), dta.end()), dta.end());
    for (int i = 1; i <= k; ++i) {
        int L = 0, R = M;
        int l = 0, r = dta.size() - 1;
        int m = lower_bound(dta.begin(), dta.end(), (L + R) / 2) - dta.begin();
        upd(1, 0, dta.size() - 1, l, m, 1, - L, 1);
        upd(1, 0, dta.size() - 1, m + 1, r, - 1, R, 1);
    }

    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;
        }
        x = lower_bound(dta.begin(), dta.end(), x) - dta.begin();
        if (cnt) ans[id] = -1;
        else solve(1, 0, dta.size() - 1, 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:154:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  154 |     for (auto [_, cmd, x, t]: events) {
      |               ^
new_home.cpp:179:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  179 |     for (auto [y, x, id]: work) {
      |               ^
new_home.cpp:180: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]
  180 |         while (i < events.size() && get<0>(events[i]) <= y) {
      |                ~~^~~~~~~~~~~~~~~
new_home.cpp:181:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  181 |             auto [_, cmd, x, t] = events[i];
      |                  ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 319660 KB Output is correct
2 Correct 145 ms 319692 KB Output is correct
3 Correct 146 ms 319640 KB Output is correct
4 Correct 154 ms 319580 KB Output is correct
5 Correct 158 ms 319688 KB Output is correct
6 Correct 143 ms 319832 KB Output is correct
7 Correct 159 ms 320092 KB Output is correct
8 Correct 159 ms 320028 KB Output is correct
9 Correct 147 ms 320340 KB Output is correct
10 Correct 153 ms 319948 KB Output is correct
11 Correct 154 ms 319748 KB Output is correct
12 Correct 145 ms 319756 KB Output is correct
13 Correct 164 ms 319796 KB Output is correct
14 Correct 165 ms 319744 KB Output is correct
15 Correct 148 ms 319948 KB Output is correct
16 Correct 150 ms 319996 KB Output is correct
17 Correct 155 ms 319880 KB Output is correct
18 Correct 161 ms 320124 KB Output is correct
19 Correct 145 ms 320012 KB Output is correct
20 Correct 155 ms 319856 KB Output is correct
21 Correct 146 ms 319916 KB Output is correct
22 Correct 147 ms 320432 KB Output is correct
23 Correct 146 ms 320232 KB Output is correct
24 Correct 155 ms 319952 KB Output is correct
25 Correct 154 ms 319824 KB Output is correct
26 Correct 147 ms 319808 KB Output is correct
27 Correct 147 ms 319712 KB Output is correct
28 Correct 154 ms 319792 KB Output is correct
29 Correct 179 ms 319692 KB Output is correct
30 Correct 142 ms 319760 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 319660 KB Output is correct
2 Correct 145 ms 319692 KB Output is correct
3 Correct 146 ms 319640 KB Output is correct
4 Correct 154 ms 319580 KB Output is correct
5 Correct 158 ms 319688 KB Output is correct
6 Correct 143 ms 319832 KB Output is correct
7 Correct 159 ms 320092 KB Output is correct
8 Correct 159 ms 320028 KB Output is correct
9 Correct 147 ms 320340 KB Output is correct
10 Correct 153 ms 319948 KB Output is correct
11 Correct 154 ms 319748 KB Output is correct
12 Correct 145 ms 319756 KB Output is correct
13 Correct 164 ms 319796 KB Output is correct
14 Correct 165 ms 319744 KB Output is correct
15 Correct 148 ms 319948 KB Output is correct
16 Correct 150 ms 319996 KB Output is correct
17 Correct 155 ms 319880 KB Output is correct
18 Correct 161 ms 320124 KB Output is correct
19 Correct 145 ms 320012 KB Output is correct
20 Correct 155 ms 319856 KB Output is correct
21 Correct 146 ms 319916 KB Output is correct
22 Correct 147 ms 320432 KB Output is correct
23 Correct 146 ms 320232 KB Output is correct
24 Correct 155 ms 319952 KB Output is correct
25 Correct 154 ms 319824 KB Output is correct
26 Correct 147 ms 319808 KB Output is correct
27 Correct 147 ms 319712 KB Output is correct
28 Correct 154 ms 319792 KB Output is correct
29 Correct 179 ms 319692 KB Output is correct
30 Correct 142 ms 319760 KB Output is correct
31 Correct 3446 ms 380496 KB Output is correct
32 Correct 327 ms 328764 KB Output is correct
33 Correct 1744 ms 338564 KB Output is correct
34 Correct 3236 ms 349592 KB Output is correct
35 Correct 2617 ms 371680 KB Output is correct
36 Correct 1514 ms 352932 KB Output is correct
37 Correct 1162 ms 329272 KB Output is correct
38 Correct 894 ms 328220 KB Output is correct
39 Correct 715 ms 327048 KB Output is correct
40 Correct 700 ms 327124 KB Output is correct
41 Correct 1714 ms 327472 KB Output is correct
42 Correct 1801 ms 327608 KB Output is correct
43 Correct 264 ms 332336 KB Output is correct
44 Correct 1628 ms 327296 KB Output is correct
45 Correct 1323 ms 327272 KB Output is correct
46 Correct 1089 ms 327260 KB Output is correct
47 Correct 774 ms 326836 KB Output is correct
48 Correct 696 ms 326836 KB Output is correct
49 Correct 902 ms 326988 KB Output is correct
50 Correct 1322 ms 327020 KB Output is correct
51 Correct 853 ms 326972 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 319660 KB Output is correct
2 Correct 145 ms 319692 KB Output is correct
3 Correct 146 ms 319640 KB Output is correct
4 Correct 154 ms 319580 KB Output is correct
5 Correct 158 ms 319688 KB Output is correct
6 Correct 143 ms 319832 KB Output is correct
7 Correct 159 ms 320092 KB Output is correct
8 Correct 159 ms 320028 KB Output is correct
9 Correct 147 ms 320340 KB Output is correct
10 Correct 153 ms 319948 KB Output is correct
11 Correct 154 ms 319748 KB Output is correct
12 Correct 145 ms 319756 KB Output is correct
13 Correct 164 ms 319796 KB Output is correct
14 Correct 165 ms 319744 KB Output is correct
15 Correct 148 ms 319948 KB Output is correct
16 Correct 150 ms 319996 KB Output is correct
17 Correct 155 ms 319880 KB Output is correct
18 Correct 161 ms 320124 KB Output is correct
19 Correct 145 ms 320012 KB Output is correct
20 Correct 155 ms 319856 KB Output is correct
21 Correct 146 ms 319916 KB Output is correct
22 Correct 147 ms 320432 KB Output is correct
23 Correct 146 ms 320232 KB Output is correct
24 Correct 155 ms 319952 KB Output is correct
25 Correct 154 ms 319824 KB Output is correct
26 Correct 147 ms 319808 KB Output is correct
27 Correct 147 ms 319712 KB Output is correct
28 Correct 154 ms 319792 KB Output is correct
29 Correct 179 ms 319692 KB Output is correct
30 Correct 142 ms 319760 KB Output is correct
31 Correct 3446 ms 380496 KB Output is correct
32 Correct 327 ms 328764 KB Output is correct
33 Correct 1744 ms 338564 KB Output is correct
34 Correct 3236 ms 349592 KB Output is correct
35 Correct 2617 ms 371680 KB Output is correct
36 Correct 1514 ms 352932 KB Output is correct
37 Correct 1162 ms 329272 KB Output is correct
38 Correct 894 ms 328220 KB Output is correct
39 Correct 715 ms 327048 KB Output is correct
40 Correct 700 ms 327124 KB Output is correct
41 Correct 1714 ms 327472 KB Output is correct
42 Correct 1801 ms 327608 KB Output is correct
43 Correct 264 ms 332336 KB Output is correct
44 Correct 1628 ms 327296 KB Output is correct
45 Correct 1323 ms 327272 KB Output is correct
46 Correct 1089 ms 327260 KB Output is correct
47 Correct 774 ms 326836 KB Output is correct
48 Correct 696 ms 326836 KB Output is correct
49 Correct 902 ms 326988 KB Output is correct
50 Correct 1322 ms 327020 KB Output is correct
51 Correct 853 ms 326972 KB Output is correct
52 Correct 3840 ms 475296 KB Output is correct
53 Correct 3868 ms 417248 KB Output is correct
54 Correct 4810 ms 428524 KB Output is correct
55 Correct 3083 ms 379440 KB Output is correct
56 Correct 3428 ms 403772 KB Output is correct
57 Correct 2868 ms 344984 KB Output is correct
58 Correct 3636 ms 379596 KB Output is correct
59 Correct 3490 ms 403732 KB Output is correct
60 Correct 3051 ms 345260 KB Output is correct
61 Correct 337 ms 351864 KB Output is correct
62 Correct 3823 ms 475380 KB Output is correct
63 Correct 4657 ms 429140 KB Output is correct
64 Execution timed out 5012 ms 404700 KB Time limit exceeded
65 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 319660 KB Output is correct
2 Correct 145 ms 319692 KB Output is correct
3 Correct 146 ms 319640 KB Output is correct
4 Correct 154 ms 319580 KB Output is correct
5 Correct 158 ms 319688 KB Output is correct
6 Correct 143 ms 319832 KB Output is correct
7 Correct 159 ms 320092 KB Output is correct
8 Correct 159 ms 320028 KB Output is correct
9 Correct 147 ms 320340 KB Output is correct
10 Correct 153 ms 319948 KB Output is correct
11 Correct 154 ms 319748 KB Output is correct
12 Correct 145 ms 319756 KB Output is correct
13 Correct 164 ms 319796 KB Output is correct
14 Correct 165 ms 319744 KB Output is correct
15 Correct 148 ms 319948 KB Output is correct
16 Correct 150 ms 319996 KB Output is correct
17 Correct 155 ms 319880 KB Output is correct
18 Correct 161 ms 320124 KB Output is correct
19 Correct 145 ms 320012 KB Output is correct
20 Correct 155 ms 319856 KB Output is correct
21 Correct 146 ms 319916 KB Output is correct
22 Correct 147 ms 320432 KB Output is correct
23 Correct 146 ms 320232 KB Output is correct
24 Correct 155 ms 319952 KB Output is correct
25 Correct 154 ms 319824 KB Output is correct
26 Correct 147 ms 319808 KB Output is correct
27 Correct 147 ms 319712 KB Output is correct
28 Correct 154 ms 319792 KB Output is correct
29 Correct 179 ms 319692 KB Output is correct
30 Correct 142 ms 319760 KB Output is correct
31 Correct 3446 ms 380496 KB Output is correct
32 Correct 327 ms 328764 KB Output is correct
33 Correct 1744 ms 338564 KB Output is correct
34 Correct 3236 ms 349592 KB Output is correct
35 Correct 2617 ms 371680 KB Output is correct
36 Correct 1514 ms 352932 KB Output is correct
37 Correct 1162 ms 329272 KB Output is correct
38 Correct 894 ms 328220 KB Output is correct
39 Correct 715 ms 327048 KB Output is correct
40 Correct 700 ms 327124 KB Output is correct
41 Correct 1714 ms 327472 KB Output is correct
42 Correct 1801 ms 327608 KB Output is correct
43 Correct 264 ms 332336 KB Output is correct
44 Correct 1628 ms 327296 KB Output is correct
45 Correct 1323 ms 327272 KB Output is correct
46 Correct 1089 ms 327260 KB Output is correct
47 Correct 774 ms 326836 KB Output is correct
48 Correct 696 ms 326836 KB Output is correct
49 Correct 902 ms 326988 KB Output is correct
50 Correct 1322 ms 327020 KB Output is correct
51 Correct 853 ms 326972 KB Output is correct
52 Execution timed out 5069 ms 639712 KB Time limit exceeded
53 Halted 0 ms 0 KB -