Submission #406141

#	Time	Username	Problem	Language	Result	Execution time	Memory
406141		kshitij_sodani	New Home (APIO18_new_home)	C++14	0 / 100	5121 ms	855556 KiB

new_home

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
llo n,k,q;
llo ans[300001];
set<llo> pre[300001];
map<llo,llo> pre2[300001];
bool vis[3000001];
map<pair<llo,pair<llo,llo>>,llo> xx;
map<pair<llo,pair<llo,llo>>,llo> xx2;
map<llo,llo> ss;
map<llo,llo> ss2;
vector<pair<llo,llo>> yy;

llo ne=0;
llo nn;
pair<llo,llo> solve(llo i,llo j){
	pair<llo,llo> ac={i,0};
	pair<llo,llo> ac2={j+1,0};
	return {lower_bound(yy.begin(),yy.end(),ac)-yy.begin(),lower_bound(yy.begin(),yy.end(),ac2)-yy.begin()-1};
}
set<pair<llo,llo>> tree[4*800001];
//llo ans[300001];
void update(llo no,llo l,llo r,llo aa,llo bb,pair<llo,llo> x,llo st){
	/*if(no==0){
		cout<<aa<<":"<<bb<<":"<<x.a<<":"<<x.b<<endl;
	}*/
	
	if(r<aa or l>bb){
		return;
	}
	if(aa<=l and r<=bb){
		//cout<<l<<",,"<<r<<endl;
		tree[no].insert(x);
	}
	else{
		llo mid=(l+r)/2;
		update(no*2+1,l,mid,aa,bb,x,st);
		update(no*2+2,mid+1,r,aa,bb,x,st);
	}
}
llo query(llo no,llo l,llo r,llo i){
	llo cur=0;
	while(tree[no].size()){
		if(vis[(*(tree[no].begin())).b]){
			tree[no].erase(tree[no].begin());
		}
		else{
			break;
		}
	}
	while(tree[no].size()){
		auto j=tree[no].end();
		j--;
		if(vis[(*j).b]){
			tree[no].erase(j);
		}
		else{
			break;
		}
	}

	if(tree[no].size()){
		//cout<<l<<","<<r<<","<<yy[i].a<<endl;
		cur=max(cur,abs((*tree[no].begin()).a-yy[i].a));
		auto jj=tree[no].end();
		jj--;
		cur=max(cur,abs((*jj).a-yy[i].a));
	}
	if(l<r){
		llo mid=(l+r)/2;
		if(i<=mid){
			cur=max(cur,query(no*2+1,l,mid,i));
		}
		else{
			cur=max(cur,query(no*2+2,mid+1,r,i));
		}
	}
	return cur;

}
void add(llo i,llo aa,llo bb,llo st){
	llo mid=(aa+bb)/2;
	if(st==1){
		xx[{i,{aa,mid}}]=ne;
		
		pair<llo,llo> ind=solve(aa,mid);

		update(0,0,nn-1,ind.a,ind.b,{aa,ne},0);
		ne++;
		xx[{i,{mid+1,bb}}]=ne;
		ind=solve(mid+1,bb);
		update(0,0,nn-1,ind.a,ind.b,{bb,ne},1);
		ne++;
	}
	else{
		vis[xx[{i,{aa,mid}}]]=1;
		vis[xx[{i,{mid+1,bb}}]]=1;
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k>>q;

	vector<pair<pair<llo,llo>,pair<llo,llo>>> cur;
	for(llo i=0;i<n;i++){
		llo x,aa,bb,tt;
		cin>>x>>tt>>aa>>bb;
		ss[x]++;
		tt--;
		cur.pb({{aa,-1},{x,tt}});
		cur.pb({{bb,1},{x,tt}});
	}
	for(llo i=0;i<q;i++){
		llo x,aa;
		cin>>x>>aa;
		ss[x]++;
		cur.pb({{aa,0},{x,i}});
	}
	sort(cur.begin(),cur.end());
	llo ind5=-1;
	
	ss[-1e9]++;
	
	ss[1e9]++;
	for(auto j:ss){
		ind5++;
		ss2[j.a]=ind5;
		yy.pb({j.a,ind5});
	}
	nn=yy.size();
	//sort(cur.begin(),cur.end());
/*	for(auto j:yy){
		cout<<j.a<<",";
	}
	cout<<endl;*/
	
	for(llo i=0;i<k;i++){
		pre[i].insert(-1e9);
		pre2[i][-1e9]++;
		pre[i].insert(1e9);
		pre2[i][1e9]++;
		add(i,-1e9,1e9,1);
	//	xx[{i,{-1e9,1e9}}]=;
	//	update(0,0,nn-1,0,nn-1);
	}

	for(auto j:cur){
		if(j.a.b==-1){
			//add
			//continue;
			if(pre2[j.b.b].find(j.b.a)!=pre2[j.b.b].end()){
				pre2[j.b.b][j.b.a]++;
			}
			else{
				pre2[j.b.b][j.b.a]++;
				llo re=*(pre[j.b.b].lower_bound(j.b.a));
				auto jj=pre[j.b.b].lower_bound(j.b.a);
				jj--;
				llo le=*jj;
				pre[j.b.b].insert(j.b.a);
				add(j.b.b,le,re,0);
				add(j.b.b,le,j.b.a,1);
				add(j.b.b,j.b.a,re,1);
			}
		}
		else if(j.a.b==1){
			//remove 
			//continue;
			pre2[j.b.b][j.b.a]--;
			if(pre2[j.b.b][j.b.a]==0){
				pre[j.b.b].erase(j.b.a);
				llo re=*(pre[j.b.b].lower_bound(j.b.a));
				auto jj=pre[j.b.b].lower_bound(j.b.a);
				jj--;
				llo le=*jj;
				add(j.b.b,le,j.b.a,0);
				add(j.b.b,j.b.a,re,0);
				add(j.b.b,le,re,1);
				
			}
		}
		else{
			//cout<<j.b.a<<":"<<j.b.b<<endl;
			llo ans2=query(0,0,nn-1,ss2[j.b.a]);
			if(ans2>1e8){
				ans2=-1;
			}
			ans[j.b.b]=ans2;
		}
	}
	for(llo i=0;i<q;i++){
		cout<<ans[i]<<endl;
	}
	/*for(llo i=0;i<cur.size();i++){
		cur[i].b.a=ss2[cur[i].b.a];
	}*/





	return 0;
}
 

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20