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 |