Submission #138736

#	Time	Username	Problem	Language	Result	Execution time	Memory
138736		FedericoS	New Home (APIO18_new_home)	C++14	0 / 100	5097 ms	164200 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;
vector<ll> V[300005];
vector<pair<pair<ll,string>,pll> > E;
int ans[300005];

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(false and K<=400){

	}
	else{

		for(int i=0;i<N;i++){
			X[i]*=2;
			P[i]*=2;
		}

		for(int i=0;i<Q;i++)
			E.push_back({{P[i],"q"},{P[i],i}});

		for(int i=0;i<N;i++){
			V[T[i]].push_back(X[i]);
			E.push_back({{X[i],"rl"},{X[i],X[i]}});
		}

		for(int i=0;i<K;i++){
			sort(V[i].begin(),V[i].end());
			for(int j=0;j<V[i].size()-1;j++)
				E.push_back({{(V[i][j]+V[i][j+1])/2,"lr"},{V[i][j],V[i][j+1]}});
		}

		for(int i=0;i<K;i++)
			R.insert(V[i][0]);

		sort(E.begin(),E.end());

		//for(auto p:E)cout<<p.first.first<<" "<<p.first.second<<" "<<p.second.first<<" "<<p.second.second<<endl;		

		for(auto p:E){

			ll a=p.second.first;
			ll b=p.second.second;
			string t=p.first.second;

			if(t=="lr"){
				L.erase(L.find(a));
				R.insert(b);
			}
			else if(t=="rl"){
				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:45:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<V[i].size()-1;j++)
                ~^~~~~~~~~~~~~~

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