Submission #560561

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
560561	2022-05-11T17:06:58 Z	hoanghq2004	New Home (APIO18_new_home)	C++14	0 / 100	5000 ms	922696 KB

new_home

#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];

inline 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 proc(int L, int R, int u, int v, int a, int b) {
    u = lower_bound(dta, dta + m, u) - dta;
    v = upper_bound(dta, dta + m, v) - dta - 1;
    push(1, 1, q, L, R, u, v, 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 i = id[t][{L, R}].back();
    id[t][{L, R}].pop_back();
    proc(i, ti - 1, L, (L + R) / 2, 1, -L);
    proc(i, ti - 1, (L + R) / 2 + 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);

    id[t][{L, R}].push_back(ti);
    int i = id[t][{L, X}].back();
    id[t][{L, X}].pop_back();
    proc(i, ti - 1, L, (L + X) / 2, 1, -L);
    proc(i, ti - 1, (L + X) / 2 + 1, X, -1, X);

    i = id[t][{X, R}].back();
    id[t][{X, R}].pop_back();
    proc(i, ti - 1, X, (X + R) / 2, 1, -X);
    proc(i, ti - 1, (X + R) / 2 + 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] = 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);
    }
    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;
//    cout << m << '\n';
//    exit(0);
    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:111:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  111 |         int mid = L + R >> 1;
      |                   ~~^~~
new_home.cpp: In member function 'int SegmentTree::calc(int, int, int, int)':
new_home.cpp:128:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  128 |         int mid = L + R >> 1;
      |                   ~~^~~
new_home.cpp: In function 'void solve(int, int, int)':
new_home.cpp:138:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  138 |     for (auto [u, v, a, b]: work[id]) {
      |               ^
new_home.cpp:147:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  147 |         int mid = L + R >> 1;
      |                   ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:172:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  172 |     for (auto [_, cmd, x, t]: events) {
      |               ^
new_home.cpp:195:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  195 |     for (auto [y, x, id]: work) {
      |               ^
new_home.cpp:197: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]
  197 |         while (i < events.size() && get<0>(events[i]) <= y) {
      |                ~~^~~~~~~~~~~~~~~
new_home.cpp:198:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  198 |             auto [_, cmd, x, t] = events[i];
      |                  ^
new_home.cpp:209: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]
  209 |     while (i < events.size()) {
      |            ~~^~~~~~~~~~~~~~~
new_home.cpp:210:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  210 |         auto [_, cmd, x, t] = events[i];
      |              ^
new_home.cpp:218:40: warning: 'm' may be used uninitialized in this function [-Wmaybe-uninitialized]
  218 |         int m = lower_bound(dta, dta + m, (L + R) / 2) - dta;
      |                                        ^

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	125 ms	267976 KB	Output is correct
2	Runtime error	432 ms	543304 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	125 ms	267976 KB	Output is correct
2	Runtime error	432 ms	543304 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2581 ms	428184 KB	Output is correct
2	Correct	1947 ms	418384 KB	Output is correct
3	Correct	1907 ms	469192 KB	Output is correct
4	Correct	2484 ms	434320 KB	Output is correct
5	Correct	1791 ms	417792 KB	Output is correct
6	Correct	1869 ms	418352 KB	Output is correct
7	Runtime error	1810 ms	922696 KB	Execution killed with signal 11
8	Halted	0 ms	0 KB	-