oj.uz

Submission #237919

# Submission time Handle Problem Language Result Execution time Memory
237919 2020-06-09T10:07:25 Z MrRobot_28 Doktor (COCI17_doktor) C++17
100 / 100
 733 ms 52568 KB 
#include<bits/stdc++.h>
using namespace std;

bool cmp(pair <pair <int, int>, pair <int, int> > a, pair <pair <int, int>, pair <int, int> > b)
{
	return a.second.second - a.first.second < b.second.second - b.first.second; 
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	vector <int> a(n);
	set <pair <pair <int, int>, pair <int, int> > > st;
	vector <int> cnt1(n), cnt2(n);
	vector <pair <pair <int, int>, pair <int, int> > > vec;
	vector <int> pref(n);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
		a[i]--;
		if(i == a[i])
		{
			pref[i]++;
		}
		if(i != 0)
		{
			pref[i] += pref[i - 1];
		}
		int len = fabs(a[i] - i) + 1;
		int l = i, r = a[i];
		if(l > r)
		{
			swap(l, r);
		}
		if(len % 2 == 0)
		{
			vec.push_back({{l + len / 2 - 1, 0}, {l, r}});
		}
		else
		{
			vec.push_back({{l + len / 2, 1}, {l, r}});
		}
	}
	sort(vec.begin(), vec.end(), cmp);
	vector <int> add(vec.size());
	for(int i = 0; i < vec.size(); i++)
	{
		set <pair <pair <int, int>, pair <int, int> > > :: iterator it;
		it = st.lower_bound({vec[i].first, {vec[i].second.first, 0}});
		if(it != st.end() && it -> first == vec[i].first)
		{
			add[i] += add[it -> second.second];
		}
		add[i]++;
		st.insert({vec[i].first, {vec[i].second.first, i}});
	}
	int ans = 0, ansl = a[0], ansr = a[0];
	for(int i = 0; i < vec.size(); i++)
	{
		int l = vec[i].second.first;
		int r = vec[i].second.second;
		int val = add[i];
		if(l != 0)
		{
			val += pref[l - 1];
		}
		val -= pref[r];
		if((r - l + 1) % 2 == 1 && a[(r + l) / 2] == (r + l) / 2)
		{
			val++;
		}
		if(val > ans)
		{
			ans = val;
			ansl = a[l];
			ansr = a[r];
		}
	}
	cout << ansl + 1 << " " << ansr + 1;
	return 0;
}

Compilation message

doktor.cpp: In function 'int main()':
doktor.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < vec.size(); i++)
                 ~~^~~~~~~~~~~~
doktor.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < vec.size(); i++)
                 ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 768 KB Output is correct
2 Correct 6 ms 640 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 840 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1408 KB Output is correct
2 Correct 238 ms 31588 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 9696 KB Output is correct
2 Correct 77 ms 10732 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 733 ms 51616 KB Output is correct
2 Correct 422 ms 52568 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 30296 KB Output is correct
2 Correct 302 ms 50908 KB Output is correct