Cod sursa(job #582351)

Utilizator david95szabo david emanuel david95 Data 15 aprilie 2011 11:31:44
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#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;
}
}
 
char sir[1<<22];
 
void read_data(void)
{
int i, ind, x, minus;
 
scanf("%d %d\n", &N, &K);
fgets(sir, 1<<22, stdin);
 
for(ind = 0, i = 1; i <= N; ind++, i++)
{
if(sir[ind] == '-')
{
for(x = 0, ind++; sir[ind] >= '0' && sir[ind] <= '9'; ind++)
x = x*10+(sir[ind]-48);
A[i] = x*(-1);
}
else
{
for(x = 0; sir[ind] >= '0' && sir[ind] <= '9'; ind++)
x = x*10+(sir[ind]-48);
A[i] = x;
}
}
}
 
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;
}