//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
int n,k,q;
int ans[300001];
set<int> pre[300001];
map<int,int> pre2[300001];
bool vis[3000001];
map<pair<int,pair<int,int>>,int> xx;
map<pair<int,pair<int,int>>,int> xx2;
map<int,int> ss;
map<int,int> ss2;
vector<pair<int,int>> yy;
int ne=0;
int nn;
pair<int,int> solve(int i,int j){
pair<int,int> ac={i,0};
pair<int,int> ac2={j+1,0};
return {lower_bound(yy.begin(),yy.end(),ac)-yy.begin(),lower_bound(yy.begin(),yy.end(),ac2)-yy.begin()-1};
}
priority_queue<pair<int,int>> tree[4*800001];
priority_queue<pair<int,int>> tree2[4*800001];
int kk=1;
//int ans[300001];
void update(int no,int l,int r,int aa,int bb,pair<int,int> x,int st){
/*if(no==0){
cout<<aa<<":"<<bb<<":"<<x.a<<":"<<x.b<<endl;
}*/
if(r<aa or l>bb){
return;
}
if(aa<=l and r<=bb){
//cout<<l<<",,"<<r<<endl;
if(kk){
if(tree[no].size()>100){
pair<int,int> ma=tree[no].top();
tree[no].pop();
tree[no].push(max(ma,x));
ma=tree2[no].top();
tree2[no].pop();
tree2[no].push(max(ma,{-x.a,x.b}));
}
else{
tree[no].push(x);
tree2[no].push({-x.a,x.b});
}
return ;
}
tree[no].push(x);
tree2[no].push({-x.a,x.b});
}
else{
int mid=(l+r)/2;
update(no*2+1,l,mid,aa,bb,x,st);
update(no*2+2,mid+1,r,aa,bb,x,st);
}
}
int query(int no,int l,int r,int i){
int cur=0;
while(tree[no].size()){
if(vis[(tree[no].top()).b]){
tree[no].pop();
}
else{
break;
}
}
while(tree2[no].size()){
if(vis[(tree2[no].top()).b]){
tree2[no].pop();
}
else{
break;
}
}
if(tree[no].size()){
//cout<<l<<","<<r<<","<<yy[i].a<<endl;
cur=max(cur,abs((tree[no].top()).a-yy[i].a));
cur=max(cur,abs(-(tree2[no].top()).a-yy[i].a));
}
if(l<r){
int mid=(l+r)/2;
if(i<=mid){
cur=max(cur,query(no*2+1,l,mid,i));
}
else{
cur=max(cur,query(no*2+2,mid+1,r,i));
}
}
return cur;
}
void add(int i,int aa,int bb,int st){
int mid=(aa+bb)/2;
if(st==1){
xx[{i,{aa,mid}}]=ne;
pair<int,int> ind=solve(aa,mid);
update(0,0,nn-1,ind.a,ind.b,{aa,ne},0);
ne++;
xx[{i,{mid+1,bb}}]=ne;
ind=solve(mid+1,bb);
update(0,0,nn-1,ind.a,ind.b,{bb,ne},1);
ne++;
}
else{
vis[xx[{i,{aa,mid}}]]=1;
vis[xx[{i,{mid+1,bb}}]]=1;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>k>>q;
vector<pair<pair<int,int>,pair<int,int>>> cur;
for(int i=0;i<n;i++){
int x,aa,bb,tt;
cin>>x>>tt>>aa>>bb;
ss[x]++;
tt--;
if(aa!=1 or bb!=1e8){
kk=0;
}
cur.pb({{aa,-1},{x,tt}});
cur.pb({{bb,1},{x,tt}});
pre[tt].insert(x);
}
for(int i=0;i<q;i++){
int x,aa;
cin>>x>>aa;
ss[x]++;
cur.pb({{aa,0},{x,i}});
/*if(kk){
//pre[aa].insert(x);
}*/
}
sort(cur.begin(),cur.end());
int ind5=-1;
ss[-2e8]++;
ss[2e8]++;
for(auto j:ss){
ind5++;
ss2[j.a]=ind5;
yy.pb({j.a,ind5});
}
nn=yy.size();
//sort(cur.begin(),cur.end());
/* for(auto j:yy){
cout<<j.a<<",";
}
cout<<endl;*/
for(int i=0;i<k;i++){
pre[i].insert(-2e8);
pre2[i][-2e8]++;
pre[i].insert(2e8);
pre2[i][2e8]++;
//if(kk==0){
if(kk==0){
add(i,-2e8,2e8,1);
}
// xx[{i,{-2e8,2e8}}]=;
// update(0,0,nn-1,0,nn-1);
}
for(int i=0;i<k;i++){
vector<int> xx;
for(auto j:pre[i]){
xx.pb(j);
}
for(int j=0;j+1<xx.size();j++){
add(i,xx[j],xx[j+1],1);
//cout<<i<<":"<<xx[j]<<":"<<xx[j+1]<<endl;
}
}
for(auto j:cur){
if(j.a.b==-1){
//add
if(kk){
continue;
}
//continue;
if(pre2[j.b.b].find(j.b.a)!=pre2[j.b.b].end()){
if(pre2[j.b.b][j.b.a]>0){
pre2[j.b.b][j.b.a]++;
continue;
}
}
//else{
pre2[j.b.b][j.b.a]++;
int re=*(pre[j.b.b].lower_bound(j.b.a));
auto jj=pre[j.b.b].lower_bound(j.b.a);
jj--;
int le=*jj;
pre[j.b.b].insert(j.b.a);
add(j.b.b,le,re,0);
add(j.b.b,le,j.b.a,1);
add(j.b.b,j.b.a,re,1);
//}
}
else if(j.a.b==1){
//remove
if(kk){
continue;
}
//continue;
pre2[j.b.b][j.b.a]--;
if(pre2[j.b.b][j.b.a]==0){
pre[j.b.b].erase(j.b.a);
int re=*(pre[j.b.b].lower_bound(j.b.a));
auto jj=pre[j.b.b].lower_bound(j.b.a);
jj--;
int le=*jj;
add(j.b.b,le,j.b.a,0);
add(j.b.b,j.b.a,re,0);
add(j.b.b,le,re,1);
}
}
else{
//cout<<j.b.a<<":"<<j.b.b<<endl;
int ans2=query(0,0,nn-1,ss2[j.b.a]);
if(ans2>1e8){
ans2=-1;
}
ans[j.b.b]=ans2;
}
}
for(int i=0;i<q;i++){
cout<<ans[i]<<endl;
}
/*for(int i=0;i<cur.size();i++){
cur[i].b.a=ss2[cur[i].b.a];
}*/
return 0;
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:194:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
194 | for(int j=0;j+1<xx.size();j++){
| ~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
115 ms |
228940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
115 ms |
228940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5050 ms |
491508 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5073 ms |
580088 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
115 ms |
228940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
115 ms |
228940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
