#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 N=6e5+1;
struct segtree{
multiset<int> st[4*N];
void add(int l,int r,int tp,int x,int v,int tl,int tr){
if(tl>=l&&tr<=r){
if(tp)
st[v].insert(x);
else
st[v].erase(st[v].find(x));
// cout<<"ADDT "<<tp<<' '<<tl<<' '<<tr<<' '<<x<<endl;
return;
}
if(tl>r||tr<l) return;
int tm=(tl+tr)>>1;
add(l,r,tp,x,2*v,tl,tm);add(l,r,tp,x,2*v+1,tm+1,tr);
}
pii get(int id,int v,int tl,int tr){
pii ans={-1e9,0};
ans.s+=sz(st[v]);
if(sz(st[v]))
umax(ans.f,*st[v].rbegin());
if(tl==tr){
return ans;
}
int tm=(tl+tr)>>1;
pii w;
if(tm>=id)
w=get(id,2*v,tl,tm);
else
w=get(id,2*v+1,tm+1,tr);
ans.f=max(ans.f,w.f);
ans.s+=w.s;
return ans;
}
}lft,rgt;
vec<int> kek;
int gl(int x){
return upper_bound(all(kek),x)-kek.begin()-1;
}
int gu(int x){
return upper_bound(all(kek),x)-kek.begin();
}
void add(int l,int r,int t){
if(l==r) return;
int mid=(l+r)>>1;
// if(l!=-3e8 || r!=3e8){
//// cout<<"ADD "<<l<<' '<<mid<<' '<<t<<' '<<-l<<' '<<endl;
//// cout<<"ADD "<<mid+1<<' '<<r<<' '<<t<<' '<<r<<' '<<endl;
// }
if(gl(mid)>=0)
lft.add(gl(l),gl(mid),t,-l,1,0,sz(kek)-1);
if(gl(mid)+1<=gl(r))
rgt.add(gl(mid)+1,gl(r),t,r,1,0,sz(kek)-1);
}
const int Nax=3e5+1;
multiset<int> st[N];
signed main(){
fast_iati;
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];
kek.pb(x[i]);
arr.pb({a[i],i,0});
arr.pb({b[i]+1,i,-1});
--t[i];
}
vec<int>l(q),y(q);
for(int i=0;i<q;i++){
cin>>l[i]>>y[i];
kek.pb(y[i]);
arr.pb({y[i],i,2});
}
sort(all(kek));kek.erase(unique(all(kek)),kek.end());
sort(all(arr));
auto stupid=[&](array<int,3> z){
pii me={-1e9,0};
int x=l[z[1]];
for(int j=0;j<k;j++){
if(sz(st[j])==2) continue;
// cout<<"TYP "<<endl;
// for(auto &z : st[j])
// cout<<z<<' ';
// cout<<endl;
auto it=st[j].lower_bound(x);
int mn=2e9;
if(it!=st[j].end()) umin(mn,*it-x);
if(it!=st[j].begin()) umin(mn,x-*prev(it));
umax(me.f,mn);
me.s++;
}
return me;
};
auto solve=[&](array<int,3> z){
pii me={-1e9,0};
int x=l[z[1]];
x=gl(x);
pii fe=lft.get(x,1,0,sz(kek)-1);
pii si=rgt.get(x,1,0,sz(kek)-1);
// cout<<fe.f<<' '<<si.f<<endl;
me.s=fe.s+si.s;
me.f=max(fe.f+l[z[1]],si.f-l[z[1]]);
return me;
};
vec<int>cnt(k,0);
for(int i=0;i<k;i++){
add(-3e8,3e8,1);
st[i].insert(-3e8);
st[i].insert(3e8);
}
int total=0;
vec<int>ans(q,-1);
for(auto &z : arr){
if(z[2]==2){
pii og=stupid(z);
// cout<<"TOTAL "<<total<<' '<<og.s<<endl;
assert(total==og.s);
if(total!=k){
ans[z[1]]=-1;
continue;
}
// assert(rio.f==og.f);
pii rio=solve(z);
// assert(rio.f==og.f);
ans[z[1]]=og.f;
// cerr<<"BRUTE "<<og.f<<' '<<og.s<<endl;
// cerr<<"SOL "<<rio.f<<' '<<rio.s<<endl;
ans[z[1]]=rio.f;
}
else if(z[2]==-1){
int i=z[1];
auto it=st[t[i]].lower_bound(x[i]);
add(x[i],*next(it),0);
add(*prev(it),x[i],0);
add(*prev(it),*next(it),1);
st[t[i]].erase(it);
cnt[t[i]]--;
if(!cnt[t[i]]) total--;
// cout<<"DEL "<<t[i]<<x[i]<<endl;
}
else{
int i=z[1];
if(!cnt[t[i]]) total++;
cnt[t[i]]++;
st[t[i]].insert(x[i]);
// cout<<"BLY "<<t[i]<<' '<<x[i]<<endl;
auto it=st[t[i]].lower_bound(x[i]);
add(*prev(it),*next(it),0);
add(x[i],*next(it),1);
add(*prev(it),x[i],1);
}
}
for(auto &z : ans)
cout<<z<<'\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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
120 ms |
253836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
120 ms |
253836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5086 ms |
529520 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5061 ms |
449844 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
120 ms |
253836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
120 ms |
253836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
