Pagini recente » Cod sursa (job #901546) | Cod sursa (job #2426302) | Cod sursa (job #508650) | Cod sursa (job #1216069) | Cod sursa (job #750226)
Cod sursa(job #750226)
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("secventa.in");
ofstream out("secventa.out");
int a[500010], q[500010];
int N, k, i, st, dr, rez, poz;
int main()
{
in >> N >> k;
for(i = 1; i <= N; ++i)
in >> a[i];
rez = ~(1 << 30);
st = 1, dr = 0;
for(i = 1; i <= k - 1; ++i){
while((st <= dr) && (a[i] <= a[ q[dr] ])) dr--;
dr++;
q[dr] = i;
}
for(i = k; i <= N; ++i){
while((st <= dr) && (a[i] <= a[ q[dr] ])) dr--;
dr++;
q[dr] = i;
while((st <= dr) && (q[st] < (i - k + 1))) st++;
if(a[ q[st] ] > rez){
rez = a[ q[st] ];
poz = i;
}
}
out << poz - k + 1 << " " << poz << " " << rez;
return 0;
}