Cod sursa(job #1808250)

Utilizator blackmanta45Andrei blackmanta45 Data 17 noiembrie 2016 16:04:26
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <cstdio>
#include <cstring>
#define DIMBUFF 500000
using namespace std;
FILE *fin  = fopen("secventa.in", "r");
FILE *fout = fopen("secventa.out","w");
short v[500010],minim=-31000,j,nr;
int semn;
int n,k,i,D[500010],pozj,p,u,pozi,m,val;

char buff[DIMBUFF];
int pp;

int numar() {
    int val = 0, semn = 1;
    while (!(buff[pp] >= '0' && buff[pp] <= '9')) {
        pp++;
        if (pp == DIMBUFF) {
            fread(buff, 1, DIMBUFF, fin);
            pp=0;
        }

    }
    if (buff[pp] == '+' || buff[pp] == '-') {
        if (buff[pp] == '-')
            semn = -1;
        pp++;
        if (pp == DIMBUFF) {
            fread(buff, 1, DIMBUFF, fin);
            pp=0;
        }

    }
    while (buff[pp] >= '0' && buff[pp] <= '9') {
        val = val*10 + buff[pp] - '0';
        pp++;
        if (pp == DIMBUFF) {
            fread(buff, 1, DIMBUFF, fin);
            pp=0;
        }
    }
    return val;
}


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

    for (i=1;i<=n;i++)
        v[i] = numar();
    p=1;
    u=1;
    D[1]=1;
    for(i=2;i<=n;i++){
        while(v[i]<=v[D[u]] && p<=u)
            u--;
        D[++u]=i;
        if(i-D[p]>=k)
            p++;
        if(i>=k && v[D[p]]>minim){
            minim=v[D[p]];
            pozi=i-k+1;
            pozj=i;
        }

    }
    fprintf(fout, "%d %d %d", pozi, pozj, minim);

}