#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib>
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
//#define int long long
//#define double long double
const int mxn=1e6,inf=1e9,minf=-1e9,Mxn=1e8+1;
int mx;
bitset<Mxn>del;
set<int>pos[mxn+10];
int cnt=0;
int curid=0;
vector<int>comp;
int n,k,q;
priority_queue<pii,vector<pii>,greater<pii>>huh;
struct seg{
priority_queue<pii>v[2*mxn+10];
priority_queue<pii>v2[2*mxn+10];
//v=-val v2=+val
//keep max
//val id
void update(int l,int r,pii val,int type){//lazy on top, 1=right
//cout<<l<<" "<<r<<'\n';
if(r<l)assert(0);
l=max(l,0);
r=max(r,l);
//cout<<l<<" "<<r<<" "<<val.f<<"PPP\n";
for(l+=mx,r+=mx;l<=r;l>>=1,r>>=1){
if(l&1){
if(type)v[l].push(val);
else v2[l].push(val);
l++;
}
if(!(r&1)){
if(type)v[r].push(val);
else v2[r].push(val);
r--;
}
}
}
pii qry(int pos){
int g=comp.size()-1;
pos=min(pos,g);
pii ans={minf,minf};
for(pos+=mx;pos>=0;pos>>=1){
while(!v[pos].empty()&&del[v[pos].top().s])v[pos].pop();
if(v[pos].size())ans.f=max(ans.f,v[pos].top().f);
while(!v2[pos].empty()&&del[v2[pos].top().s])v2[pos].pop();
if(v2[pos].size())ans.s=max(ans.s,v2[pos].top().f);
if(pos==0)break;
}
return ans;
}
}seg;
int rangeleft[mxn+10],rangeright[mxn+10];
int rangeidleft[mxn+10],rangeidright[mxn+10];
int idpos[mxn+10],idposincomp[mxn+10];
int tmp;
void add(int x,int t){
//cout<<"PPP\n";
//x =pos in comp;
auto it=pos[t].insert(x).f;
if(it!=pos[t].begin()){
it--;
tmp=(*it);
int val=ceil((idpos[tmp]+idpos[x])*1.0/2);
//find mid point
auto it2=lb(all(comp),val)-comp.begin();
if(it2==comp.size())assert(0);
//find mid point in comp
if(it2<=idposincomp[tmp])it2=idposincomp[tmp]+1;
rangeright[tmp]=it2-1;
if(it2>idposincomp[x])rangeleft[x]=idposincomp[x];
else rangeleft[x]=it2;
del[rangeidright[tmp]]=1;
rangeidright[tmp]=++curid;
rangeidleft[x]=++curid;
seg.update(idposincomp[tmp],rangeright[tmp],{-idpos[tmp],rangeidright[tmp]},1);
it++;
}
else{
rangeleft[x]=0;
rangeidleft[x]=++curid;
}
it++;
if(it!=pos[t].end()){
tmp=(*it);
int val=ceil((idpos[tmp]+idpos[x])*1.0/2);
auto it2=lb(all(comp),val)-comp.begin();
if(it2==comp.size())assert(0);
if(it2<=idposincomp[x])it2=idposincomp[x]+1;
rangeright[x]=it2-1;
rangeleft[tmp]=it2;
if(it2>idposincomp[tmp])rangeleft[tmp]=idposincomp[tmp];
else rangeleft[tmp]=it2;
del[rangeidleft[tmp]]=1;
rangeidright[x]=++curid;
rangeidleft[tmp]=++curid;
seg.update(rangeleft[tmp],idposincomp[tmp],{idpos[tmp],rangeidleft[tmp]},0);
}
else{
rangeright[x]=mx;
rangeidright[x]=++curid;
}
// cout<<"LL\n";
seg.update(rangeleft[x],idposincomp[x],{idpos[x],rangeidleft[x]},0);
seg.update(idposincomp[x],rangeright[x],{-idpos[x],rangeidright[x]},1);
}
void die(int x,int t){
del[rangeidleft[x]]=1;
del[rangeidright[x]]=1;
auto it=pos[t].find(x);
if(it==pos[t].end())assert(0);
int l,r;
if(it==pos[t].begin()){
it++;
if(it!=pos[t].end()){
tmp=(*it);
seg.update(0,rangeleft[tmp]-1,{idpos[tmp],rangeidleft[tmp]},0);
rangeleft[tmp]=0;
}
it--;
pos[t].erase(it);
return;
}
it--;
l=(*it);
it++;
it++;
if(it==pos[t].end()){
if(rangeright[l]!=mx)seg.update(rangeright[l]+1,mx,{-idpos[l],rangeidright[l]},1);
rangeright[l]=mx;
it--;
pos[t].erase(it);
return;
}
else r=(*it);
int val=ceil((idpos[l]+idpos[r])*1.0/2);
auto it2=lb(all(comp),val)-comp.begin();
if(it2==comp.size())assert(0);
int k=it2;
if(rangeright[l]>=it2)k=rangeright[l]+1;
seg.update(rangeright[l],k-1,{-idpos[l],rangeidright[l]},1);
if(rangeleft[r]<k)k=rangeleft[r];
seg.update(k,rangeleft[r],{idpos[r],rangeidleft[r]},0);
rangeright[l]=k-1;
rangeleft[r]=k;
it--;
pos[t].erase(it);
return;
}
int ans[mxn+10];
struct info{int time,etype,pos,type,id;};
bool cmp(info a,info b){
if(a.pos==b.pos)return a.etype>b.etype;
return a.pos<b.pos;
}
bool cmp2(info a,info b){
if(a.time==b.time)return a.etype<b.etype;
return a.time<b.time;
}
vector<info>event;
int what[mxn+10],bro[mxn+10],tt[mxn+10],ttt[mxn+10];
int32_t main(){
fastio
cin>>n>>k>>q;
for(int i=0;i<n;i++){
int x,t,a,b;cin>>x>>t>>a>>b;
event.pb({a,1,x,t,i});
event.pb({b+1,0,x,t,i});
comp.pb(x);
}
vector<pair<pii,int>>qry(q);
for(int i=0;i<q;i++)cin>>qry[i].f.s>>qry[i].f.f,qry[i].s=i,comp.pb(qry[i].f.s);
sort(all(qry));
sort(all(event),cmp);
sort(all(comp));
comp.erase(unique(all(comp)),comp.end());
int cnt=0;
for(auto &i:event){
if(i.etype==0){
i.id=what[i.id];
continue;
}
what[i.id]=cnt;
i.id=cnt;
idpos[cnt]=i.pos;
tt[cnt]=i.type;
idposincomp[cnt]=lb(all(comp),i.pos)-comp.begin();
ttt[cnt]=i.time;
cnt++;
}
sort(all(event),cmp2);
int p=cnt;
mx=comp.size();
int cur=0,g=0;
cnt=0;
for(int i=1;i<=k;i++)bro[i]=inf;
// for(auto i:comp)cout<<i<<" ";
//cout<<'\n';
for(auto i:qry){
g++;
while(cur<event.size()&&event[cur].time<=i.f.f){
//cout<<event[cur].pos<<" "<<event[cur].type<<" "<<event[cur].etype<<'\n';
if(event[cur].etype){
if(pos[event[cur].type].size()==0)cnt++;
add(event[cur].id,event[cur].type);
}
else{
die(event[cur].id,event[cur].type);
if(pos[event[cur].type].size()==0)cnt--;
}
cur++;
/*
for(int ii=1;ii<=k;ii++){
cout<<ii<<'\n';
for(auto j:pos[ii]){
cout<<rangeidleft[j]<<" "<<idposincomp[j]<<" "<<rangeidright[j]<<"LL\n";
}
}
cout<<"_____________\n";*/
}
pii bru=seg.qry(lb(all(comp),i.f.s)-comp.begin());
if(cnt!=k)ans[i.s]=-1;
else{
/*
for(int j=1;j<=p;j++){
if(ttt[j]>3)continue;
if(del[rangeidright[j]]!=del[rangeidleft[j]])assert(0);
if(del[rangeidright[j]]&&del[rangeidleft[j]])continue;
if((comp[rangeleft[j]]<=i.f.s&&i.f.s<=idpos[j])||(idpos[j]<=i.f.s&&i.f.s<=comp[rangeright[j]])){
int g=abs(i.f.s-idpos[j]);
bro[tt[j]]=min(bro[tt[j]],g);
}
//break;
}*/
///for(int i=1;i<=k;i++)cout<<bro[i]<<'\n';
//ans[i.s]=mx;
if(bru.f!=minf)ans[i.s]=max(ans[i.s],i.f.s+bru.f);
if(bru.s!=minf)ans[i.s]=max(ans[i.s],bru.s-i.f.s);
}
}
for(int i=0;i<q;i++)cout<<ans[i]<<'\n';
return 0;
}
/*
(2*n+q)log(n)*log(10^8)
when there are currently a,b,c shop active with the same k
int range of each shop will be (0,(a+b)/2),((a+b)/2+1,(b+c)/2),((b+c)/2+1,mx)
the contribution on range l,r when shop pos is x will be
x-a,x-b,x,c-x,d-x;
we can keep muliset segtree
*/
Compilation message
new_home.cpp: In function 'void add(int, int)':
new_home.cpp:101:15: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | if(it2==comp.size())assert(0);
| ~~~^~~~~~~~~~~~~
new_home.cpp:122:15: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | if(it2==comp.size())assert(0);
| ~~~^~~~~~~~~~~~~
new_home.cpp: In function 'void die(int, int)':
new_home.cpp:172:11: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | if(it2==comp.size())assert(0);
| ~~~^~~~~~~~~~~~~
new_home.cpp: In function 'int32_t main()':
new_home.cpp:235:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
235 | while(cur<event.size()&&event[cur].time<=i.f.f){
| ~~~^~~~~~~~~~~~~
new_home.cpp:226:9: warning: unused variable 'p' [-Wunused-variable]
226 | int p=cnt;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
141 ms |
174928 KB |
Output is correct |
| 2 |
Correct |
53 ms |
174928 KB |
Output is correct |
| 3 |
Correct |
52 ms |
175128 KB |
Output is correct |
| 4 |
Correct |
50 ms |
174928 KB |
Output is correct |
| 5 |
Runtime error |
183 ms |
354388 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
141 ms |
174928 KB |
Output is correct |
| 2 |
Correct |
53 ms |
174928 KB |
Output is correct |
| 3 |
Correct |
52 ms |
175128 KB |
Output is correct |
| 4 |
Correct |
50 ms |
174928 KB |
Output is correct |
| 5 |
Runtime error |
183 ms |
354388 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2340 ms |
399192 KB |
Output is correct |
| 2 |
Correct |
1421 ms |
308380 KB |
Output is correct |
| 3 |
Correct |
1240 ms |
365724 KB |
Output is correct |
| 4 |
Correct |
2173 ms |
395784 KB |
Output is correct |
| 5 |
Correct |
1113 ms |
283188 KB |
Output is correct |
| 6 |
Correct |
1303 ms |
305372 KB |
Output is correct |
| 7 |
Correct |
1190 ms |
364876 KB |
Output is correct |
| 8 |
Correct |
2084 ms |
394348 KB |
Output is correct |
| 9 |
Correct |
2473 ms |
410596 KB |
Output is correct |
| 10 |
Correct |
1886 ms |
373128 KB |
Output is correct |
| 11 |
Correct |
1304 ms |
322980 KB |
Output is correct |
| 12 |
Correct |
1595 ms |
364932 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4636 ms |
463864 KB |
Output is correct |
| 2 |
Runtime error |
553 ms |
470752 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
141 ms |
174928 KB |
Output is correct |
| 2 |
Correct |
53 ms |
174928 KB |
Output is correct |
| 3 |
Correct |
52 ms |
175128 KB |
Output is correct |
| 4 |
Correct |
50 ms |
174928 KB |
Output is correct |
| 5 |
Runtime error |
183 ms |
354388 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
141 ms |
174928 KB |
Output is correct |
| 2 |
Correct |
53 ms |
174928 KB |
Output is correct |
| 3 |
Correct |
52 ms |
175128 KB |
Output is correct |
| 4 |
Correct |
50 ms |
174928 KB |
Output is correct |
| 5 |
Runtime error |
183 ms |
354388 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
