#pragma GCC optimize("Ofast")
#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], td[maxn][2];
int pc[inf];
int lb(int x){return pc[x-1];}
int ub(int x){return pc[x];}
int etype[maxn];
int tot;
set<pair<int, int>> lmao[maxn];
priority_queue<pair<int, 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;
if(!ty)st[id][ty].push({-k.f, {k.s, td[k.s][ty]}});
else st[id][ty].push({k.f, {k.s, td[k.s][ty]}});
}
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);
}
}
int _query(int l, int r, int k, int id){
//cout << l << " " << r << " " << id << endl;
if(tot != K)return -1;
int re = 0;
while(!st[id][0].empty()){
auto x = st[id][0].top();
if(td[x.s.f][0] != x.s.s)st[id][0].pop();
else break;
}
while(!st[id][1].empty()){
auto x = st[id][1].top();
if(td[x.s.f][1] != x.s.s)st[id][1].pop();
else break;
}
if(!st[id][0].empty())re = max(re, posq[k] + st[id][0].top().f);
if(!st[id][1].empty())re = max(re, st[id][1].top().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, lb(L[id]), 1);
}
void add(int ql, int qr, pair<int, int> k, int ty){
_add(0, posq.size()-1, lb(ql), ub(qr)-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(1, 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;
td[id][ty]++;
}
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());
for(auto v: posq)pc[v]++;
for(int i = 1; i < inf; i++)pc[i]+=pc[i-1];
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});
assert(it != lmao[T[id]].end());
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";
}
Compilation message
new_home.cpp: In function 'void s_add(std::set<std::pair<int, int> >::iterator, int)':
new_home.cpp:20:26: warning: array subscript 100000005 is above array bounds of 'int [100000005]' [-Warray-bounds]
20 | int ub(int x){return pc[x];}
| ~~~~^
new_home.cpp:17:5: note: while referencing 'pc'
17 | int pc[inf];
| ^~
new_home.cpp: In function 'void s_add(std::set<std::pair<int, int> >::iterator, int)':
new_home.cpp:20:26: warning: array subscript 100000005 is above array bounds of 'int [100000005]' [-Warray-bounds]
20 | int ub(int x){return pc[x];}
| ~~~~^
new_home.cpp:17:5: note: while referencing 'pc'
17 | int pc[inf];
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
299 ms |
480972 KB |
Output is correct |
| 2 |
Correct |
300 ms |
480916 KB |
Output is correct |
| 3 |
Correct |
309 ms |
481052 KB |
Output is correct |
| 4 |
Incorrect |
312 ms |
480964 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
299 ms |
480972 KB |
Output is correct |
| 2 |
Correct |
300 ms |
480916 KB |
Output is correct |
| 3 |
Correct |
309 ms |
481052 KB |
Output is correct |
| 4 |
Incorrect |
312 ms |
480964 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4343 ms |
749300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5115 ms |
794820 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
299 ms |
480972 KB |
Output is correct |
| 2 |
Correct |
300 ms |
480916 KB |
Output is correct |
| 3 |
Correct |
309 ms |
481052 KB |
Output is correct |
| 4 |
Incorrect |
312 ms |
480964 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
299 ms |
480972 KB |
Output is correct |
| 2 |
Correct |
300 ms |
480916 KB |
Output is correct |
| 3 |
Correct |
309 ms |
481052 KB |
Output is correct |
| 4 |
Incorrect |
312 ms |
480964 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
