| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1029445 |
2024-07-20T21:59:06 Z |
erray |
New Home (APIO18_new_home) |
C++17 |
|
482 ms |
49336 KB |
// author: erray
#include <bits/stdc++.h>
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) void(37)
#endif
using namespace std;
template<typename T>
T PT(T* x) {
const static T n = T{};
return (x == NULL ? n : *x);
}
constexpr int inf = int(3e8);
struct node {
node* L = NULL, *R = NULL;
int mx = -inf;
multiset<int> acts;
void add(int x) {
acts.insert(x);
mx = *acts.rbegin();
}
void rem(int x) {
acts.erase(acts.find(x));
mx = (acts.empty() ? -inf : *acts.rbegin());
}
void pull() {
mx = max(PT(L).mx, PT(R).mx);
}
void branch() {
if (L == NULL) L = new node{};
if (R == NULL) R = new node{};
}
};
int get(node* v, int l, int r, int ll, int rr) {
if (l >= ll && rr >= r) {
return v->mx;
}
int mid = (l + r) >> 1;
int res = -inf;
if (ll <= mid && v->L != NULL) {
res = max(res, get(v->L, l, mid, ll, rr));
}
if (mid < rr && v->R != NULL) {
res = max(res, get(v->R, mid + 1, r, ll, rr));
}
return res;
}
struct SegTree {
void modify(node* v, int l, int r, int p, int x, int t) {
if (l == r) {
if (t) {
v->add(x);
} else {
v->rem(x);
}
return;
}
v->branch();
int mid = (l + r) >> 1;
if (p <= mid) {
modify(v->L, l, mid, p, x, t);
} else {
modify(v->R, mid + 1, r, p, x, t);
}
v->pull();
}
int get(node* v, int l, int r, int ll, int rr) {
if (l >= ll && rr >= r) {
return v->mx;
}
int mid = (l + r) >> 1;
int res = -inf;
if (ll <= mid && v->L != NULL) {
res = max(res, get(v->L, l, mid, ll, rr));
}
if (mid < rr && v->R != NULL) {
res = max(res, get(v->R, mid + 1, r, ll, rr));
}
return res;
}
int mn, mx;
node* root;
SegTree(int _mn, int _mx) : mn(_mn), mx(_mx) {
root = new node{};
}
void modify(int p, int x, int t) {
modify(root, mn, mx, p, x, t);
}
int get(int ll, int rr) {
return get(root, mn, mx, ll, rr);
}
};
constexpr int POS = int(1e8);
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int N, K, Q;
cin >> N >> K >> Q;
vector<int> X(N), T(N), A(N), B(N);
for (int i = 0; i < N; ++i) {
cin >> X[i] >> T[i] >> A[i] >> B[i];
--T[i];
}
vector<int> L(Q), Y(Q);
for (int i = 0; i < Q; ++i) {
cin >> L[i] >> Y[i];
}
vector<array<int, 2>> events;
for (int i = 0; i < N; ++i) {
events.push_back({A[i], i});
events.push_back({B[i] + 1, ~i});
}
for (int i = 0; i < Q; ++i) {
events.push_back({Y[i], i + N});
}
debug(events);
sort(events.begin(), events.end());
SegTree pref(1, POS), suf(1, POS);
vector<map<int, int>> acts(K);
auto Updates = [&](int t, int x) -> vector<array<int, 3>> {
debug(t, x);
if (acts[t].empty()) {
return {};
}
vector<array<int, 3>> res;
auto it = acts[t].lower_bound(x);
vector<array<int, 2>> regulars;
if (it != acts[t].end() && it->first == x) {
if (next(it) == acts[t].end()) {
res.push_back({t, POS, POS - x});
} else {
regulars.push_back({it->first, next(it)->first});
}
if (it == acts[t].begin()) {
res.push_back({t, 1, x - 1});
} else {
regulars.push_back({prev(it)->first, it->first});
}
} else {
if (it == acts[t].end()) {
res.push_back({t, POS, POS - prev(it)->first});
} else if (it == acts[t].begin()) {
res.push_back({t, 1, it->first - 1});
} else {
regulars.push_back({prev(it)->first, it->first});
}
}
for (auto[l, r] : regulars) {
int dist = (r - l) / 2, mid = (l + r) / 2;
if ((l + r) % 2 == 1) {
res.push_back({t, mid, dist});
res.push_back({t, mid + 1, dist});
} else {
res.push_back({t, mid, dist});
}
}
return res;
};
vector<int> cords;
auto Rem = [&](vector<array<int, 3>> a) {
for (auto[t, x, v] : a) {
//pref.modify(x, v + x, 0);
//suf.modify(x, v - x, 0);
}
};
auto Add = [&](vector<array<int, 3>> a) {
for (auto[t, x, v] : a) {
//pref.modify(x, v + x, 1);
//suf.modify(x, v - x, 1);
}
};
vector<int> ans(Q);
int exists = 0;
for (auto[foo, t] : events) {
debug(foo, t);
if (t < 0) {
t = ~t;
if (--acts[T[t]][X[t]] == 0) {
Rem(Updates(T[t], X[t]));
acts[T[t]].erase(X[t]);
Add(Updates(T[t], X[t]));
}
exists -= (acts[T[t]].empty());
} else if (t < N) {
exists += (acts[T[t]].empty());
if (!acts[T[t]].count(X[t])) {
Rem(Updates(T[t], X[t]));
acts[T[t]][X[t]] = 0;
Add(Updates(T[t], X[t]));
}
acts[T[t]][X[t]]++;
} else {
t -= N;
ans[t] = (exists == K ? max(pref.get(1, L[t]) - L[t], suf.get(L[t], POS) + L[t]) : -1);
}
}
for (int i = 0; i < Q; ++i) {
cout << ans[i] << '\n';
}
}
Compilation message
new_home.cpp: In lambda function:
new_home.cpp:170:14: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
170 | for (auto[t, x, v] : a) {
| ^~~~~~~~~
new_home.cpp: In lambda function:
new_home.cpp:176:14: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
176 | for (auto[t, x, v] : a) {
| ^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
352 ms |
49336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
482 ms |
46004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
