Pagini recente » Cod sursa (job #1972486) | Cod sursa (job #616383) | Cod sursa (job #1997741) | Cod sursa (job #1240476) | Cod sursa (job #71739)
Cod sursa(job #71739)
#include <cstdio>
#include <cstring>
#define maxn 500001
FILE *in = fopen("secventa.in","r"), *out = fopen("secventa.out","w");
int n;
int k;
int a[maxn] = {0};
char buf[10000];
void read()
{
fscanf(in, "%d %d", &n, &k);
for ( int i = 1; i <= n; ++i )
fscanf(in, "%d", &a[i]);
}
struct deque
{
int poz, v;
};
deque Q[maxn];
int main()
{
read();
int first = 1, last = 1;
// Q[first].v = a[1];
// Q[first].poz = 1;
int max = -300000000;
//int min = 300000000;
int pmin = 0;
int pmin2 = 0;
int e = n + 1;
int min = 300000000;
for ( int i = 1; i < k + 1; ++i )
if ( a[i] < min )
min = a[i], pmin2 = i;
if ( min > max )
max = min, pmin = pmin2;
for ( int i = k; 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;
}