Submission #138748

#	Time	Username	Problem	Language	Result	Execution time	Memory
138748		FedericoS	New Home (APIO18_new_home)	C++14	10 / 100	1934 ms	102308 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;
		for(int i=0;i<Q;i++)
			P[i]*=2;

		for(int i=0;i<Q;i++)
			E.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])
				E.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])
					E.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(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=="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:60: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: 10 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20