oj.uz

Submission #116902

# Submission time Handle Problem Language Result Execution time Memory
116902 2019-06-14T04:04:16 Z tuanasanh Doktor (COCI17_doktor) C++14
100 / 100
 279 ms 46592 KB 
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef pair<int,int> ii;
ii p;
int n,a[1000005],v[1000005],tmp,pref[1000005],suf[1000005];
vector<int> val[1000005];
int main(){
	ios::sync_with_stdio(false); cin.tie();cout.tie();
	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<1000005;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>tmp){
			tmp=ans;
			p={l,r};
		}
	}
	cout<<v[p.f]<<" "<<v[p.s];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23928 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23808 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23800 KB Output is correct
2 Correct 26 ms 23800 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23936 KB Output is correct
2 Correct 25 ms 23936 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24064 KB Output is correct
2 Correct 26 ms 23936 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23936 KB Output is correct
2 Correct 25 ms 23936 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24192 KB Output is correct
2 Correct 95 ms 30932 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 27384 KB Output is correct
2 Correct 47 ms 26104 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 42868 KB Output is correct
2 Correct 145 ms 33904 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 35064 KB Output is correct
2 Correct 115 ms 46592 KB Output is correct