#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef long long ll;
const int inf = 1e8+5;
const int maxn = 3e5+5;
vector<int> posq;
int n, K, q;
int X[maxn], T[maxn], A[maxn], B[maxn], L[maxn], Y[maxn], ans[maxn];
int etype[maxn];
int tot;
set<pair<int, int>> lmao[maxn];
set<pair<int, int>> st[4*maxn][2];
void _add(int l, int r, int ql, int qr, pair<int, int> k, int ty, int id){
//cout << ql << " " << qr << " " << ty << endl;
if(ql > qr)return;
if(l > qr || ql > r)return;
else if(ql <= l && r <= qr){
//cout << "a " << id << " " << ty << endl;
st[id][ty].insert(k);
}
else {
int mid = (l+r)>>1;
_add(l, mid, ql, qr, k, ty, id<<1);
_add(mid+1, r, ql, qr, k, ty, id<<1|1);
}
}
void _rmv(int l, int r, int ql, int qr, pair<int, int> k, int ty, int id){
if(ql > qr)return;
if(l > qr || ql > r)return;
else if(ql <= l && r <= qr)st[id][ty].erase(k);
else {
int mid = (l+r)>>1;
_rmv(l, mid, ql, qr, k, ty, id<<1);
_rmv(mid+1, r, ql, qr, k, ty, id<<1|1);
}
}
int _query(int l, int r, int k, int id){
if(tot != K)return -1;
int re = 0;
if(!st[id][0].empty())re = max(re, posq[k] - st[id][0].begin()->f);
if(!st[id][1].empty())re = max(re, st[id][1].rbegin()->f - posq[k]);
if(l == r)return re;
int mid = (l+r)>>1;
if(k <= mid)re = max(re, _query(l, mid, k, id<<1));
else re = max(re, _query(mid+1, r, k, id<<1|1));
return re;
}
int query(int id){
return _query(0, posq.size()-1, lower_bound(posq.begin(), posq.end(), L[id]) - posq.begin(), 1);
}
void add(int ql, int qr, pair<int, int> k, int ty){
_add(0, posq.size()-1, lower_bound(posq.begin(), posq.end(), ql) - posq.begin(), upper_bound(posq.begin(), posq.end(), qr) - posq.begin()-1, k, ty, 1);
}
void rmv(int ql, int qr, pair<int, int> k, int ty){
_rmv(0, posq.size()-1, lower_bound(posq.begin(), posq.end(), ql) - posq.begin(), upper_bound(posq.begin(), posq.end(), qr) - posq.begin()-1, k, ty, 1);
}
void s_add(set<pair<int, int>>::iterator it, int ty){
int id = it->s;
if(ty == 0){
if(next(it) == lmao[T[id]].end())add(X[id]+1, inf, {X[id], id}, 0);
else add(X[id]+1, (next(it)->f+X[id])/2, {X[id], id}, 0);
}
else{
if(it == lmao[T[id]].begin())add(0, X[id], {X[id], id}, 1);
else add((prev(it)->f + X[id])/2+1, X[id], {X[id], id}, 1);
}
}
void s_rmv(set<pair<int, int>>::iterator it, int ty){
int id = it->s;
if(ty == 0){
if(next(it) == lmao[T[id]].end())rmv(X[id]+1, inf, {X[id], id}, 0);
else rmv(X[id]+1, (next(it)->f+X[id])/2, {X[id], id}, 0);
}
else{
if(it == lmao[T[id]].begin())rmv(0, X[id], {X[id], id}, 1);
else rmv((prev(it)->f + X[id])/2+1, X[id], {X[id], id}, 1);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> K >> q;
vector<pair<int, pair<int, int>>> ev;
for(int i = 0; i < n; i++){
cin >> X[i] >> T[i] >> A[i] >> B[i];
ev.push_back({A[i], {0, i}});
ev.push_back({B[i]+1, {1, i}});
}
for(int i = 0; i < q; i++){
cin >> L[i] >> Y[i];
ev.push_back({Y[i], {2, i}});
posq.push_back(L[i]);
}
sort(posq.begin(), posq.end());
posq.erase(unique(posq.begin(), posq.end()), posq.end());
sort(ev.begin(), ev.end());
for(auto v: ev){
//cout << v.s.f << " " << v.s.s << endl;
int id = v.s.s;
if(v.s.f == 0){
auto it = lmao[T[id]].lower_bound({X[id], id});
if(it != lmao[T[id]].end())s_rmv(it, 1);
if(it != lmao[T[id]].begin())s_rmv(prev(it), 0);
it = lmao[T[id]].insert({X[id], id}).f;
s_add(it, 0);
s_add(it, 1);
if(it != lmao[T[id]].begin())s_add(prev(it), 0);
if(next(it) != lmao[T[id]].end())s_add(next(it), 1);
tot += etype[T[id]]++==0;
}
else if(v.s.f == 1){
auto it = lmao[T[id]].find({X[id], id});
s_rmv(it, 0);
s_rmv(it, 1);
if(it != lmao[T[id]].begin())s_rmv(prev(it), 0);
if(next(it) != lmao[T[id]].end())s_rmv(next(it), 1);
lmao[T[id]].erase(it);
it = lmao[T[id]].lower_bound({X[id], id});
if(it != lmao[T[id]].end())s_add(it, 1);
if(it != lmao[T[id]].begin())s_add(prev(it), 0);
tot += --etype[T[id]]==0;
}
else ans[id] = query(id);
}
for(int i = 0; i < q; i++)cout << ans[i] << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
127160 KB |
Output is correct |
| 2 |
Correct |
69 ms |
127164 KB |
Output is correct |
| 3 |
Correct |
68 ms |
127156 KB |
Output is correct |
| 4 |
Correct |
70 ms |
127056 KB |
Output is correct |
| 5 |
Correct |
56 ms |
127180 KB |
Output is correct |
| 6 |
Incorrect |
60 ms |
127272 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
127160 KB |
Output is correct |
| 2 |
Correct |
69 ms |
127164 KB |
Output is correct |
| 3 |
Correct |
68 ms |
127156 KB |
Output is correct |
| 4 |
Correct |
70 ms |
127056 KB |
Output is correct |
| 5 |
Correct |
56 ms |
127180 KB |
Output is correct |
| 6 |
Incorrect |
60 ms |
127272 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5060 ms |
379468 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5068 ms |
309984 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
127160 KB |
Output is correct |
| 2 |
Correct |
69 ms |
127164 KB |
Output is correct |
| 3 |
Correct |
68 ms |
127156 KB |
Output is correct |
| 4 |
Correct |
70 ms |
127056 KB |
Output is correct |
| 5 |
Correct |
56 ms |
127180 KB |
Output is correct |
| 6 |
Incorrect |
60 ms |
127272 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
127160 KB |
Output is correct |
| 2 |
Correct |
69 ms |
127164 KB |
Output is correct |
| 3 |
Correct |
68 ms |
127156 KB |
Output is correct |
| 4 |
Correct |
70 ms |
127056 KB |
Output is correct |
| 5 |
Correct |
56 ms |
127180 KB |
Output is correct |
| 6 |
Incorrect |
60 ms |
127272 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
