| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1112577 | Pioneer | New Home (APIO18_new_home) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#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 int inf=1e8;
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];
multiset<int> st[MAX];
vector<int> tim,pos;
struct segtree{
multiset<int> t[4*2*MAX];
int mx[4*2*MAX];
segtree(){
memset(mx,-1,sizeof(mx));
}
void add(int v,int tl,int tr,int pos,int x){
pos+=m;
t[pos].insert(x);
mx[pos]=*t[pos].rbegin();
while(pos>1){
pos/=2;
mx[pos]=max(mx[2*pos],mx[2*pos+1]);
}
}
void del(int v,int tl,int tr,int pos,int x){
pos+=m;
t[pos].erase(t[pos].find(x));
mx[pos]=(t[pos].empty()?-1:*t[pos].rbegin());
while(pos>1){
pos/=2;
mx[pos]=max(mx[2*pos],mx[2*pos+1]);
}
}
int get(int v,int tl,int tr,int l,int r){
l+=m,r+=m+1;
int res=0;
while(l<r){
if(l&1){
res=max(res,mx[l++]);
}
if(r&1){
res=max(res,mx[--r]);
}
l/=2,r/=2;
}
return res;
}
}tree;
int cnt[MAX],col;
int getx(int x){
return lb(all(pos),x)-pos.begin();
}
void add(int id){
if(cnt[t[id]]==0)col++;
cnt[t[id]]++;
if(st[t[id]].count(x[id]))st[t[id]].insert(x[id]);
else{
auto l=--st[t[id]].lb(x[id]);
auto r=st[t[id]].lb(x[id]);
int LL=getx(*l+1);
if(!(*l==-1&&*r==inf+1))tree.del(1,0,m-1,LL,*r-1);
tree.add(1,0,m-1,LL,x[id]-1);
tree.add(1,0,m-1,getx(x[id]+1),*r-1);
st[t[id]].insert(x[id]);
}
}
void del(int id){
id=-id;
cnt[t[id]]--;
if(cnt[t[id]]==0)col--;
st[t[id]].erase(st[t[id]].find(x[id]));
if(!st[t[id]].count(x[id])){
auto l=--st[t[id]].lb(x[id]);
auto r=st[t[id]].lb(x[id]);
int LL=getx(*l+1);
tree.del(1,0,m-1,LL,x[id]-1);
tree.del(1,0,m-1,getx(x[id]+1),*r-1);
if(!(*l==-1&&*r==inf+1))tree.add(1,0,m-1,LL,*r-1);
}
}
bool check(int l,int r){
l=max(l,0);
r=min(r,inf);
l=ub(all(pos),l)-pos.begin()-1;
// cout<<0<<" "<<l<<" "<<tree.get(1,0,m-1,0,l)<<"\n";
if(tree.get(1,0,m-1,0,l)>=r)return 0;
return 1;
}
int ans[MAX];
void solve(){
cin>>n>>k>>q;
pos.pb(0),pos.pb(inf);
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]+1);
pos.pb(x[i]-1);
}
for(int i=1;i<=q;i++){
cin>>l[i]>>y[i];
tim.pb(y[i]);
}
sort(all(tim));
tim.erase(unique(all(tim)),tim.end());
sort(all(pos));
pos.erase(unique(all(pos)),pos.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);
}
for(int i=1;i<=k;i++){
st[i].insert(-1);
st[i].insert(inf+1);
}
m=sz(pos);
for(int i=0;i<sz(tim);i++){
for(auto id:events[i]){
if(id>0){
add(id);
}
else{
del(id);
}
}
for(int id:zap[i]){
if(col!=k){
ans[id]=-1;
}
else{
int L=0,R=inf,res=inf;
while(L<=R){
int mid=(L+R)/2;
if(check(l[id]-mid,l[id]+mid)){
R=mid-1,res=mid;
}
else L=mid+1;
}
ans[id]=res;
}
}
}
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();
}