1484 2022. 11. 13 21:09:11 tomi7 Völgy (100 pont) cpp11 Elfogadva 100/100 39ms 6344 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin>>n;
	vector<int> a(n);
	vector<int> jobb(n);
	vector<int> bal(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int legnagyobb=-1;
    jobb[n-1]=-1;
	bal[0]=-1;
	for(int i=1;i<n;i++){ 
		for(int j=i-1;1;){ 
		    if(a[i]>a[j]){
			     if(bal[j]==-1){
				     bal[i]=-1;  
					 break;
			     }
			     if(bal[j]!=-1){
				     j=bal[j];
			     }
		    }else{
				bal[i]=j;
				if(i-j>1){
			         legnagyobb=max(i-j, legnagyobb);
				}   
				break;
			}
	    }
	}

	for(int i=n-2;i>=0;i--){
		for(int j=i+1;1;){
	//		cout << "Uj j " << j << '\n';
		    if(a[i]>a[j]){
			     if(jobb[j]==-1){
				     jobb[i]=-1;
	//				 cout << "Elso if : a[i]: " << a[i] << " a[j]: " << a[j] << " jobb[i]: " << jobb[i] << '\n';
					 break;
			     }
			     if(bal[j]!=-1){
				     j=jobb[j];
	//				 cout << "Masodik if : a[i]: " << a[i] << " a[j]: " << a[j] << " jobb[i]: " << jobb[i] << '\n';
			     }
		    }else{
				jobb[i]=j;
				if(j-i>1){
			         legnagyobb=max(j-i, legnagyobb);
				}
	//			cout << "Else : a[i]: " << a[i] << " a[j]: " << a[j] << " jobb[i]: " << jobb[i] << '\n';
				break;
			}
	    }
	}
	cout<<legnagyobb<<'\n';





	
	







	//for(int i=0; i<n; i++) {
	//	cout<<"BAL"<<bal[i]<<" ";
//	}
//	cout<<endl;
//	for(int i=0; i<n; i++) {
//		cout<<"JOBB"<<jobb[i]<<" ";
//	}
//	cout<<endl;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 100/100
1 Elfogadva 0/0 3ms 1684 KiB
2 Elfogadva 0/0 2ms 1936 KiB
3 Elfogadva 5/5 2ms 2052 KiB
4 Elfogadva 5/5 2ms 2260 KiB
5 Elfogadva 5/5 2ms 2324 KiB
6 Elfogadva 5/5 2ms 2576 KiB
7 Elfogadva 5/5 2ms 2776 KiB
8 Elfogadva 5/5 2ms 2868 KiB
9 Elfogadva 5/5 2ms 3080 KiB
10 Elfogadva 5/5 2ms 3288 KiB
11 Elfogadva 5/5 4ms 3408 KiB
12 Elfogadva 5/5 4ms 3780 KiB
13 Elfogadva 5/5 4ms 3728 KiB
14 Elfogadva 5/5 6ms 3732 KiB
15 Elfogadva 5/5 34ms 5884 KiB
16 Elfogadva 5/5 37ms 5880 KiB
17 Elfogadva 5/5 35ms 5820 KiB
18 Elfogadva 5/5 35ms 5820 KiB
19 Elfogadva 5/5 35ms 5824 KiB
20 Elfogadva 5/5 39ms 6100 KiB
21 Elfogadva 5/5 39ms 6160 KiB
22 Elfogadva 5/5 39ms 6344 KiB