Submission #51689

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
51689	2018-06-20T03:02:46 Z	zetapi	New Home (APIO18_new_home)	C++14	10 / 100	1204 ms	173236 KB

new_home

#include <bits/stdc++.h>
using namespace std;
 
#define pb  push_back
#define mp  make_pair
#define int long long
#define itr ::iterator 
 
typedef pair<int,int>  pii;
 
const int MAX=5e5;
const int INF=1e8;
 
vector<int> fst_,sec_,vec[MAX];
vector<pii> fst,sec,increasing,decreasing;
 
int N,K,Q,X,Y,Z,l,r,pre,res,Begin,End;
 
bool cmp(pii X,pii Y)
{
	return X.first<Y.first;
}
 
signed main()
{
	ios_base::sync_with_stdio(false);
	/*cin.tie(0);
	cout.tie(0);*/
 
 	Begin=0;
 	End=INF;
	cin>>N>>K>>Q;
	for(int A=1;A<=N;A++)
	{
		cin>>X>>Y>>Z>>Z;
		vec[Y].pb(X);
	}
	for(int A=1;A<=K;A++)
	{
		if(vec[A].empty())
		{
			while(Q--)
				cout<<-1<<"\n";
			return 0;
		}
		sort(vec[A].begin(),vec[A].end());
		for(int B=1;B<vec[A].size();B++)
			increasing.pb(mp(vec[A][B-1],(vec[A][B-1]+vec[A][B])/2));
		for(int B=vec[A].size()-2;B>=0;B--)
			decreasing.pb(mp(vec[A][B+1],(vec[A][B+1]+vec[A][B]+1)/2));		
		increasing.pb(mp(vec[A].back(),INF));
		decreasing.pb(mp(*vec[A].begin(),0));
		Begin=max(Begin,*vec[A].begin());
		End=min(End,vec[A].back());
	}
	sort(increasing.begin(),increasing.end());
	sort(decreasing.begin(),decreasing.end());
	for(int A=0;A<increasing.size();A++)
	{
		l=max(pre+1,increasing[A].first);
		r=increasing[A].second;
		if(l>r)
			continue;
		fst.pb(mp(l,r));
		fst_.pb(increasing[A].first);
		pre=r;
	}
	pre=INF+99;
	for(int A=decreasing.size()-1;A>=0;A--)
	{
		l=min(pre-1,decreasing[A].first);
		r=decreasing[A].second;
		if(l<r)
			continue;
		sec.pb(mp(r,l));
		sec_.pb(decreasing[A].first);
		pre=r;
	}
	reverse(sec.begin(),sec.end());
	reverse(sec_.begin(),sec_.end());
	/*for(auto A:fst)
		cout<<A.first<<" fst "<<A.second<<"\n";
	for(auto A:sec)
		cout<<A.first<<" sec "<<A.second<<"\n";*/
	while(Q--)
	{
		res=0;
		cin>>X>>Y;
		/*if(X<Begin)
		{
			cout<<Begin-X<<"\n";
			continue;
		}
		else if(X>End)
		{
			cout<<X-End<<"\n";
			continue;
		}*/
		int low=0,high=fst.size()-1,mid;
		while(low<=high)
		{
			mid=(low+high)/2;
			if(fst[mid].first<=X and fst[mid].second>=X)
			{
				res=max(res,abs(X-fst_[mid]));
				break;
			}
			else if(fst[mid].second<X)
				low=mid+1;
			else if(fst[mid].first>X)
				high=mid-1;
		}
		low=0,high=sec.size()-1;
		while(low<=high)
		{
			mid=(low+high)/2;
			if(sec[mid].first<=X and sec[mid].second>=X)
			{
				res=max(res,abs(sec_[mid]-X));
				break;
			}
			else if(sec[mid].second<X)
				low=mid+1;
			else if(sec[mid].first>X)
				high=mid-1;
		}
		cout<<res<<"\n";
	}
	return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:47:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int B=1;B<vec[A].size();B++)
               ~^~~~~~~~~~~~~~
new_home.cpp:58:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int A=0;A<increasing.size();A++)
              ~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	12084 KB	Output is correct
2	Incorrect	14 ms	12276 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	12084 KB	Output is correct
2	Incorrect	14 ms	12276 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	972 ms	29316 KB	Output is correct
2	Correct	1032 ms	41664 KB	Output is correct
3	Correct	996 ms	60564 KB	Output is correct
4	Correct	1058 ms	69780 KB	Output is correct
5	Correct	1204 ms	99484 KB	Output is correct
6	Correct	1103 ms	99484 KB	Output is correct
7	Correct	931 ms	113152 KB	Output is correct
8	Correct	873 ms	121572 KB	Output is correct
9	Correct	836 ms	134744 KB	Output is correct
10	Correct	875 ms	146768 KB	Output is correct
11	Correct	938 ms	159296 KB	Output is correct
12	Correct	896 ms	172268 KB	Output is correct