| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 560306 | hoanghq2004 | New Home (APIO18_new_home) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 * 100];
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;
go(st[id].lhs), go(st[id].rhs);
upd(st[id].lhs, L, mid, u, v, a, b, mode);
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';
}