Cod sursa(job #1890061)

Utilizator raluca1234Tudor Raluca raluca1234 Data 23 februarie 2017 00:51:46
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <cstdio>
#include <deque>
/*
#include <cctype>
#include <cstring>

#define BUF_SIZE (1<<17)
*/
#define INF 0x3f3f3f3f
#define maxN 500000

using namespace std;
/*
char buf[BUF_SIZE];
int pos=BUF_SIZE;

inline char getChar(FILE *f){
    if (pos==BUF_SIZE){
        pos=0;
        fread(buf, 1, BUF_SIZE, f);
    }
    return buf[pos++];
}

inline int getInt(FILE *f){
    int nr=0, sign=1;
    char c;
    c=getChar(f);
    while (!isdigit(c) && c!='-') c=getChar(f);
    if (c=='-'){
        sign=-1;
        c=getChar(f);
    }
    while (isdigit(c)){
        nr=nr*10+c-'0';
        c=getChar(f);
    }
    nr=nr*sign;
    return nr;
}
*/
int v[maxN+1];
deque <int> d;

int main(){
    FILE *fin, *fout;
    fin=fopen("secventa.in", "r");
    fout=fopen("secventa.out", "w");
    int N, K, i, bmax, left, right;
    //N=getInt(fin);
    //K=getInt(fin);
    fscanf(fin, "%d%d", &N, &K);
    for (i=1; i<=N; i++)
        //v[i]=getInt(fin);
        fscanf(fin, "%d", &v[i]);
    bmax=-INF;
    for (i=1; i<=N; i++){
        if (!d.empty() && v[i]<=v[d.back()])
            d.pop_back();
        d.push_back(i);
        if (d.front()==i-K)
            d.pop_front();
        if (i>=K && v[d.front()]>bmax){
            bmax=v[d.front()];
            left=i-K+1;
            right=i;
        }
    }
    fprintf(fout, "%d %d %d\n", left, right, bmax);
    fclose(fin);
    fclose(fout);
    return 0;
}