Submission #934889

#TimeUsernameProblemLanguageResultExecution timeMemory
934889IBoryNew Home (APIO18_new_home)C++17
47 / 100
5069 ms564768 KiB
#include <bits/stdc++.h> #define pii pair<int, int> using namespace std; const int SZ = 1 << 20; int P[SZ], S[SZ], X[SZ], ans[SZ]; multiset<int> CX[SZ]; struct Seg { priority_queue<int> T[SZ << 1], E[SZ << 1]; int CL[SZ << 1], CR[SZ << 1]; void Update(int L, int R, int v, bool e, int sL = 1, int sR = SZ, int n = 1) { if (R < sL || sR < L) return; if (L <= sL && sR <= R) { (e ? E[n] : T[n]).push(v); return; } int mid = (sL + sR) >> 1; Update(L, R, v, e, sL, mid, n * 2); Update(L, R, v, e, mid + 1, sR, n * 2 + 1); } int Query(int p) { int sL = 1, sR = SZ, n = 1, ret = -1e9; while (1) { while (!T[n].empty() && !E[n].empty() && T[n].top() == E[n].top()) T[n].pop(), E[n].pop(); if (!T[n].empty()) ret = max(ret, T[n].top()); if (sL == sR) return ret; int mid = (sL + sR) >> 1; if (p <= mid) sR = mid, n = n * 2; else sL = mid + 1, n = n * 2 + 1; } } } T1, T2; vector<int> UX; int Find(int x) { return lower_bound(UX.begin(), UX.end(), x) - UX.begin(); } int main() { ios::sync_with_stdio(0); cin.tie(0); int N, K, Q; cin >> N >> K >> Q; vector<pii> ord; for (int i = 1; i <= N; ++i) { int a, b; cin >> P[i] >> S[i] >> a >> b; P[i] <<= 1; ord.emplace_back(a, i); ord.emplace_back(b + 1, -i); } for (int i = 1; i <= Q; ++i) { int t; cin >> X[i] >> t; X[i] <<= 1; ord.emplace_back(t, SZ + i); } sort(ord.begin(), ord.end()); UX.push_back(-1); UX.push_back(1); UX.push_back(1e8); for (auto [_, id] : ord) { // Line Add if (0 < id && id < SZ) { int pos = P[abs(id)], type = S[abs(id)]; UX.push_back(pos); auto it = CX[type].insert(pos); if (it != CX[type].begin()) { int h = abs(pos - *prev(it)) / 2; UX.push_back(*prev(it) + h); } if (next(it) != CX[type].end()) { int h = abs(pos - *next(it)) / 2; UX.push_back(pos + h); } } // Line Erase else if (id < 0) { int pos = P[abs(id)], type = S[abs(id)]; auto it = CX[type].find(pos); if (it != CX[type].begin() && next(it) != CX[type].end()) { int h = abs(*next(it) - *prev(it)) / 2; UX.push_back(*prev(it) + h); } CX[type].erase(it); } else UX.push_back(X[id - SZ]); } sort(UX.begin(), UX.end()); UX.erase(unique(UX.begin(), UX.end()), UX.end()); memset(ans, 0xf3, sizeof(ans)); int curOpen = 0, L_LIM = 1, R_LIM = UX.size() - 1; for (auto [_, id] : ord) { // Line Add if (0 < id && id < SZ) { int pos = P[abs(id)], type = S[abs(id)], x = Find(pos); if (CX[type].empty()) curOpen++; auto it = CX[type].insert(pos); bool isPrev = it != CX[type].begin(); bool isNext = next(it) != CX[type].end(); // Add T2.Update(isPrev ? Find(pos - (pos - *prev(it)) / 2) : L_LIM, x, pos, 0); T1.Update(x, isNext ? Find(pos + (*next(it) - pos) / 2) : R_LIM, -pos, 0); // Modify if (isNext) { int nx = Find(*next(it)); T2.Update(isPrev ? Find(*next(it) - (*next(it) - *prev(it)) / 2) : L_LIM, nx, *next(it), 1); T2.Update(Find(*next(it) - (*next(it) - pos) / 2), nx, *next(it), 0); } if (isPrev) { int px = Find(*prev(it)); T1.Update(px, isNext ? Find(*prev(it) + (*next(it) - *prev(it)) / 2) : R_LIM, -*prev(it), 1); T1.Update(px, Find(*prev(it) + (pos - *prev(it)) / 2), -*prev(it), 0); } } // Line Erase else if (id < 0) { int pos = P[abs(id)], type = S[abs(id)], x = Find(pos); auto it = CX[type].find(pos); bool isPrev = it != CX[type].begin(); bool isNext = next(it) != CX[type].end(); // Add T2.Update(isPrev ? Find(pos - (pos - *prev(it)) / 2) : L_LIM, x, pos, 1); T1.Update(x, isNext ? Find(pos + (*next(it) - pos) / 2) : R_LIM, -pos, 1); // Modify if (isNext) { int nx = Find(*next(it)); T2.Update(isPrev ? Find(*next(it) - (*next(it) - *prev(it)) / 2) : L_LIM, nx, *next(it), 0); T2.Update(Find(*next(it) - (*next(it) - pos) / 2), nx, *next(it), 1); } if (isPrev) { int px = Find(*prev(it)); T1.Update(px, isNext ? Find(*prev(it) + (*next(it) - *prev(it)) / 2) : R_LIM, -*prev(it), 0); T1.Update(px, Find(*prev(it) + (pos - *prev(it)) / 2), -*prev(it), 1); } CX[type].erase(it); if (CX[type].empty()) curOpen--; } // Query else if (curOpen == K) { id -= SZ; int x = X[id], p = Find(x); int b1 = T1.Query(p); int b2 = T2.Query(p); // cout << "Query: " << p << ' ' << b1 << ' ' << b2 << '\n'; ans[id] = max(x + b1, b2 - x); } } for (int i = 1; i <= Q; ++i) cout << (ans[i] < 0 ? -1 : ans[i] / 2) << '\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...