| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 934797 |
2024-02-28T02:47:10 Z |
IBory |
New Home (APIO18_new_home) |
C++17 |
|
930 ms |
1048576 KB |
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int MAX = 300003, LIM = 18000000, SZ = 1 << 27;
int P[MAX], S[MAX], X[MAX], ans[MAX];
multiset<int> CX[MAX];
struct Seg {
priority_queue<int> T[LIM], E[LIM];
int CL[LIM], CR[LIM], CN;
void Clear() {
for (int i = 0; i < LIM; ++i) {
while (!T[i].empty()) T[i].pop();
while (!E[i].empty()) E[i].pop();
}
memset(CL, -1, sizeof(CL));
memset(CR, -1, sizeof(CR));
CN = 1;
}
void Update(int L, int R, int v, bool e, int sL = 1, int sR = SZ, int n = 1) {
if (n == 1) {
if (v < 0 && R != SZ) R = L + (R - L) / 2;
else if (v > 0 && L != 1) L = R - (R - L) / 2;
}
if (R < sL || sR < L) return;
if (L <= sL && sR <= R) {
(e ? E[n] : T[n]).push(v);
return;
}
int mid = (sL + sR) >> 1;
if (CL[n] == -1) CL[n] = ++CN;
if (CR[n] == -1) CR[n] = ++CN;
Update(L, R, v, e, sL, mid, CL[n]);
Update(L, R, v, e, mid + 1, sR, CR[n]);
}
int Query(int p) {
int sL = 1, sR = SZ, n = 1, ret = -1e9;
while (1) {
if (n == -1) break;
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) break;
int mid = (sL + sR) >> 1;
if (p <= mid) sR = mid, n = CL[n];
else sL = mid + 1, n = CR[n];
}
// cout << p << ' ' << ret << '\n';
return ret;
}
} T;
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;
ord.emplace_back(a, i);
ord.emplace_back(b + 1, -i);
}
for (int i = 1; i <= Q; ++i) {
int t;
cin >> X[i] >> t;
ord.emplace_back(t, MAX + i);
}
// Process 1: a = 1
int curOpen = 0;
memset(ans, 0xf3, sizeof(ans));
sort(ord.begin(), ord.end());
for (auto [_, id] : ord) {
// Insert / Modify Line
if (0 < id && id < MAX) {
// cout << "Insert " << id << '\n';
int cur = P[id], type = S[id];
if (CX[type].empty()) curOpen++;
auto it = CX[type].insert(cur);
int L = (it == CX[type].begin() ? -1 : *prev(it));
int R = (next(it) == CX[type].end() ? SZ : *next(it) - 1);
if (L != -1) {
T.Update(L, R, -L, 1);
T.Update(L, cur - 1, -L, 0);
}
T.Update(cur, R, -cur, 0);
}
// Erase / Modify Line
else if (id < 0) {
// cout << "Erase " << -id << '\n';
id = abs(id);
int cur = P[id], type = S[id];
auto it = CX[type].find(cur);
int L = (it == CX[type].begin() ? -1 : *prev(it));
int R = (next(it) == CX[type].end() ? SZ : *next(it) - 1);
if (L != -1) {
T.Update(L, R, -L, 0);
T.Update(L, cur - 1, -L, 1);
}
T.Update(cur, R, -cur, 1);
CX[type].erase(it);
if (CX[type].empty()) curOpen--;
}
// Query
else {
id -= MAX;
// cout << "Query " << id << '\n';
if (curOpen == K) ans[id] = max(ans[id], X[id] + T.Query(X[id]));
}
}
// cout << "-------------\n";
// Process 2: a = -1
T.Clear();
for (auto [_, id] : ord) {
// Insert / Modify Line
if (0 < id && id < MAX) {
int cur = P[id], type = S[id];
if (CX[type].empty()) curOpen++;
auto it = CX[type].insert(cur);
int L = (it == CX[type].begin() ? 1 : *prev(it) + 1);
int R = (next(it) == CX[type].end() ? -1 : *next(it));
if (R != -1) {
T.Update(L, R, R, 1);
T.Update(cur + 1, R, R, 0);
}
T.Update(L, cur, cur, 0);
}
// Erase / Modify Line
else if (id < 0) {
id = abs(id);
int cur = P[id], type = S[id];
auto it = CX[type].find(cur);
int L = (it == CX[type].begin() ? 1 : *prev(it) + 1);
int R = (next(it) == CX[type].end() ? -1 : *next(it));
if (R != -1) {
T.Update(L, R, R, 0);
T.Update(cur + 1, R, R, 1);
}
T.Update(L, cur, cur, 1);
CX[type].erase(it);
if (CX[type].empty()) curOpen--;
}
// Query
else {
id -= MAX;
// cout << "Query " << id << '\n';
if (curOpen == K) ans[id] = max(ans[id], -X[id] + T.Query(X[id]));
}
}
for (int i = 1; i <= Q; ++i) cout << (ans[i] < 0 ? -1 : ans[i]) << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
930 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
930 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
372 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
328 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
930 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
930 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
