Pagini recente » Cod sursa (job #1647423) | Cod sursa (job #1214660) | Cod sursa (job #1654637) | Cod sursa (job #2447534) | Cod sursa (job #71436)
Cod sursa(job #71436)
#include <cstdio>
#define maxn 500001
FILE *in = fopen("secventa.in","r"), *out = fopen("secventa.out","w");
int n;
int k;
int a[maxn] = {0};
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];
/*
8 3
-1 2 3 1 0 4 8 6
Q: poz v
1 -1
2 2
*/
int main()
{
read();
int first = 1, last = 1;
for ( int i = 1; i <= n; ++i )
{
Q[last].v = a[i];
Q[last++].poz = i;
while ( first <= last && Q[first].poz <= i - k + 1 )
++first;
while ( last >= first && Q[last].v >= a[i] )
--last;
}
//printf("%d %d\n\n\n", first, last);
int min = 100000000;
int start, stop;
for ( int i = 1; i < last; ++i )
if ( Q[i].v < min )
min = Q[i].v, start = Q[i].poz, stop = Q[i].poz + k - 1;
//printf("\n\n");
//for ( int i = 1; i <= n; ++i )
// printf("%d %d\n", Q[i].v, Q[i].poz);
fprintf(out, "%d %d %d\n", start, stop, min);
return 0;
}