#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int inf = 1e8;
struct IT{
struct node{
node *l, *r;
int m;
node(){
l = r = 0;
m = 0;
}
};
multiset<int> r1;
node *rt;
void init(){
rt = new node();
}
void upd(node *v, int tl, int tr, int& p, int& x){
if (tl == tr){
v -> m = x;
return;
}
int tm = (tl + tr) / 2;
if (p <= tm){
if (!(v -> l)) v -> l = new node();
upd(v -> l, tl, tm, p, x);
}
else {
if (!(v -> r)) v -> r = new node();
upd(v -> r, tm + 1, tr, p, x);
}
v -> m = 0;
if (v -> l) v -> m = max(v -> m, v -> l -> m);
if (v -> r) v -> m = max(v -> m, v -> r -> m);
}
void add(int l, int r){
if (l == 1){
r1.insert(r);
return;
}
upd(rt, 1, inf, l, r);
}
void rem(int l, int r){
if (l == 1){
r1.erase(r1.find(r));
return;
}
r = 0;
upd(rt, 1, inf, l, r);
}
int get(node *v, int tl, int tr, int l, int r){
if (l > tr || r < tl) return 0;
if (l <= tl && tr <= r) return v -> m;
int tm = (tl + tr) / 2, out = 0;
if (v -> l) out = max(out, get(v -> l, tl, tm, l, r));
if (v -> r) out = max(out, get(v -> r, tm + 1, tr, l, r));
return out;
}
bool get(int l, int r){
if (!r1.empty() && *prev(r1.end()) >= r) return 1;
return get(rt, 1, inf, 1, l) >= r;
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k, q; cin>>n>>k>>q;
vector<int> x(n + 1), t(n + 1), a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++){
cin>>x[i]>>t[i]>>a[i]>>b[i];
}
vector<int> xq(q + 1), yq(q + 1);
for (int i = 1; i <= q; i++){
cin>>xq[i]>>yq[i];
}
map<int, vector<pii>> mp;
for (int i = 1; i <= n; i++){
mp[a[i]].pb({1, i});
mp[b[i] + 1].pb({2, i});
}
for (int i = 1; i <= q; i++){
mp[yq[i]].pb({i + 2, xq[i]});
}
vector<int> out(q + 1), cnt(k + 1);
multiset<int> st[k + 1];
int df = 0, l, r;
vector<pii> qq;
IT T; T.init();
for (auto [X, V]: mp){
qq.clear();
for (auto [tt, i]: V){
if (tt == 1){
df += !cnt[t[i]];
cnt[t[i]]++;
if (st[t[i]].empty()){
if (1 < x[i]) T.add(1, x[i] - 1);
if (x[i] < inf) T.add(x[i] + 1, inf);
st[t[i]].insert(x[i]);
continue;
}
if (st[t[i]].find(x[i]) != st[t[i]].end()){
st[t[i]].insert(x[i]);
continue;
}
auto it = st[t[i]].upper_bound(x[i]);
if (it == st[t[i]].end()) r = inf;
else r = (*it) - 1;
if (it == st[t[i]].begin()) l = 1;
else l = *prev(it) + 1;
if (l <= r) T.rem(l, r);
if (l < x[i]) T.add(l, x[i] - 1);
if (x[i] < r) T.add(x[i] + 1, r);
st[t[i]].insert(x[i]);
}
else if (tt == 2){
cnt[t[i]]--;
df -= !cnt[t[i]];
if (st[t[i]].count(x[i]) > 1){
st[t[i]].erase(st[t[i]].find(x[i]));
continue;
}
auto it = st[t[i]].find(x[i]);
if (it == st[t[i]].begin()) l = 1;
else l = *prev(it) + 1;
if (it == prev(st[t[i]].end())) r = inf;
else r = *next(it) - 1;
if (l < x[i]) T.rem(l, x[i] - 1);
if (x[i] < r) T.rem(x[i] + 1, r);
if (cnt[t[i]]) T.add(l, r);
st[t[i]].erase(it);
}
else {
qq.pb({tt - 2, i});
}
}
for (auto [ii, x]: qq){
if (df < k){
out[ii] = -1;
continue;
}
auto check = [&](int d){
return T.get(max(1, x - d), min(inf, x + d));
};
int l = 0, r = inf;
while (l + 1 < r){
int m = (l + r) / 2;
if (check(m)){
l = m + 1;
}
else {
r = m;
}
}
if (check(l)) l = r;
out[ii] = l;
}
}
for (int i = 1; i <= q; i++){
cout<<out[i]<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2249 ms |
178292 KB |
Output is correct |
| 2 |
Incorrect |
3597 ms |
170112 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3496 ms |
198260 KB |
Output is correct |
| 2 |
Execution timed out |
5052 ms |
38836 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
