Pagini recente » Cod sursa (job #1235673) | Cod sursa (job #1173381) | Cod sursa (job #2371156) | Cod sursa (job #2986172) | Cod sursa (job #71812)
Cod sursa(job #71812)
#include <cstdio>
#include <cstring>
#define maxn 500001
FILE *in = fopen("secventa.in","r"), *out = fopen("secventa.out","w");
int n;
int k;
int e;
int a[maxn] = {0};
void read()
{
fscanf(in, "%d %d", &n, &k);
e = n + 1;
for ( int i = 1; i < e; ++i )
fscanf(in, "%d", &a[i]);
}
struct deque
{
int poz, v;
};
deque Q[maxn];
int main()
{
read();
int first = 1, last = 1;
int max = -3000000;
int pmin = 0;
int min = 3000000;
for ( int i = 1; i < k + 1; ++i )
if ( a[i] < min )
min = a[i], pmin = i;
max = min;
for ( int i = 1; i < e; ++i )
{
while ( first <= last + 1 && Q[first].poz < i - k + 1 )
++first;
while ( last >= first - 1 && Q[last].v > a[i] - 1 )
--last;
++last;
Q[last].v = a[i];
Q[last].poz = i;
if ( Q[first].v > max && Q[first].poz > k - 1 )
max = Q[first].v, pmin = Q[first].poz;
// for ( int j = first; j <= last; ++j )
// printf("%d ", Q[j].v);
// printf("\n");
}
int st = pmin;
int dr = pmin;
int p = max - 1;
while ( a[st] > p && st )
--st;
++st;
while ( a[dr] > p && dr - st < k )
++dr;
--dr;
fprintf(out, "%d %d %d\n", st, dr, max);
return 0;
}