oj.uz

Submission #797093

# Submission time Handle Problem Language Result Execution time Memory
797093 2023-07-29T06:27:23 Z Trisanu_Das Doktor (COCI17_doktor) C++17
100 / 100
 148 ms 49620 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23804 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23860 KB Output is correct
2 Correct 14 ms 23764 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23824 KB Output is correct
2 Correct 15 ms 23852 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23968 KB Output is correct
2 Correct 14 ms 23948 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23948 KB Output is correct
2 Correct 15 ms 23820 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24212 KB Output is correct
2 Correct 68 ms 32648 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 27760 KB Output is correct
2 Correct 32 ms 26580 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 45956 KB Output is correct
2 Correct 103 ms 37064 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 36860 KB Output is correct
2 Correct 69 ms 49620 KB Output is correct