Cod sursa(job #2038123)

Utilizator ruxi.icleanuRuxandra Icleanu ruxi.icleanu Data 13 octombrie 2017 11:16:50
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <stdlib.h>
#include <stdio.h>
#include <deque>

using namespace std;

#define MAXN 500000
#define INF 30001

int v[MAXN];
deque <int> deq;

int main()
{
    int n, k, i, poz_sf, bmax;
    FILE *fi, *fo;
    fi = fopen("secventa.in", "r");
    fo = fopen("secventa.out", "w");
    fscanf(fi, "%d%d", &n, &k);
    for(i=0; i<n; i++)
        fscanf(fi, "%d", &v[i]);
    bmax=-INF;
    for(i=0; i<n; i++) {
        while(deq.empty()!=1 && v[i]<v[deq.back()])
            deq.pop_back();
        deq.push_back(i);
        if(i-deq.front()>=k) {
            deq.pop_front();
        }
        if(i>=k-1)
            if(v[deq.front()]>bmax) {
                bmax=v[deq.front()];
                //poz_in=deq.front();
                poz_sf=i;
            }
    }
    fprintf(fo, "%d %d %d", poz_sf-k+2, poz_sf+1, bmax);
    fclose(fi);
    fclose(fo);
    return 0;
}