Pagini recente » Cod sursa (job #812204) | Cod sursa (job #2427672) | Cod sursa (job #2917987) | Cod sursa (job #2758878) | Cod sursa (job #1719667)
#include <iostream>
#include <fstream>
#include <stack>
#define nMax 500005
using namespace std;
int n, a[nMax], k, st[nMax], dr[nMax], mx, Dr, St;
stack <int> deq;
void read()
{
ifstream fin("secventa.in");
fin >> n >> k;
for(int i = 1; i <= n; ++i){
fin >> a[i];
dr[i] = n;
st[i] = 1;
}
}
void solve()
{
for(int i = 1; i <= n; ++i){
while(!deq.empty() && a[i] < a[deq.top()]){
if(dr[deq.top()] == n)dr[deq.top()] = i - 1;
deq.pop();
}
deq.push(i);
}
while(!deq.empty())
deq.pop();
for(int i = n; i >= 1; --i){
while(!deq.empty() && a[i] < a[deq.top()]){
if(st[deq.top()] == 1)st[deq.top()] = i + 1;
deq.pop();
}
deq.push(i);
}
for(int i = 1; i <= n; ++i){
if(dr[i] - st[i] + 1 >= k){
if(a[i] > mx) mx = a[i], St = st[i], Dr = dr[i];
else if(a[i] == mx){
if(st[i] < St) St = st[i], Dr = dr[i];
else if(st[i] == St && dr[i] > Dr) Dr = dr[i];
}
}
}
}
void write()
{
ofstream fout("secventa.out");
fout << St << ' ' << Dr << ' ' << mx;
}
int main()
{
read();
solve();
write();
return 0;
}