#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define ll long long
#define int ll
#define all(v) v.begin(),v.end()
#define sz(s) ((int)s.size())
#define pb push_back
#define F first
#define S second
#define pii pair<int,int>
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
const ll inf=1e18;
const int MAX=3e5+10;
const int mod=1e9+7;
int binpow(int a,int n){
if(!n)return 1;
if(n%2==1)return a*binpow(a,n-1)%mod;
int k=binpow(a,n/2);
return k*k%mod;
}
int n,k,q,m;
int a[MAX],b[MAX],x[MAX],t[MAX];
int l[MAX],y[MAX];
vector<int> events[MAX+MAX],zap[MAX+MAX];
set<pii> st[MAX];
vector<int> tim,pos;
struct segtree{
multiset<int> t[4*MAX];
void add(int v,int tl,int tr,int l,int r,int x){
if(l>r||tl>r||l>tr)return;
if(l<=tl&&tr<=r){
t[v].insert(x);
return;
}
int tm=(tl+tr)/2;
add(2*v,tl,tm,l,r,x);
add(2*v+1,tm+1,tr,l,r,x);
}
void del(int v,int tl,int tr,int l,int r,int x){
if(l>r||tl>r||l>tr)return;
if(l<=tl&&tr<=r){
t[v].erase(t[v].find(x));
return;
}
int tm=(tl+tr)/2;
del(2*v,tl,tm,l,r,x);
del(2*v+1,tm+1,tr,l,r,x);
}
int get(int v,int tl,int tr,int p,int x){
int res=0;
if(!t[v].empty())res=max(abs(*t[v].begin()-x),abs(*t[v].rbegin()-x));
// if(!t[v].empty())cout<<*t[v].begin()<<" "<<*t[v].rbegin()<<" "<<x<<"\n";
if(tl==tr)return res;
int tm=(tl+tr)/2;
if(p<=tm)return max(res,get(2*v,tl,tm,p,x));
else return max(res,get(2*v+1,tm+1,tr,p,x));
}
}tree;
int L[MAX],R[MAX];
int cnt[MAX],col;
void add(int id){
if(cnt[t[id]]==0)col++;
cnt[t[id]]++;
if(st[t[id]].empty()){
L[id]=0,R[id]=m-1;
tree.add(1,0,m-1,0,m-1,x[id]);
}
else{
auto r=st[t[id]].lb({x[id],id});
if(r==st[t[id]].end()){
r--;
tree.del(1,0,m-1,L[r->S],R[r->S],x[r->S]);
int mid=ub(all(pos),(r->F+x[id])/2)-pos.begin()-1;
R[r->S]=mid;
L[id]=mid+1,R[id]=m-1;
tree.add(1,0,m-1,L[r->S],R[r->S],x[r->S]);
tree.add(1,0,m-1,L[id],R[id],x[id]);
}
else if(r==st[t[id]].begin()){
tree.del(1,0,m-1,L[r->S],R[r->S],x[r->S]);
int mid=ub(all(pos),(x[id]+r->F)/2)-pos.begin()-1;
R[id]=mid,L[id]=0;
L[r->S]=mid+1;
tree.add(1,0,m-1,L[r->S],R[r->S],x[r->S]);
tree.add(1,0,m-1,L[id],R[id],x[id]);
}
else{
auto l=--st[t[id]].lb({x[id],id});
tree.del(1,0,m-1,L[r->S],R[r->S],x[r->S]);
tree.del(1,0,m-1,L[l->S],R[l->S],x[l->S]);
int mid1=ub(all(pos),(x[id]+l->F)/2)-pos.begin()-1;
int mid2=ub(all(pos),(x[id]+r->F)/2)-pos.begin()-1;
R[l->S]=mid1;
L[id]=mid1+1;
R[id]=mid2;
L[r->S]=mid2+1;
tree.add(1,0,m-1,L[r->S],R[r->S],x[r->S]);
tree.add(1,0,m-1,L[l->S],R[l->S],x[l->S]);
tree.add(1,0,m-1,L[id],R[id],x[id]);
}
}
st[t[id]].insert({x[id],id});
}
void del(int id){
id=-id;
cnt[t[id]]--;
if(cnt[t[id]]==0)col--;
if(sz(st[t[id]])==1){
// cerr<<"OK\n";
tree.del(1,0,m-1,0,m-1,x[id]);
}
else{
tree.del(1,0,m-1,L[id],R[id],x[id]);
auto r=st[t[id]].lb({x[id],id});
if(r==st[t[id]].end()){
r--;
tree.del(1,0,m-1,L[r->S],R[r->S],x[r->S]);
R[r->S]=m-1;
tree.add(1,0,m-1,L[r->S],R[r->S],x[r->S]);
}
else if(r==st[t[id]].begin()){
r++;
tree.del(1,0,m-1,L[r->S],R[r->S],x[r->S]);
L[r->S]=0;
tree.add(1,0,m-1,L[r->S],R[r->S],x[r->S]);
}
else{
auto l=--st[t[id]].lb({x[id],id});
r++;
tree.del(1,0,m-1,L[r->S],R[r->S],x[r->S]);
tree.del(1,0,m-1,L[l->S],R[l->S],x[l->S]);
int mid=ub(all(pos),(r->F+l->F)/2)-pos.begin()-1;
R[l->S]=mid;
L[id]=mid+1;
tree.add(1,0,m-1,L[r->S],R[r->S],x[r->S]);
tree.add(1,0,m-1,L[l->S],R[l->S],x[l->S]);
}
}
st[t[id]].erase({x[id],id});
}
void solve(){
cin>>n>>k>>q;
for(int i=1;i<=n;i++){
cin>>x[i]>>t[i]>>a[i]>>b[i];
tim.pb(a[i]);
tim.pb(b[i]+1);
pos.pb(x[i]);
}
for(int i=1;i<=q;i++){
cin>>l[i]>>y[i];
pos.pb(l[i]);
tim.pb(y[i]);
}
sort(all(pos));
pos.erase(unique(all(pos)),pos.end());
sort(all(tim));
tim.erase(unique(all(tim)),tim.end());
for(int i=1;i<=n;i++){
a[i]=lb(all(tim),a[i])-tim.begin();
b[i]=lb(all(tim),b[i]+1)-tim.begin();
events[a[i]].pb(i);
events[b[i]].pb(-i);
}
for(int i=1;i<=q;i++){
y[i]=lb(all(tim),y[i])-tim.begin();
zap[y[i]].pb(i);
}
m=sz(pos);
vector<int> ans(q+1,0);
// cerr<<sz(tim)<<"\n";
for(int i=0;i<sz(tim);i++){
// cerr<<0<<"\n";
for(auto id:events[i]){
if(id>0){
add(id);
}
else{
del(id);
}
}
// cout<<"! "<<tim[i]<<"\n";
for(int id:zap[i]){
// cout<<col<<"\n";
// cout<<"? "<<id<<" "<<l[id]<<"\n";
if(col!=k)ans[id]=-1;
else ans[id]=tree.get(1,0,m-1,lb(all(pos),l[id])-pos.begin(),l[id]);
}
// for(int i=1;i<=n;i++)cout<<L[i]<<" "<<R[i]<<" "<<pos[L[i]]<<" "<<pos[R[i]]<<"\n";
}
for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
99120 KB |
Output is correct |
| 2 |
Execution timed out |
5067 ms |
99144 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
99120 KB |
Output is correct |
| 2 |
Execution timed out |
5067 ms |
99144 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
555 ms |
301240 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
696 ms |
313840 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
99120 KB |
Output is correct |
| 2 |
Execution timed out |
5067 ms |
99144 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
99120 KB |
Output is correct |
| 2 |
Execution timed out |
5067 ms |
99144 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
