Submission #82274

#	Time	Username	Problem	Language	Result	Execution time	Memory
82274		MatheusLealV	Doktor (COCI17_doktor)	C++17	100 / 100	312 ms	57116 KiB

doktor

#include <bits/stdc++.h>
#define N 1000010
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

pii O;

int n, a[N], v[N], opt, pref[N], suf[N];

vector<int> val[N];

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n;

	for(int i = 1; i <= n; i++)
	{
		cin>>v[i];

		a[v[i]] = i;

		pref[i] = pref[i - 1] + (v[i] == i);
	}

	for(int i = n; i >= 1; i--) suf[i] = suf[i + 1] + (v[i] == i);

	for(int i = 1; i <= n; i++) val[i + a[i]].push_back(i);

	for(int i = 1; i < N; i++) sort(val[i].begin(), val[i].end());

	for(int i = 1; i <= n; i++)
	{
		int L = min(i, a[i]), R = max(i, a[i]);

		int ans = upper_bound(val[i + a[i]].begin(), val[i + a[i]].end(), R) - lower_bound(val[i + a[i]].begin(), val[i + a[i]].end(), L) + suf[R + 1] + pref[L - 1];

		if(ans > opt) opt = ans, O = {L, R};
	}

	cout<<v[O.f]<<" "<<v[O.s]<<"\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10