Submission #560311

#	Time	Username	Problem	Language	Result	Execution time	Memory
560311		hoanghq2004	New Home (APIO18_new_home)	C++14	12 / 100	4438 ms	1048576 KiB

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;

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 / 2 + *(--st[id].rgt.end()));
    if (st[id].lft.size()) ans = max(ans, - x / 2 + *(--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, - 4e8, 4e8, L * 2, L + R, 1, - L, -1);
    upd(1, - 4e8, 4e8, L + R, R * 2, -1, R, -1);
    upd(1, - 4e8, 4e8, L * 2, L + x, 1, - L, 1);
    upd(1, - 4e8, 4e8, L + x, x * 2, -1, x, 1);
    upd(1, - 4e8, 4e8, x * 2, x + R, 1, - x, 1);
    upd(1, - 4e8, 4e8, x + R, R * 2, -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, - 4e8, 4e8, L * 2, L + R, 1, - L, 1);
    upd(1, - 4e8, 4e8, L + R, R * 2, -1, R, 1);
    upd(1, - 4e8, 4e8, L * 2, L + x, 1, - L, -1);
    upd(1, - 4e8, 4e8, L + x, x * 2, -1, x, -1);
    upd(1, - 4e8, 4e8, x * 2, x + R, 1, - x, -1);
    upd(1, - 4e8, 4e8, x + R, R * 2, -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;
        events.push_back({a, -1, x, t});
        events.push_back({b + 1, 1, x, t});
    }
    for (int i = 1; i <= k; ++i) {
        int L = - 2e8, R = 2e8;
        s[i].insert(L), s[i].insert(R);
        upd(1, - 4e8, 4e8, L * 2, L + R, 1, - L, 1);
        upd(1, - 4e8, 4e8, L + R, R * 2, - 1, R, 1);
    }
    cnt = k;
    vector <tuple <int, int, int> > work;
    for (int i = 1; i <= q; ++i) {
        int x, y;
        cin >> x >> y;
        work.push_back({y, x * 2, 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, - 4e8, 4e8, x, ans[id]);
    }
    for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}

Compilation message (stderr)

new_home.cpp: In function 'void upd(int, int, int, int, int, int, int, int)':
new_home.cpp:43:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int mid = L + R >> 1;
      |               ~~^~~
new_home.cpp: In function 'void solve(int, int, int, int, int&)':
new_home.cpp:58:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |     int mid = L + R >> 1;
      |               ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:118:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |     for (auto [y, x, id]: work) {
      |               ^
new_home.cpp:119: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]
  119 |         while (i < events.size() && get<0>(events[i]) <= y) {
      |                ~~^~~~~~~~~~~~~~~
new_home.cpp:120:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |             auto [_, cmd, x, t] = events[i];
      |                  ^

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20