#include <bits/stdc++.h>
#define f first
#define s second
#define sz(x) (int)(x).size()
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define pw(x) (1LL<<(x))
#define m_p make_pair
#define fast_iati ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pii;
const int lg=log2(300'000)+1;
const int N=pw(lg);
bool del[5*N];
struct segtree{
vec<int> uk[2*N][2];
vec<int> pos[2*N];
vec<int> mx[2*N];
int type=0;
void build(int v,int tl,int tr){
/// my positions are like that
if(type){
for(int i=sz(pos[v])-2;i>=0;i--)
umax(mx[v][i],mx[v][i+1]);
if(tl==tr)
return;
for(int t=0;t<2;t++){
uk[v][t].resize(sz(pos[v]));
int u=2*v+t;
int j=sz(pos[u]);
for(int i=sz(pos[v])-1;i>=0;i--){
while(j!=0 && pos[u][j-1]>=pos[v][i]) --j;
uk[v][t][i]=j;
}
}
}
else{
for(int i=1;i<sz(pos[v]);i++)
umax(mx[v][i],mx[v][i-1]);
// cout<<"BUILD "<<v<<endl;
// for(auto &z : pos[v])
// cout<<z<<' ';
// cout<<endl;
// for(auto &z : mx[v])
// cout<<z<<' ';
// cout<<endl;
if(tl==tr)
return;
for(int t=0;t<2;t++){
uk[v][t].resize(sz(pos[v]));
int u=2*v+t;
int j=-1;
for(int i=0;i<sz(pos[v]);i++){
while(j+1!=sz(pos[u]) && pos[u][j+1]<=pos[v][i]) ++j;
uk[v][t][i]=j;
}
}
}
int tm=(tl+tr)>>1;
build(2*v,tl,tm);build(2*v+1,tm+1,tr);
}
void add(int l,int r,int i,int x,int v,int tl,int tr){
if(tl>r||tr<l)
return;
if(!sz(pos[v]) || pos[v].back()!=i)
pos[v].pb(i),mx[v].pb(-1e9);
// cout<<"ADDED "<<i<<' '<<x<<' '<<l<<' '<<r<<' '<<tl<<' '<<tr<<'\n';
if(tl>=l&&tr<=r){
// cout<<"_SET "<<v<<' '<<sz(mx[v])-1<<' '<<i<<' '<<x<<endl;
umax(mx[v].back(),x);
return;
}
int tm=(tl+tr)>>1;
add(l,r,i,x,2*v,tl,tm);add(l,r,i,x,2*v+1,tm+1,tr);
}
int get(int _t,int j,int v,int tl,int tr){
if(_t>tr || _t<tl)
return -1e9;
if(j==-1 || j==sz(pos[v]))
return -1e9;
int ans=mx[v][j];
if(tl==tr){
return ans;
}
int tm=(tl+tr)>>1;
if(tm>=_t)
return max(ans,get(_t,uk[v][0][j],2*v,tl,tm));
else
return max(ans,get(_t,uk[v][1][j],2*v+1,tm+1,tr));
}
}lft,rgt;
vec<int> ts;
map<pii,int>mp;
int vr[4*N];
int tmr,cur_t=-1;
vec<array<int,4>>addls;
vec<array<int,4>>addrs;
void add(int l,int r,int t,int tp){
if(l==r) return;
int mid=(l+r)>>1;
if(!t){
int st=vr[mp[{l,tp}]],_end=(cur_t)-1;
mp.erase({l,tp});
// cout<<"ADDITIOn "<<l<<' '<<' '<<r<<' '<<st<<' '<<_end<<endl;
addls.pb({mid,st,_end,-l});
// cout<<"WHAT "<<mid<<' '<<r<<' '<<st<<' '<<_end<<endl;
addrs.pb({mid+1,st,_end,r});
return;
}
// cout<<"CHE "<<l<<' '<<r<<endl;
mp[{l,tp}]=tmr;
vr[tmr]=cur_t;
++tmr;
}
const int Nax=3e5+1;
multiset<int> st[Nax];
vec<int>here[Nax];
signed main(){
fast_iati;
lft.type=1;rgt.type=0;
int n,q,k;
// n=15;k=4;q=15;
cin>>n>>k>>q;
vec<array<int,3>>arr;
vec<int>x(n),a(n),b(n),t(n);
for(int i=0;i<n;i++){
cin>>x[i]>>t[i]>>a[i]>>b[i];
// x[i]=rand(),t[i]=rand()%k+1;
// a[i]=rand(),b[i]=rand();
// if(a[i]>b[i])
// swap(a[i],b[i]);
// kek.pb(x[i]);
// ts.pb(a[i]);
// ts.pb(b[i]+1);
arr.pb({a[i],0,i});
arr.pb({b[i]+1,-1,i});
--t[i];
here[t[i]].pb(i);
}
vec<int>l(q),y(q);
for(int i=0;i<q;i++){
cin>>l[i]>>y[i];
// l[i]=rand(),y[i]=rand();
ts.pb(y[i]);
arr.pb({y[i],2,i});
}
ts.pb(-2e9);
sort(all(ts));ts.erase(unique(all(ts)),ts.end());
sort(all(arr));
auto stupid=[&](array<int,3> z){
pii me={-1e9,0};
int tx=l[z[1]];
for(int j=0;j<k;j++){
if(sz(st[j])==2) continue;
auto it=st[j].lower_bound(tx);
int omn=2e9;
if(it!=st[j].end()) umin(omn,*it-tx);
if(it!=st[j].begin()) umin(omn,tx-*prev(it));
// cout<<"COLOUR "<<j<<' '<<omn<<' '<<tx<<endl;
umax(me.f,omn);me.s++;
}
return me;
};
int uk=0;
for(auto &z : arr){
while(uk+1<sz(ts) && ts[uk+1]<=z[0]) ++uk;
// cout<<"ALO "<<z[0]<<' '<<uk<<' '<<ts[uk]<<endl;
z[0]=uk;
}
vec<int>cnt(k,0);
cur_t=0;
for(int i=0;i<k;i++){
add(-3e8,3e8,1,i);
st[i].insert(-3e8);st[i].insert(3e8);
}
int total=0;
vec<int>sta(q,-1);
vec<bool>bad(q,0);
for(auto &z : arr){
cur_t=z[0];
swap(z[1],z[2]);
if(z[2]==2){
bad[z[1]]=(total==k?0:1);
// cout<<"ALO "<<
// sta[z[1]]=(total==k?stupid(z).f:-1);
continue;
}
// cout<<"TYPE "<<t[z[1]]<<endl;
if(z[2]==-1){
int i=z[1];
auto it=st[t[i]].lower_bound(x[i]);
add(x[i],*next(it),0,t[i]);
add(*prev(it),x[i],0,t[i]);
add(*prev(it),*next(it),1,t[i]);
st[t[i]].erase(it);
cnt[t[i]]--;
if(!cnt[t[i]])
total--;
// cout<<"DEL "<<x[i]<<endl;
}
else{
int i=z[1];
// cout<<"ADD "<<x[i]<<endl;
if(!cnt[t[i]])
total++;
cnt[t[i]]++;
st[t[i]].insert(x[i]);
auto it=st[t[i]].lower_bound(x[i]);
add(*prev(it),*next(it),0,t[i]);
add(x[i],*next(it),1,t[i]);
add(*prev(it),x[i],1,t[i]);
}
// cout<<z[0]<<' '<<total<<endl;
}
///building
sort(all(addls));sort(all(addrs));
for(auto &z : addls)
lft.add(z[1],z[2],z[0],z[3],1,0,sz(ts)-1);
// cout<<endl;
for(auto &z : addrs)
rgt.add(z[1],z[2],z[0],z[3],1,0,sz(ts)-1);
lft.build(1,0,sz(ts)-1);
// cout<<endl;cout<<endl;
rgt.build(1,0,sz(ts)-1);
for(int i=0;i<q;i++){
// if(cntt[])
int j=l[i];
int my_t=lower_bound(all(ts),y[i])-ts.begin();
// cout<<"STUPID "<<sta[i]<<' ';
if(bad[i]){
cout<<-1<<'\n';
continue;
}
int id=lower_bound(all(lft.pos[1]),j)-lft.pos[1].begin();
int ans=max(0,j+lft.get(my_t,id,1,0,sz(ts)-1));
// cout<<"ALO "<<ans<<endl;
id=upper_bound(all(rgt.pos[1]),j)-rgt.pos[1].begin()-1;
// cout<<"DEBUGID "<<id<<endl;
umax(ans,-j+rgt.get(my_t,id,1,0,sz(ts)-1));
if(ans>1e8)
ans=-1;
cout<<ans<<'\n';
}
return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7
1 1 1
100000000 1 1 1
1 1
*/
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:160:10: warning: variable 'stupid' set but not used [-Wunused-but-set-variable]
160 | auto stupid=[&](array<int,3> z){
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
218552 KB |
Output is correct |
| 2 |
Correct |
114 ms |
218344 KB |
Output is correct |
| 3 |
Correct |
115 ms |
218404 KB |
Output is correct |
| 4 |
Incorrect |
111 ms |
218460 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
218552 KB |
Output is correct |
| 2 |
Correct |
114 ms |
218344 KB |
Output is correct |
| 3 |
Correct |
115 ms |
218404 KB |
Output is correct |
| 4 |
Incorrect |
111 ms |
218460 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3645 ms |
916820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5134 ms |
734768 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
218552 KB |
Output is correct |
| 2 |
Correct |
114 ms |
218344 KB |
Output is correct |
| 3 |
Correct |
115 ms |
218404 KB |
Output is correct |
| 4 |
Incorrect |
111 ms |
218460 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
218552 KB |
Output is correct |
| 2 |
Correct |
114 ms |
218344 KB |
Output is correct |
| 3 |
Correct |
115 ms |
218404 KB |
Output is correct |
| 4 |
Incorrect |
111 ms |
218460 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
