Pagini recente » Cod sursa (job #736417) | Cod sursa (job #1097660) | Cod sursa (job #1209339) | Cod sursa (job #1916183) | Cod sursa (job #2210360)
#include <bits/stdc++.h>
using namespace std;
ifstream in("secventa.in");
ofstream out("secventa.out");
int const NMAX=500000+10;
int v[NMAX], st[NMAX], sf[NMAX];
stack<int> stiva;
int n;
template <class T>
void clstack(stack<T>& stiva){
while (!stiva.empty()) stiva.pop();
}
void calcst(){
v[0]=-1e5;
clstack(stiva);
stiva.push(0);
for (int i=1; i<=n; i++){
while (v[stiva.top()]>=v[i])
stiva.pop();
st[i]=stiva.top()+1;
stiva.push(i);
}
}
void calcsf(){
v[0]=-1e5;
clstack(stiva);
stiva.push(0);
for (int i=1; i<=n; i++){
while (v[stiva.top()]>v[i]){
sf[stiva.top()]=i-1;
stiva.pop();
}
stiva.push(i);
}
while (v[stiva.top()]>-1e5){
sf[stiva.top()]=n;
stiva.pop();
}
}
int lsecv(int x){
return sf[x]-st[x]+1;
}
int main(){
int k, valmax=-1e5, stmax, sfmax;
in >> n >> k;
for (int i=1; i<=n; i++)
in >> v[i];
calcsf();
calcst();
// for (int i=1; i<=n; i++)
// cout << st[i] << ' ' << sf[i] << "\n";
for (int i=1; i<=n; i++){
if (lsecv(i)<k) continue;
if (v[i]>valmax){
valmax=v[i];
stmax=st[i];
sfmax=(i-st[i]+1>=k) ? i : k+st[i]-1;
}
else if (v[i]==valmax){
if (st[i]<stmax){
valmax=v[i];
stmax=st[i];
sfmax=(i-st[i]+1>=k) ? i : k+st[i]-1;
}
}
}
out << stmax << ' ' << sfmax << ' ' << valmax;
}