Pagini recente » Cod sursa (job #2884184) | Cod sursa (job #2949653) | Cod sursa (job #2511941) | Istoria paginii runda/emag_2016-incepatori-3/clasament | Cod sursa (job #2767683)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int n, k;
int v[500500];
int dq[500500];
int lg[500500];
int dreapta[500500];
int stanga[500500];
int st = 0, dr = -1;
int main()
{
fin >> n >> k;
for(int i = 1; i <= n; i ++)
{
fin >> v[i];
}
v[n + 1] = -33333;
for(int i = 1; i <= n + 1; i ++)
{
while(st <= dr && v[dq[dr]] > v[i])
{
dreapta[dq[dr]] = i - 1;
dr--;
}
dq[++dr] = i;
}
v[0] = -33333;
st = 0;
dr = -1;
for(int i = n; i >= 0; i --)
{
while(st <= dr && v[dq[dr]] > v[i])
{
stanga[dq[dr]] = i + 1;
dr--;
}
dq[++dr] = i;
}
int minim = 0;
int posdr = 0, posst = 0;
for(int i = 1; i <= n; i ++)
{
if(stanga[i] && dreapta[i] && dreapta[i] - stanga[i] + 1 >= k)
{
if(v[i] > minim)
{
minim = v[i];
posst = stanga[i];
posdr = dreapta[i];
}
}
}
fout << posst << ' ' << posdr << ' ' << minim << '\n';
return 0;
}