Pagini recente » Cod sursa (job #2060784) | Istoria paginii runda/hlo_cj_av_l4/clasament | Cod sursa (job #3129178) | Cod sursa (job #2331137) | Cod sursa (job #71747)
Cod sursa(job #71747)
#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 Qpoz[maxn];
int Qv[maxn];
int main()
{
read();
int first = 1, last = 1;
int max = -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 = 1; i < e; ++i )
{
while ( first < last + 1 && Qpoz[first] < i - k + 1 )
++first;
while ( last > first - 1 && Qv[last] > a[i] - 1 )
--last;
++last;
Qv[last] = a[i];
Qpoz[last] = i;
if ( Qv[first] > max && Qpoz[first] > k - 1 )
max = Qv[first], pmin = Qpoz[first];
// 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 && dr - st < k )
--st;
++st;
while ( a[dr] > p && dr - st < k )
++dr;
--dr;
fprintf(out, "%d %d %d\n", st, dr, max);
return 0;
}