#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]);
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!=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<<' '<<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[5*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=vr[tmr-1];
// cout<<"ADDITIOn "<<l<<' '<<mid<<' '<<r<<' '<<st<<' '<<_end<<endl;
addls.pb({mid,st,_end,-l});
addrs.pb({mid+1,st,_end,r});
return;
}
mp[{l,tp}]=tmr;
vr[tmr]=cur_t;
++tmr;
}
const int Nax=3e5+1;
multiset<int> st[N];
vec<int>here[N];
signed main(){
fast_iati;
lft.type=0;rgt.type=1;
int n,q,k;
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]);
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));
umax(me.f,omn);me.s++;
}
return me;
};
int uk=0;
for(auto &z : arr){
while(uk<sz(ts) && ts[uk]<z[0]) ++uk;
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>ans(q,-1);
for(auto &z : arr){
cur_t=z[0];
swap(z[1],z[2]);
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--;
}
else{
int i=z[1];
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]);
}
}
///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);
rgt.build(1,0,sz(ts)-1);
for(int i=0;i<q;i++){
int j=l[i];
int my_t=lower_bound(all(ts),y[i])-ts.begin();
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));
id=upper_bound(all(rgt.pos[1]),j)-rgt.pos[1].begin()-1;
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:146:10: warning: variable 'stupid' set but not used [-Wunused-but-set-variable]
146 | auto stupid=[&](array<int,3> z){
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
101 ms |
234180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
101 ms |
234180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5085 ms |
548788 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5080 ms |
555072 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
101 ms |
234180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
101 ms |
234180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
