Cod sursa(job #1678716)

Utilizator preda.andreiPreda Andrei preda.andrei Data 7 aprilie 2016 15:10:07
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N_MAX = 500000;

int v[N_MAX + 1];
int deq[N_MAX + 1];
int stdeq, drdeq;

int main()
{
    FILE *fin = fopen("secventa.in", "r");
    FILE *fout = fopen("secventa.out", "w");

    int n, k, maxi = 0, pozStart, pozFinal;

    fscanf(fin, "%d%d", &n, &k);

    for(int i = 1; i <= n; ++i)
        deq[i] = 500000;

    stdeq = 1;
    drdeq = 0;
    for(int i = 1; i<= n; ++i){
        fscanf(fin, "%d", &v[i]);

        while(drdeq >= stdeq && v[i] <= v[deq[drdeq]])
            --drdeq;
        deq[++drdeq] = i;

        while(i - deq[stdeq] >= k && deq[stdeq] != -50000)
            ++stdeq;

        /*printf("st = %d  dr = %d\n", stdeq, drdeq);
        for(int z = stdeq; z <= drdeq; ++z)
            printf("%d ", v[deq[z]]);
        printf("\n");*/

        if(v[deq[stdeq]] > maxi){
            pozStart = i - k + 1;
            pozFinal = i;
            maxi = v[deq[stdeq]];
        }
    }

    fprintf(fout, "%d %d %d", pozStart, pozFinal, maxi);
    return 0;
}