#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define N 600010
ll dat[2*N];
void init(){
rep(i,2*N)dat[i]=-1e17;
}
void upd(ll i,ll x){
i+=N,dat[i]=x;
for(;i;i>>=1)dat[i/2]=max(dat[i],dat[i^1]);
}
ll qry(ll l,ll r){
l+=N,r+=N;
ll res=-1e17;
for(ll a=l,b=r;a<b;a>>=1,b>>=1){
if(a&1)chmax(res,dat[a++]);
if(b&1)chmax(res,dat[--b]);
}
return res;
}
struct st{
ll tim,typ,c,d;
bool operator<(const st&key)const{
if(this->tim==key.tim){
return this->typ<key.typ;
}
return this->tim<key.tim;
}
};
ll n,q,k,x[N],t[N],a[N],b[N],fans[N];
multiset<ll> s[N];
int main(){
cin.tie(0);
ios::sync_with_stdio(0);
cin>>n>>k>>q;
vector<pair<ll,ll> > xs;
rep(i,n){
cin>>x[i]>>t[i]>>a[i]>>b[i];
t[i]--;
xs.push_back(make_pair(x[i],i));
}
sort(xs.begin(),xs.end());
xs.erase(unique(xs.begin(),xs.end()),xs.end());
vector<st> v;
rep(i,n){
pair<ll,ll> key=make_pair(x[i],i);
x[i]=lower_bound(xs.begin(),xs.end(),key)-xs.begin();
v.push_back((struct st){a[i],0,x[i]+k,t[i]});
v.push_back((struct st){b[i],2,x[i]+k,t[i]});
}
rep(i,q){
ll l,y; cin>>l>>y;
v.push_back((struct st){y,1,l,i});
}
sort(v.begin(),v.end());
init();
rep(i,k){
s[i].insert(i);
s[i].insert(1e17);
upd(i,1e17);
}
for(auto e:v){
if(e.typ==0){
ll place=e.c,col=e.d;
auto it=s[col].upper_bound(place);
ll r=*it;
it--;
ll l=*it;
upd(l,place);
upd(place,r);
s[col].insert(place);
}
if(e.typ==1){
cout<<"qry"<<e.c<<" "<<e.d<<endl;
rep(i,k){
cout<<i<<":";
for(auto val:s[i])cout<<val<<" ";
cout<<endl;
}
ll place=e.c,id=e.d;
ll L=-1,R=1e9,mid;
while(L<R-1){
mid=(L+R)>>1;
pair<ll,ll> key;
key=make_pair(place-mid,-1e17);
ll l=lower_bound(xs.begin(),xs.end(),key)-xs.begin()+k;
key=make_pair(place+mid,+1e17);
ll r=upper_bound(xs.begin(),xs.end(),key)-xs.begin()-1+k;
if(qry(0,l)<=r)R=mid;
else L=mid;
}
if(R==1e9)R=-1;
fans[id]=R;
}
if(e.typ==2){
ll place=e.c,col=e.d;
s[col].erase(s[col].find(place));
auto it=s[col].upper_bound(place);
ll r=*it;
it--;
ll l=*it;
upd(place,-1e17);
upd(l,r);
}
}
rep(i,q)cout<<fans[i]<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
38008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
38008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5063 ms |
198252 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5054 ms |
224784 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
38008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
38008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
