Submission #138748

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
138748	2019-07-30T09:42:08 Z	FedericoS	New Home (APIO18_new_home)	C++14	10 / 100	1934 ms	102308 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;
		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

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	7420 KB	Output is correct
2	Incorrect	8 ms	7416 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	7420 KB	Output is correct
2	Incorrect	8 ms	7416 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1904 ms	83640 KB	Output is correct
2	Correct	1515 ms	81944 KB	Output is correct
3	Correct	1910 ms	102308 KB	Output is correct
4	Correct	1892 ms	97604 KB	Output is correct
5	Correct	1475 ms	98076 KB	Output is correct
6	Correct	1518 ms	94640 KB	Output is correct
7	Correct	1780 ms	102232 KB	Output is correct
8	Correct	1934 ms	96772 KB	Output is correct
9	Correct	1820 ms	96004 KB	Output is correct
10	Correct	1644 ms	95444 KB	Output is correct
11	Correct	1557 ms	94296 KB	Output is correct
12	Correct	1601 ms	95348 KB	Output is correct