Pagini recente » Cod sursa (job #3351005) | Cod sursa (job #2425626) | Cod sursa (job #2501134) | Cod sursa (job #2422913) | Cod sursa (job #1719670)
#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 + 1;
st[i] = 0;
}
}
void solve()
{
for(int i = 1; i <= n; ++i){
while(!deq.empty() && a[i] <= a[deq.top()]){
dr[deq.top()] = i;
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()]){
st[deq.top()] = i;
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 + 1 << ' ' << Dr - 1 << ' ' << mx;
}
int main()
{
read();
solve();
write();
return 0;
}