Pagini recente » Atasamentele paginii Clasament cerculdeinfo-lectia14-cautare_binara | Cod sursa (job #2103784) | Cod sursa (job #306687) | Profil M@2Te4i | Cod sursa (job #71491)
Cod sursa(job #71491)
#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];
int main()
{
read();
int first = 1, last = 0;
// Q[first].v = a[1];
// Q[first].poz = 1;
int max = -300000000;
//int min = 300000000;
int pmin = 0;
for ( int i = 1; i <= n; ++i )
{
while ( first <= last && i - Q[first].poz >= k )
++first;
while ( last >= first && Q[last].v >= a[i] )
--last;
if ( Q[first].v > max )
max = Q[first].v, pmin = Q[first].poz;
++last;
Q[last].v = a[i];
Q[last].poz = i;
// for ( int i = first; i <= last; ++i )
// printf("%d ", Q[i].v);
// printf("\n");
}
// printf("%d %d\n\n", first, last);
int st = pmin - k + 1;
int dr = pmin + k - 1;
for ( int i = pmin; i >= st && i; --i )
if ( a[i] < max )
{
st = 0;
break;
}
for ( int i = pmin; i <= dr && i <= n; ++i )
if ( a[i] < max )
{
dr = 0;
break;
}
if ( st )
fprintf(out, "%d %d %d\n", st, pmin, max);
else
fprintf(out, "%d %d %d\n", pmin, dr, max);
// int min = 100000000;
// int start = 0, stop = 0;
// 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;
//
// for ( int i = 1; i <= n; ++i )
// printf("%d %d\n", Q[i].v, Q[i].poz);
//
// printf("\n");
//
// fprintf(stdout, "%d %d %d\n", start, stop, min);
return 0;
}