Submission #160947

#TimeUsernameProblemLanguageResultExecution timeMemory
160947MinnakhmetovNew Home (APIO18_new_home)C++14
0 / 100
5116 ms336944 KiB
#include <bits/stdc++.h> #define ll long long #define all(aaa) aaa.begin(), aaa.end() using namespace std; struct E { int p, t, x, y; }; const int N = 3e5 + 5, INF = 1e9, MAX = 1e8; int n, q, k, cc, cq; int ans[N], ord[N], loc[N], num[N]; vector<int> vx; multiset<int> occ[N]; map<pair<int, int>, vector<int>> mp; vector<pair<int, int>> t[N * 4]; struct ST { vector<int> t[N * 4]; void upd(int l, int r, int x, int v, int L, int R) { if (l > r) return; if (l == L && r == R) { t[v].push_back(max(t[v].back(), x)); } else { int m = (L + R) >> 1; upd(l, min(m, r), x, v * 2, L, m); upd(max(m + 1, l), r, x, v * 2 + 1, m + 1, R); } } void del(int l, int r, int v, int L, int R) { if (l > r) return; if (l == L && r == R) { t[v].pop_back(); } else { int m = (L + R) >> 1; del(l, min(m, r), v * 2, L, m); del(max(m + 1, l), r, v * 2 + 1, m + 1, R); } } int que(int x, int v, int L, int R, int ans = -INF) { ans = max(ans, t[v].back()); if (L == R) return ans; int m = (L + R) >> 1; if (x <= m) return que(x, v * 2, L, m, ans); return que(x, v * 2 + 1, m + 1, R, ans); } void clear() { for (int i = 0; i < N * 4; i++) { t[i] = {-INF}; } } } segt; void upd(int l, int r, pair<int, int> p, int v, int L, int R) { if (l > r) return; if (L == l && R == r) { t[v].push_back(p); } else { int m = (L + R) >> 1; upd(l, min(m, r), p, v * 2, L, m); upd(max(m + 1, l), r, p, v * 2 + 1, m + 1, R); } } void startSeg(int x, int y) { mp[{x, y}].push_back(cq); } void endSeg(int x, int y) { auto p = make_pair(x, y); upd(mp[{x, y}].back(), cq - 1, p, 1, 0, q - 1); mp[{x, y}].pop_back(); } void updBeg(int x, bool add) { if (add) startSeg(0, x); else endSeg(0, x); } void updBetween(int x, int y, bool add) { if (x == y) return; int m1 = upper_bound(all(vx), (x + y) >> 1) - vx.begin(); if (add) startSeg(m1, y); else endSeg(m1, y); } void calcAns(int v, int L, int R) { for (auto &p : t[v]) { segt.upd(p.first, cc - 1, p.second, 1, 0, cc - 1); } if (L == R) { ans[num[L]] = max(ans[num[L]], segt.que(loc[L], 1, 0, cc - 1) - vx[loc[L]]); } else { int m = (L + R) >> 1; calcAns(v * 2, L, m); calcAns(v * 2 + 1, m + 1, R); } for (auto &p : t[v]) { segt.del(p.first, cc - 1, 1, 0, cc - 1); } } void solve(vector<E> evs) { vx.clear(); mp.clear(); for (int i = 0; i < N; i++) { occ[i].clear(); t[i].clear(); } for (E e : evs) { if (e.t == 2) vx.push_back(e.x); } sort(all(vx)); vx.erase(unique(all(vx)), vx.end()); cc = vx.size(); cq = 0; for (E e : evs) { // cout << e.p << " " << e.t << " " << e.x << " " << e.y << "\n"; if (e.t == 0) { auto it = occ[e.y].upper_bound(e.x); if (!occ[e.y].empty()) { if (it != occ[e.y].begin() && it != occ[e.y].end()) { updBetween(*prev(it), *it, false); } if (it == occ[e.y].begin()) { updBeg(*it, false); } } it = occ[e.y].insert(e.x); if (it == occ[e.y].begin()) updBeg(*it, true); else updBetween(*prev(it), *it, true); if (next(it) != occ[e.y].end()) updBetween(*it, *next(it), true); } else if (e.t == 1) { auto it = occ[e.y].find(e.x); if (it == occ[e.y].begin()) updBeg(*it, false); else updBetween(*prev(it), *it, false); if (next(it) != occ[e.y].end()) updBetween(*it, *next(it), false); if (it != occ[e.y].begin() && next(it) != occ[e.y].end()) updBetween(*prev(it), *next(it), true); if (it == occ[e.y].begin() && occ[e.y].size() > 1) updBeg(*next(it), true); occ[e.y].erase(it); } else { loc[cq] = lower_bound(all(vx), e.x) - vx.begin(); num[cq] = e.y; cq++; } } segt.clear(); calcAns(1, 0, q - 1); } signed main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cin >> n >> k >> q; vector<E> evs; for (int i = 0; i < n; i++) { int x, t, a, b; cin >> x >> t >> a >> b; t--; evs.push_back({a, 0, x, t}); evs.push_back({b + 1, 1, x, t}); vx.push_back(x); } for (int i = 0; i < k; i++) { evs.push_back({1, 0, INF, i}); evs.push_back({MAX, 1, INF, i}); } for (int i = 0; i < q; i++) { int x, y; cin >> x >> y; evs.push_back({y, 2, x, i}); } sort(all(evs), [](const E &a, const E &b) { return a.p == b.p ? a.t < b.t : a.p < b.p; }); solve(evs); for (E &e : evs) e.x = INF - e.x; solve(evs); for (int i = 0; i < q; i++) { if (ans[i] < INF / 2) { cout << ans[i] << "\n"; } else { cout << "-1\n"; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...