#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=6e5,inf=1e9,minf=-1e9,Mxn=1e8;;
int mx;
bitset<Mxn>del;
set<int>pos[mxn+10];
int cnt=0;
int curid=0;
struct seg{
priority_queue<pii,vector<pii>,greater<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
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);
}
if(!(r&1)){
if(type)v[r--].push(val);
else v2[r--].push(val);
}
}
}
pii qry(int pos){
pii ans={inf,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=min(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);
}
return ans;
}
}seg;
vector<int>comp;
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){
//x =pos in comp;
auto it=pos[t].insert(x).f;
if(it!=pos[t].begin()){
it--;
tmp=(*it);
int val=(idpos[tmp]+idpos[x])/2;
//find mid point
auto it2=lb(all(comp),val)-comp.begin();
if(it2==comp.size())assert(0);
//find mid point in comp
rangeright[tmp]=it2-1;
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=(idpos[tmp]+idpos[x])/2;
auto it2=lb(all(comp),val)-comp.begin();
if(it2==comp.size())assert(0);
rangeright[x]=it2-1;
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]=comp.size()-1;
rangeidright[x]=++curid;
}
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())return;
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()){
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=(idpos[l]+idpos[r])/2;
auto it2=lb(all(comp),val)-comp.begin();
if(it2==comp.size())assert(0);
seg.update(rangeright[l],it2-1,{-idpos[l],rangeidright[l]},1);
seg.update(val,rangeleft[r],{idpos[r],rangeidleft[r]},0);
rangeright[l]=it2-1;
rangeleft[r]=it2;
it--;
pos[t].erase(it);
return;
}
int ans[mxn+10];
struct info{int time,etype,pos,type,id;};
bool cmp(info a,info b){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];
int32_t main(){
fastio
int n,k,q;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].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;
idposincomp[cnt]=lb(all(comp),i.pos)-comp.begin();
cnt++;
}
sort(all(event),cmp2);
mx=comp.size();
int cur=0;
cnt=0;
int g=0;
for(auto i:qry){
g++;
while(cur<event.size()&&event[cur].time<=i.f.f){
//cout<<event[cur].time<<" "<<event[cur].type<<" "<<event[cur].pos<<' '<<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++;
}
pii bru=seg.qry(lb(all(comp),i.f.s)-comp.begin());
if(cnt!=k)ans[i.s]=-1;
else {
if(bru.f!=inf)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:88:15: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | if(it2==comp.size())assert(0);
| ~~~^~~~~~~~~~~~~
new_home.cpp:107:15: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | if(it2==comp.size())assert(0);
| ~~~^~~~~~~~~~~~~
new_home.cpp: In function 'void die(int, int)':
new_home.cpp:153:11: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | if(it2==comp.size())assert(0);
| ~~~^~~~~~~~~~~~~
new_home.cpp: In function 'int32_t main()':
new_home.cpp:205:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
205 | while(cur<event.size()&&event[cur].time<=i.f.f){
| ~~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
60 ms |
119380 KB |
Output is correct |
| 2 |
Correct |
24 ms |
119388 KB |
Output is correct |
| 3 |
Correct |
25 ms |
119388 KB |
Output is correct |
| 4 |
Incorrect |
26 ms |
119388 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
60 ms |
119380 KB |
Output is correct |
| 2 |
Correct |
24 ms |
119388 KB |
Output is correct |
| 3 |
Correct |
25 ms |
119388 KB |
Output is correct |
| 4 |
Incorrect |
26 ms |
119388 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2122 ms |
312716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2576 ms |
332052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
60 ms |
119380 KB |
Output is correct |
| 2 |
Correct |
24 ms |
119388 KB |
Output is correct |
| 3 |
Correct |
25 ms |
119388 KB |
Output is correct |
| 4 |
Incorrect |
26 ms |
119388 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
60 ms |
119380 KB |
Output is correct |
| 2 |
Correct |
24 ms |
119388 KB |
Output is correct |
| 3 |
Correct |
25 ms |
119388 KB |
Output is correct |
| 4 |
Incorrect |
26 ms |
119388 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
