3100 2023. 02. 15 16:55:45 horvathabel Fasor (40) cpp17 Elfogadva 40/40 199ms 34352 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); 
	int n, k; 
	cin>>n>>k;
	vector<int> fa; 
	map<int, pair<int, int>> indx; 
	for (int i=0; i<n;i++){
		int z;
		cin>>z; 
		fa.push_back(z); 
		if (indx[z].first==0) indx[z].first=i+1;
		indx[z].second=i+1; 
	} 
	indx[-1]={k*-1,k*-1};
	stack<pair<int,int>> b; 
	vector<pair<int,int>> ans(n+1); 
	ans[0]={-1,k*-1};
	for (int i=0; i<n;i++){
		if (b.empty()){
			 b.push({fa[i],i});
			ans[i]={-1, k*-1-1};
		}
		else{
			 if (fa[i]<b.top().first){
				ans[i]=b.top(); 
				b.push({fa[i],i});

			 }
			 else{
				 int cnt=0; 
				 while (!b.empty() && fa[i]>=b.top().first){
					 b.pop();
				 }

				 if (b.empty()) ans[i]={-1,k*-1-1};
				 else ans[i]=b.top(); 
				 b.push({fa[i],i});
				 
			 }
		}
	}
	stack<pair<int,int>> bp; 
	vector<pair<int,int>> ans2(n+1); 
	for (int i=n; i>=0;i--){
		if (bp.empty()){
			 bp.push({fa[i],i});
			
			ans[i]={-1, n+k+1};
		}
		else{
			 if (fa[i]<bp.top().first){
				ans2[i]=bp.top(); 
				bp.push({fa[i],i});

			 }
			 else{
				 while (!bp.empty() && fa[i]>=bp.top().first){
					 bp.pop();
				 }
		
				 if (bp.empty()) ans2[i]={-1,n+k+1};
				 else ans2[i]=bp.top(); 
				 bp.push({fa[i],i});
				 
			 }
		}
	}
	
	for (int i=0; i<n;i++){
		if (ans[i].second+k<i && ans2[i].second-k>i){
			cout<<i+1; 
			return 0; 
		}
	}
	cout<<-1;

}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 40/40
1 Elfogadva 0/0 3ms 1828 KiB
2 Elfogadva 0/0 8ms 3288 KiB
3 Elfogadva 2/2 3ms 2236 KiB
4 Elfogadva 2/2 3ms 2448 KiB
5 Elfogadva 2/2 3ms 2660 KiB
6 Elfogadva 2/2 3ms 2888 KiB
7 Elfogadva 2/2 3ms 2872 KiB
8 Elfogadva 2/2 4ms 3140 KiB
9 Elfogadva 2/2 8ms 4912 KiB
10 Elfogadva 2/2 9ms 4776 KiB
11 Elfogadva 2/2 4ms 3836 KiB
12 Elfogadva 2/2 4ms 3924 KiB
13 Elfogadva 2/2 17ms 7332 KiB
14 Elfogadva 2/2 17ms 7588 KiB
15 Elfogadva 2/2 32ms 11296 KiB
16 Elfogadva 2/2 32ms 11552 KiB
17 Elfogadva 2/2 35ms 11680 KiB
18 Elfogadva 2/2 35ms 11800 KiB
19 Elfogadva 2/2 35ms 11632 KiB
20 Elfogadva 2/2 16ms 8140 KiB
21 Elfogadva 2/2 32ms 11984 KiB
22 Elfogadva 2/2 199ms 34352 KiB