oj.uz

Submission #51204

# Submission time Handle Problem Language Result Execution time Memory
51204 2018-06-17T08:22:56 Z zetapi New Home (APIO18_new_home) C++14
0 / 100
 5000 ms 800356 KB 
#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> vec[MAX];
vector<pii> increasing,decreasing;

int N,K,Q,X,Y,Z,l,r,pre,res[INF+9];

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);*/

	for(int A=1;A<=INF;A++)
		res[A]=-1;
	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())
			continue;
		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));		
		for(int B=vec[A][0],C=0;B>=0;B--,C++)
			res[B]=max(res[B],C);
		for(int B=vec[A].back(),C=0;B<=INF;B++,C++)
			res[B]=max(res[B],C);
	}
	sort(increasing.begin(),increasing.end());
	sort(decreasing.begin(),decreasing.end(),cmp);
	/*for(auto A:increasing)
		cout<<A.first<<" inc "<<A.second<<"\n";
	for(auto A:decreasing)
		cout<<A.first<<" dec "<<A.second<<"\n";*/
	for(int A=0;A<increasing.size();A++)
	{
		l=max(pre+1,increasing[A].first);
		r=increasing[A].second;
		for(int B=l,C=l-increasing[A].first;B<=r;B++,C++)
			res[B]=max(res[B],C);
	}
	pre=INF+99;
	for(int A=decreasing.size()-1;A>=0;A--)
	{
		l=min(pre-1,decreasing[A].first);
		r=decreasing[A].second;
		for(int B=l,C=decreasing[A].first-l;B>=r;B--,C++)
			res[B]=max(res[B],C);
	}
	while(Q--)
	{
		cin>>X>>Y;
		cout<<res[Y]<<"\n";
	}
	return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:43: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 2163 ms 795008 KB Output is correct
2 Incorrect 2105 ms 795056 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2163 ms 795008 KB Output is correct
2 Incorrect 2105 ms 795056 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2163 ms 795008 KB Output is correct
2 Incorrect 2105 ms 795056 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2163 ms 795008 KB Output is correct
2 Incorrect 2105 ms 795056 KB Output isn't correct
3 Halted 0 ms 0 KB -