oj.uz

Submission #560523

# Submission time Handle Problem Language Result Execution time Memory
560523 2022-05-11T15:24:34 Z hoanghq2004 New Home (APIO18_new_home) C++14
5 / 100
 5000 ms 897680 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;
vector <int> dta;

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

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

struct __ {
    int x, y, u, v, a, b;
};
vector <__> _;
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);
}

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

    int i = id[t][{L, R}].back();
    id[t][{L, R}].pop_back();
    _.push_back({i, ti - 1, l, lr, 1, - L});
    _.push_back({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);
}

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

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

struct SegmentTree {
    vector <int> st[N * 20];
    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) {
            st[id].push_back((st[id].empty() ? val : max(val, st[id].back())));
            return;
        }
        int mid = L + R >> 1;
        add(id * 2, L, mid, u, v, val);
        add(id * 2 + 1, mid + 1, R, u, v, val);
    }
    void rollback(int id, int L, int R, int u, int v) {
        if (u > R || L > v) return;
        if (u <= L && R <= v) {
            st[id].pop_back();
            return;
        }
        int mid = L + R >> 1;
        rollback(id * 2, L, mid, u, v);
        rollback(id * 2 + 1, mid + 1, R, u, v);
    }
    int get(int id, int L, int R, int i) {
        int ans = (st[id].empty() ? - 1e9 : st[id].back());
        if (L == R) return ans;
        int mid = L + R >> 1;
        if (i <= mid) return max(get(id * 2, L, mid, i), ans);
        else return max(get(id * 2 + 1, mid + 1, R, i), ans);
    }
} lft, rgt;

int ask[N], wh[N];

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

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;
        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.begin(), dta.end(), x) - dta.begin();
        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 = dta.size() - 1;
        int m = lower_bound(dta.begin(), dta.end(), (L + R) / 2) - dta.begin();
        int _i = id[i][{L, R}].back();
        id[i][{L, R}].pop_back();
        _.push_back({_i, ti - 1, l, m, 1, -L});
        _.push_back({_i, ti - 1, m + 1, r, -1, L});
    }
    for (auto [L, R, u, v, a, b]: _)
        push(1, 1, ti, L, R, u, v, a, b);
    solve(1, 1, ti);
    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:61:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     int mid = L + R >> 1;
      |               ~~^~~
new_home.cpp: In function 'void rev(int, int)':
new_home.cpp:91:9: warning: unused variable 'lr' [-Wunused-variable]
   91 |     int lr = lower_bound(dta.begin(), dta.end(), (L + R) / 2) - dta.begin();
      |         ^~
new_home.cpp: In member function 'void SegmentTree::add(int, int, int, int, int, int)':
new_home.cpp:115:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  115 |         int mid = L + R >> 1;
      |                   ~~^~~
new_home.cpp: In member function 'void SegmentTree::rollback(int, int, int, int, int)':
new_home.cpp:125:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  125 |         int mid = L + R >> 1;
      |                   ~~^~~
new_home.cpp: In member function 'int SegmentTree::get(int, int, int, int)':
new_home.cpp:132:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  132 |         int mid = L + R >> 1;
      |                   ~~^~~
new_home.cpp: In function 'void solve(int, int, int)':
new_home.cpp:141:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  141 |     for (auto [u, v, a, b]: work[id]) {
      |               ^
new_home.cpp:150:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  150 |         int mid = L + R >> 1;
      |                   ~~^~~
new_home.cpp:155:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  155 |     for (auto [u, v, a, b]: work[id]) {
      |               ^
new_home.cpp: In function 'int main()':
new_home.cpp:181:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  181 |     for (auto [_, cmd, x, t]: events) {
      |               ^
new_home.cpp:202:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  202 |     for (auto [y, x, id]: work) {
      |               ^
new_home.cpp:204: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]
  204 |         while (i < events.size() && get<0>(events[i]) <= y) {
      |                ~~^~~~~~~~~~~~~~~
new_home.cpp:205:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  205 |             auto [_, cmd, x, t] = events[i];
      |                  ^
new_home.cpp:216: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]
  216 |     while (i < events.size()) {
      |            ~~^~~~~~~~~~~~~~~
new_home.cpp:217:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  217 |         auto [_, cmd, x, t] = events[i];
      |              ^
new_home.cpp:231:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  231 |     for (auto [L, R, u, v, a, b]: _)
      |               ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 338516 KB Output is correct
2 Correct 153 ms 338516 KB Output is correct
3 Correct 160 ms 338408 KB Output is correct
4 Correct 173 ms 338460 KB Output is correct
5 Correct 153 ms 338784 KB Output is correct
6 Correct 159 ms 339004 KB Output is correct
7 Correct 166 ms 339332 KB Output is correct
8 Correct 200 ms 339244 KB Output is correct
9 Correct 173 ms 339404 KB Output is correct
10 Correct 177 ms 339108 KB Output is correct
11 Correct 168 ms 338960 KB Output is correct
12 Correct 167 ms 338924 KB Output is correct
13 Correct 159 ms 338852 KB Output is correct
14 Correct 155 ms 338780 KB Output is correct
15 Correct 176 ms 339148 KB Output is correct
16 Correct 162 ms 339200 KB Output is correct
17 Correct 184 ms 339092 KB Output is correct
18 Correct 165 ms 339204 KB Output is correct
19 Correct 165 ms 339280 KB Output is correct
20 Correct 177 ms 339076 KB Output is correct
21 Correct 166 ms 339084 KB Output is correct
22 Correct 167 ms 339492 KB Output is correct
23 Correct 187 ms 339276 KB Output is correct
24 Correct 183 ms 339236 KB Output is correct
25 Correct 164 ms 339112 KB Output is correct
26 Correct 158 ms 338980 KB Output is correct
27 Correct 173 ms 338996 KB Output is correct
28 Correct 178 ms 338996 KB Output is correct
29 Correct 171 ms 339016 KB Output is correct
30 Correct 157 ms 338752 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 338516 KB Output is correct
2 Correct 153 ms 338516 KB Output is correct
3 Correct 160 ms 338408 KB Output is correct
4 Correct 173 ms 338460 KB Output is correct
5 Correct 153 ms 338784 KB Output is correct
6 Correct 159 ms 339004 KB Output is correct
7 Correct 166 ms 339332 KB Output is correct
8 Correct 200 ms 339244 KB Output is correct
9 Correct 173 ms 339404 KB Output is correct
10 Correct 177 ms 339108 KB Output is correct
11 Correct 168 ms 338960 KB Output is correct
12 Correct 167 ms 338924 KB Output is correct
13 Correct 159 ms 338852 KB Output is correct
14 Correct 155 ms 338780 KB Output is correct
15 Correct 176 ms 339148 KB Output is correct
16 Correct 162 ms 339200 KB Output is correct
17 Correct 184 ms 339092 KB Output is correct
18 Correct 165 ms 339204 KB Output is correct
19 Correct 165 ms 339280 KB Output is correct
20 Correct 177 ms 339076 KB Output is correct
21 Correct 166 ms 339084 KB Output is correct
22 Correct 167 ms 339492 KB Output is correct
23 Correct 187 ms 339276 KB Output is correct
24 Correct 183 ms 339236 KB Output is correct
25 Correct 164 ms 339112 KB Output is correct
26 Correct 158 ms 338980 KB Output is correct
27 Correct 173 ms 338996 KB Output is correct
28 Correct 178 ms 338996 KB Output is correct
29 Correct 171 ms 339016 KB Output is correct
30 Correct 157 ms 338752 KB Output is correct
31 Execution timed out 5073 ms 483044 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5058 ms 867356 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 5114 ms 897680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 338516 KB Output is correct
2 Correct 153 ms 338516 KB Output is correct
3 Correct 160 ms 338408 KB Output is correct
4 Correct 173 ms 338460 KB Output is correct
5 Correct 153 ms 338784 KB Output is correct
6 Correct 159 ms 339004 KB Output is correct
7 Correct 166 ms 339332 KB Output is correct
8 Correct 200 ms 339244 KB Output is correct
9 Correct 173 ms 339404 KB Output is correct
10 Correct 177 ms 339108 KB Output is correct
11 Correct 168 ms 338960 KB Output is correct
12 Correct 167 ms 338924 KB Output is correct
13 Correct 159 ms 338852 KB Output is correct
14 Correct 155 ms 338780 KB Output is correct
15 Correct 176 ms 339148 KB Output is correct
16 Correct 162 ms 339200 KB Output is correct
17 Correct 184 ms 339092 KB Output is correct
18 Correct 165 ms 339204 KB Output is correct
19 Correct 165 ms 339280 KB Output is correct
20 Correct 177 ms 339076 KB Output is correct
21 Correct 166 ms 339084 KB Output is correct
22 Correct 167 ms 339492 KB Output is correct
23 Correct 187 ms 339276 KB Output is correct
24 Correct 183 ms 339236 KB Output is correct
25 Correct 164 ms 339112 KB Output is correct
26 Correct 158 ms 338980 KB Output is correct
27 Correct 173 ms 338996 KB Output is correct
28 Correct 178 ms 338996 KB Output is correct
29 Correct 171 ms 339016 KB Output is correct
30 Correct 157 ms 338752 KB Output is correct
31 Execution timed out 5073 ms 483044 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 338516 KB Output is correct
2 Correct 153 ms 338516 KB Output is correct
3 Correct 160 ms 338408 KB Output is correct
4 Correct 173 ms 338460 KB Output is correct
5 Correct 153 ms 338784 KB Output is correct
6 Correct 159 ms 339004 KB Output is correct
7 Correct 166 ms 339332 KB Output is correct
8 Correct 200 ms 339244 KB Output is correct
9 Correct 173 ms 339404 KB Output is correct
10 Correct 177 ms 339108 KB Output is correct
11 Correct 168 ms 338960 KB Output is correct
12 Correct 167 ms 338924 KB Output is correct
13 Correct 159 ms 338852 KB Output is correct
14 Correct 155 ms 338780 KB Output is correct
15 Correct 176 ms 339148 KB Output is correct
16 Correct 162 ms 339200 KB Output is correct
17 Correct 184 ms 339092 KB Output is correct
18 Correct 165 ms 339204 KB Output is correct
19 Correct 165 ms 339280 KB Output is correct
20 Correct 177 ms 339076 KB Output is correct
21 Correct 166 ms 339084 KB Output is correct
22 Correct 167 ms 339492 KB Output is correct
23 Correct 187 ms 339276 KB Output is correct
24 Correct 183 ms 339236 KB Output is correct
25 Correct 164 ms 339112 KB Output is correct
26 Correct 158 ms 338980 KB Output is correct
27 Correct 173 ms 338996 KB Output is correct
28 Correct 178 ms 338996 KB Output is correct
29 Correct 171 ms 339016 KB Output is correct
30 Correct 157 ms 338752 KB Output is correct
31 Execution timed out 5073 ms 483044 KB Time limit exceeded
32 Halted 0 ms 0 KB -