Submission #138736

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
138736	2019-07-30T09:23:04 Z	FedericoS	New Home (APIO18_new_home)	C++14	0 / 100	5000 ms	164200 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	5097 ms	7416 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	5097 ms	7416 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1964 ms	96316 KB	Output is correct
2	Runtime error	1469 ms	164200 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Halted	0 ms	0 KB	-