Submission #138808

#	Time	Username	Problem	Language	Result	Execution time	Memory
138808		FedericoS	New Home (APIO18_new_home)	C++14	22 / 100	3086 ms	88612 KiB

new_home

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;
 
int N,K,Q;
ll X[300005],T[300005],A[300005],B[300005],P[300005],Y[300005];
multiset<ll> L,R;
multiset<ll> S[405];
vector<ll> V[300005];
vector<pair<pair<ll,string>,pll> > Eold;
vector<pair<pair<ll,string>,ll> > E;
int ans[300005];

ll dist(ll x, ll t){
	ll res=1e9;
	auto p=S[t].lower_bound(x);
	if(p!=S[t].end())
		res=(*p)-x;
	if(p!=S[t].begin()){
		p--;
		res=min(res,x-(*p));
	}
	return res;
}

int main(){
	cin>>N>>K>>Q;
	for(int i=0;i<N;i++){
		cin>>X[i]>>T[i]>>A[i]>>B[i];
		T[i]--;
	}
	for(int i=0;i<Q;i++)
		cin>>P[i]>>Y[i];
 
	if(K<=400 and N<=60000){
 		for(int i=0;i<Q;i++)
 			E.push_back({{Y[i],"q"},i});
 		for(int i=0;i<N;i++){
 			E.push_back({{A[i],"a"},i});
 			E.push_back({{B[i],"r"},i});
 		}
 		sort(E.begin(),E.end());

 		for(auto p:E){
 			int a=p.second;
 			string t=p.first.second;

 			if(t=="a")
 				S[T[a]].insert(X[a]);
 			else if(t=="r")
 				S[T[a]].erase(S[T[a]].find(X[a]));
 			else{
 				ll res=-1;
 				for(int i=0;i<K;i++)
 					res=max(res,dist(P[a],i));
 				ans[a]=(res==1e9)?-1:res;
 			}

 		}

 		for(int i=0;i<Q;i++)
 			cout<<ans[i]<<" ";
	}
	else{
 
		for(int i=0;i<N;i++)
			X[i]*=2;
		for(int i=0;i<Q;i++)
			P[i]*=2;
 
		for(int i=0;i<Q;i++)
			Eold.push_back({{P[i],"cq"},{P[i],i}});
 
		for(int i=0;i<N;i++)
			V[T[i]].push_back(X[i]);
 
		for(int i=0;i<K;i++){
 
			sort(V[i].begin(),V[i].end());
 
			vector<int> W;
			for(ll x:V[i])
				if((!W.empty() and W.back()!=x) or W.empty())
					W.push_back(x);
 
			V[i].clear();
			for(ll x:W)
				V[i].push_back(x);
		}
 
		for(int i=0;i<K;i++)
			for(int x:V[i])
				Eold.push_back({{x,"arl"},{x,x}});
 
		for(int i=0;i<K;i++)
			for(int j=0;j<V[i].size()-1;j++)
				if(V[i][j]!=V[i][j+1])
					Eold.push_back({{(V[i][j]+V[i][j+1])/2,"blr"},{V[i][j],V[i][j+1]}});
 
		for(int i=0;i<K;i++)
			R.insert(V[i][0]);
 
		sort(Eold.begin(),Eold.end());
 
		//for(auto p:Eold)cout<<p.first.first<<" "<<p.first.second<<" "<<p.second.first<<" "<<p.second.second<<endl;		
 
		for(auto p:Eold){
 
			ll a=p.second.first;
			ll b=p.second.second;
			string t=p.first.second;
 
			if(t=="blr"){
				L.erase(L.find(a));
				R.insert(b);
			}
			else if(t=="arl"){
				R.erase(R.find(a));
				L.insert(b);
			}
			else{
				ll x=0,y=0;
				if(!L.empty())
					x=a-*L.begin();
				if(!R.empty())
					y=*R.rbegin()-a;
				ans[b]=max(x,y);
			}
		}
 
		for(int i=0;i<Q;i++)
			cout<<ans[i]/2<<" ";
	}
 
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:100:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<V[i].size()-1;j++)
                ~^~~~~~~~~~~~~~

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