//#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'
llo n,k,q;
llo ans[300001];
set<llo> pre[300001];
map<llo,llo> pre2[300001];
bool vis[3000001];
map<pair<llo,pair<llo,llo>>,llo> xx;
map<pair<llo,pair<llo,llo>>,llo> xx2;
map<llo,llo> ss;
map<llo,llo> ss2;
vector<pair<llo,llo>> yy;
llo ne=0;
llo nn;
pair<llo,llo> solve(llo i,llo j){
pair<llo,llo> ac={i,0};
pair<llo,llo> ac2={j+1,0};
return {lower_bound(yy.begin(),yy.end(),ac)-yy.begin(),lower_bound(yy.begin(),yy.end(),ac2)-yy.begin()-1};
}
set<pair<llo,llo>> tree[4*800001];
//llo ans[300001];
void update(llo no,llo l,llo r,llo aa,llo bb,pair<llo,llo> x,llo 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;
tree[no].insert(x);
}
else{
llo 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);
}
}
llo query(llo no,llo l,llo r,llo i){
llo cur=0;
while(tree[no].size()){
if(vis[(*(tree[no].begin())).b]){
tree[no].erase(tree[no].begin());
}
else{
break;
}
}
while(tree[no].size()){
auto j=tree[no].end();
j--;
if(vis[(*j).b]){
tree[no].erase(j);
}
else{
break;
}
}
if(tree[no].size()){
//cout<<l<<","<<r<<","<<yy[i].a<<endl;
cur=max(cur,abs((*tree[no].begin()).a-yy[i].a));
auto jj=tree[no].end();
jj--;
cur=max(cur,abs((*jj).a-yy[i].a));
}
if(l<r){
llo 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(llo i,llo aa,llo bb,llo st){
llo mid=(aa+bb)/2;
if(st==1){
xx[{i,{aa,mid}}]=ne;
pair<llo,llo> 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<llo,llo>,pair<llo,llo>>> cur;
for(llo i=0;i<n;i++){
llo x,aa,bb,tt;
cin>>x>>tt>>aa>>bb;
ss[x]++;
tt--;
cur.pb({{aa,-1},{x,tt}});
cur.pb({{bb,1},{x,tt}});
}
for(llo i=0;i<q;i++){
llo x,aa;
cin>>x>>aa;
ss[x]++;
cur.pb({{aa,0},{x,i}});
}
sort(cur.begin(),cur.end());
llo ind5=-1;
ss[-1e9]++;
ss[1e9]++;
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(llo i=0;i<k;i++){
pre[i].insert(-1e9);
pre2[i][-1e9]++;
pre[i].insert(1e9);
pre2[i][1e9]++;
add(i,-1e9,1e9,1);
// xx[{i,{-1e9,1e9}}]=;
// update(0,0,nn-1,0,nn-1);
}
for(auto j:cur){
if(j.a.b==-1){
//add
//continue;
if(pre2[j.b.b].find(j.b.a)!=pre2[j.b.b].end()){
pre2[j.b.b][j.b.a]++;
}
else{
pre2[j.b.b][j.b.a]++;
llo re=*(pre[j.b.b].lower_bound(j.b.a));
auto jj=pre[j.b.b].lower_bound(j.b.a);
jj--;
llo 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
//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);
llo re=*(pre[j.b.b].lower_bound(j.b.a));
auto jj=pre[j.b.b].lower_bound(j.b.a);
jj--;
llo 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;
llo ans2=query(0,0,nn-1,ss2[j.b.a]);
if(ans2>1e8){
ans2=-1;
}
ans[j.b.b]=ans2;
}
}
for(llo i=0;i<q;i++){
cout<<ans[i]<<endl;
}
/*for(llo i=0;i<cur.size();i++){
cur[i].b.a=ss2[cur[i].b.a];
}*/
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
178812 KB |
Output is correct |
| 2 |
Correct |
107 ms |
178808 KB |
Output is correct |
| 3 |
Correct |
107 ms |
178780 KB |
Output is correct |
| 4 |
Correct |
108 ms |
178752 KB |
Output is correct |
| 5 |
Incorrect |
109 ms |
178836 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
178812 KB |
Output is correct |
| 2 |
Correct |
107 ms |
178808 KB |
Output is correct |
| 3 |
Correct |
107 ms |
178780 KB |
Output is correct |
| 4 |
Correct |
108 ms |
178752 KB |
Output is correct |
| 5 |
Incorrect |
109 ms |
178836 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5079 ms |
823132 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5121 ms |
855556 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
178812 KB |
Output is correct |
| 2 |
Correct |
107 ms |
178808 KB |
Output is correct |
| 3 |
Correct |
107 ms |
178780 KB |
Output is correct |
| 4 |
Correct |
108 ms |
178752 KB |
Output is correct |
| 5 |
Incorrect |
109 ms |
178836 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
178812 KB |
Output is correct |
| 2 |
Correct |
107 ms |
178808 KB |
Output is correct |
| 3 |
Correct |
107 ms |
178780 KB |
Output is correct |
| 4 |
Correct |
108 ms |
178752 KB |
Output is correct |
| 5 |
Incorrect |
109 ms |
178836 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
