3102 | 2023. 02. 15 17:08:08 | horvathabel | Fasor (40) | cpp17 | Elfogadva 40/40 | 37ms | 11588 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);
}
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 | 1824 KiB | |||
2 | Elfogadva | 0/0 | 4ms | 2528 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2252 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2460 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2676 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 2884 KiB | |||
7 | Elfogadva | 2/2 | 3ms | 3248 KiB | |||
8 | Elfogadva | 2/2 | 3ms | 3232 KiB | |||
9 | Elfogadva | 2/2 | 4ms | 3724 KiB | |||
10 | Elfogadva | 2/2 | 4ms | 3680 KiB | |||
11 | Elfogadva | 2/2 | 4ms | 3808 KiB | |||
12 | Elfogadva | 2/2 | 4ms | 3892 KiB | |||
13 | Elfogadva | 2/2 | 17ms | 7380 KiB | |||
14 | Elfogadva | 2/2 | 17ms | 7372 KiB | |||
15 | Elfogadva | 2/2 | 30ms | 11260 KiB | |||
16 | Elfogadva | 2/2 | 32ms | 11136 KiB | |||
17 | Elfogadva | 2/2 | 34ms | 11256 KiB | |||
18 | Elfogadva | 2/2 | 34ms | 11136 KiB | |||
19 | Elfogadva | 2/2 | 34ms | 11260 KiB | |||
20 | Elfogadva | 2/2 | 14ms | 7636 KiB | |||
21 | Elfogadva | 2/2 | 30ms | 11472 KiB | |||
22 | Elfogadva | 2/2 | 37ms | 11588 KiB |