Submission #406273

#	Time	Username	Problem	Language	Result	Execution time	Memory
406273		kshitij_sodani	New Home (APIO18_new_home)	C++14	80 / 100	5111 ms	530064 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'
int n,k,q;
int ans[300001];
set<int> pre[300001];
map<int,int> pre2[300001];
bool vis[3000001];
map<pair<int,pair<int,int>>,int> xx;
map<pair<int,pair<int,int>>,int> xx2;
map<int,int> ss;
map<int,int> ss2;
map<int,int> ss3;
map<int,int> ss4;
vector<pair<int,int>> yy;

int ne=0;
int nn;
pair<int,int> solve(int i,int j){
	pair<int,int> ac={i,0};
	pair<int,int> ac2={j+1,0};
	return {lower_bound(yy.begin(),yy.end(),ac)-yy.begin(),lower_bound(yy.begin(),yy.end(),ac2)-yy.begin()-1};
}
priority_queue<pair<int,int>> tree[4*400001];
priority_queue<pair<int,int>> tree2[4*400001];
int tree3[4*800001][2];
int kk=1;
//int ans[300001];
void update(int no,int l,int r,int aa,int bb,pair<int,int> x,int st){
	/*if(no==0){
		cout<<aa<<":"<<bb<<":"<<x.a<<":"<<x.b<<endl;
	}*/
	
	if(r<aa or l>bb or aa>bb){
		return;
	}
	if(aa<=l and r<=bb){
		//cout<<l<<",,"<<r<<endl;

		tree[no].push(x);

		tree2[no].push({-x.a,x.b});


	}
	else{
		int 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);
	}
}
void update2(int no,int l,int r,int aa,int bb,int x,int st){
/*	if(no==0){
		cout<<aa<<":"<<bb<<":"<<x<<endl;
	}*/
	
	if(r<aa or l>bb){
		return;
	}
	if(aa<=l and r<=bb){
		//cout<<l<<",,"<<r<<endl;
		tree3[no][0]=min(tree3[no][0],x);
		tree3[no][1]=max(tree3[no][1],x);
/*		if(kk){
			if(tree[no].size()){
				pair<int,int> ma=tree[no].top();
				tree[no].pop();
				tree[no].push(max(ma,x));
				 ma=tree2[no].top();
				tree2[no].pop();
				tree2[no].push(max(ma,{-x.a,x.b}));
			}
			else{
				tree[no].push(x);

				tree2[no].push({-x.a,x.b});

			}
			return ;
		}
		tree[no].push(x);

		tree2[no].push({-x.a,x.b});
*/

	}
	else{
		int mid=(l+r)/2;
		update2(no*2+1,l,mid,aa,bb,x,st);
		update2(no*2+2,mid+1,r,aa,bb,x,st);
	}
}
int query(int no,int l,int r,int i){
	int cur=0;
	while(tree[no].size()){
		if(vis[(tree[no].top()).b]){
			tree[no].pop();

		}
		else{
			break;
		}
	}
	while(tree2[no].size()){
		if(vis[(tree2[no].top()).b]){
			tree2[no].pop();
			
		}
		else{
			break;
		}
	}

	if(tree[no].size()){
		//cout<<l<<","<<r<<","<<yy[i].a<<endl;
		cur=max(cur,abs((tree[no].top()).a-yy[i].a));
		
		cur=max(cur,abs(-(tree2[no].top()).a-yy[i].a));
	}
	if(l<r){
		int 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;

}
int query2(int no,int l,int r,int i){
	int cur=0;
	//cout<<l<<"<"<<r<<"<"<<yy[i].a<<"<"<<tree3[no][0]<<"<"<<tree3[no][1]<<endl;
	cur=max(cur,yy[i].a-tree3[no][0]);
	cur=max(cur,tree3[no][1]-yy[i].a);
	if(l<r){
		int mid=(l+r)/2;
		if(i<=mid){
			cur=max(cur,query2(no*2+1,l,mid,i));
		}
		else{
			cur=max(cur,query2(no*2+2,mid+1,r,i));
		}
	}
	return cur;

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

			update2(0,0,nn-1,ind.a,ind.b,aa,0);
			//ne++;
			//xx[{i,{mid+1,bb}}]=ne;
			ind=solve(mid+1,bb);
			update2(0,0,nn-1,ind.a,ind.b,bb,0);
			//ne++;
		}
		return ;
	}
	if(st==1){
		xx[{i,{aa,mid}}]=ne;
		
		pair<int,int> 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<int,int>,pair<int,int>>> cur;
	vector<pair<int,int>> zz5;
	for(int i=0;i<n;i++){
		int x,aa,bb,tt;
		cin>>x>>tt>>aa>>bb;
		ss[x]++;
		tt--;
		if(aa!=1){
			kk=0;
		}
		cur.pb({{aa,-1},{x,tt}});
		cur.pb({{bb,1},{x,tt}});
	//	pre[tt].insert(x);
		zz5.pb({tt,x});
	}
	
	for(int i=0;i<q;i++){
		int x,aa;
		cin>>x>>aa;
		ss[x]++;
		cur.pb({{aa,0},{x,i}});
		ss3[x]++;
		/*if(kk){
			//pre[aa].insert(x);
		}*/
	}
	if(kk){
		for(auto j:zz5){
			pre[j.a].insert(j.b);
		}
		for(int i=0;i<4*ss.size()+10;i++){
			tree3[i][0]=1e8;
			tree3[i][1]=0;
		}
	}



	sort(cur.begin(),cur.end());
	int ind5=-1;
	
	ss[-2e8]++;
	
	ss[2e8]++;
	for(auto j:ss){
		ind5++;
		ss2[j.a]=ind5;
		//yy.pb({j.a,ind5});
	}
	ind5=-1;
	for(auto j:ss3){
		ind5++;
		ss4[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;*/
	//cout<<kk<<endl;
	for(int i=0;i<k;i++){
		pre[i].insert(-2e8);
		pre2[i][-2e8]++;
		pre[i].insert(2e8);
		pre2[i][2e8]++;
		//if(kk==0){
		/*if(kk==0){
			add(i,-2e8,2e8,1);
		}*/

	//	xx[{i,{-2e8,2e8}}]=;
	//	update(0,0,nn-1,0,nn-1);
	}

	for(int i=0;i<k;i++){
		vector<int> xx;
		for(auto j:pre[i]){
			xx.pb(j);
		}
	/*	for(auto j:xx){
			cout<<j<<".";
		}
		cout<<endl;*/
		for(int j=0;j+1<xx.size();j++){
			add(i,xx[j],xx[j+1],1);
			//cout<<i<<":"<<xx[j]<<":"<<xx[j+1]<<endl;
		}
	}

	for(auto j:cur){
		if(j.a.b==-1){
			//add
			/*if(kk){
				continue;
			}*/
			//continue;
			if(pre2[j.b.b].find(j.b.a)!=pre2[j.b.b].end()){
				if(pre2[j.b.b][j.b.a]>0){
					pre2[j.b.b][j.b.a]++;
					continue;
				}
			}
			//else{
				pre2[j.b.b][j.b.a]++;
				if(kk){
					continue;
				}
				int re=*(pre[j.b.b].lower_bound(j.b.a));
				auto jj=pre[j.b.b].lower_bound(j.b.a);
				jj--;
				int 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 
			/*if(kk){




				continue;
			}*/
			//continue;
			pre2[j.b.b][j.b.a]--;
			if(pre2[j.b.b][j.b.a]==0){
				//cout<<11<<endl;
				pre[j.b.b].erase(j.b.a);
				int re=*(pre[j.b.b].lower_bound(j.b.a));
				auto jj=pre[j.b.b].lower_bound(j.b.a);
				jj--;
				int 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;
			if(kk){
				int ans2=query2(0,0,nn-1,ss4[j.b.a]);
				if(ans2>1e8){
					ans2=-1;
				}
				ans[j.b.b]=ans2;
				continue;
			}
			int ans2=query(0,0,nn-1,ss4[j.b.a]);
			if(ans2>1e8){
				ans2=-1;
			}
			ans[j.b.b]=ans2;
		}
	}
	for(int i=0;i<q;i++){
		cout<<ans[i]<<endl;
	}
	/*for(int i=0;i<cur.size();i++){
		cur[i].b.a=ss2[cur[i].b.a];
	}*/





	return 0;
}
 

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:225:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |   for(int i=0;i<4*ss.size()+10;i++){
      |               ~^~~~~~~~~~~~~~~
new_home.cpp:280:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  280 |   for(int j=0;j+1<xx.size();j++){
      |               ~~~^~~~~~~~~~

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