Cod sursa(job #2158066)

Utilizator aannddrreeiiandrei aannddrreeii Data 10 martie 2018 10:13:58
Problema Secventa Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.49 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;
// Copright Andrei 2018
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;
}