Pagini recente » Cod sursa (job #476934) | Cod sursa (job #1206170) | Cod sursa (job #678825) | Cod sursa (job #2169671) | Cod sursa (job #1780)
Cod sursa(job #1780)
#include <stdio.h>
#define MAXN (1 << 19)
#define min(a,b) ((a) < (b) ? (a) : (b))
int N, K;
int A[MAXN], Q[MAXN], poz[MAXN];
int best = - (1 << 30), pi, pf;
void solve(void)
{
int i, inc = 1, sf = 1, baza;
Q[1] = A[1], poz[1] = 1;
for(i = 2; i <= K-1; i++)
{
while(A[i] <= Q[sf] && sf > 0) sf--;
Q[++sf] = A[i], poz[sf] = i;
}
for(i = K; i <= N; i++)
{
while(i - poz[inc] >= K) inc++;
baza = min(A[i], Q[inc]);
if(baza > best) best = baza, pi = i-K+1, pf = i;
while(A[i] <= Q[sf] && sf > 0) sf--;
Q[++sf] = A[i], poz[sf] = i;
if(inc > sf) inc = sf;
}
}
void read_data(void)
{
int i;
scanf("%d %d\n", &N, &K);
for(i = 1; i <= N; i++)
scanf("%d ", &A[i]);
}
void write_data(void)
{
printf("%d %d %d\n", pi, pf, best);
}
int main(void)
{
freopen("secventa.in", "rt", stdin);
freopen("secventa.out", "wt", stdout);
read_data();
solve();
write_data();
return 0;
}