Pagini recente » Cod sursa (job #2877504) | Cod sursa (job #858792) | Cod sursa (job #713220) | Cod sursa (job #2927469) | Cod sursa (job #35992)
Cod sursa(job #35992)
#include <stdio.h>
#define nmax 500005
FILE *fin, *fout;
long n, k, a[nmax];
void read_data()
{
long i;
fin = fopen("secventa.in", "rt");
fout = fopen("secventa.out", "wt");
fscanf(fin, "%ld %ld", &n, &k);
for (i = 0; i < n; i++)
{
fscanf(fin, "%ld", &a[i]);
}
}
long in, sf, c[nmax];
void solve()
{
long i;
long sm, fm, vm = -30005;
in = 0; sf = 0; c[0] = 0;
for (i = 1; i < n; i++)
{
//introduc a[i] in coada
while ( a[ c[sf] ]> a[i] && sf>=in ) sf--;
sf++;
c[sf] = i;
//scot din coada elementele care nu sunt din [i-k+1, i] => am toate minimile din [i-k+1, i] in coada, sortate
while ( c[in] < i-k+1 ) in++;
//retin noua solutie, daca e mai buna
if ( a[ c[in] ] > vm && i-k+1 >= 0)
{
vm = a[ c[in] ];
sm = i-k+1;
fm = i;
}
}
fprintf(fout, "%ld %ld %ld\n", sm + 1, fm + 1, vm);
}
int main()
{
read_data();
solve();
fclose(fin);
fclose(fout);
return 0;
}