Cod sursa(job #2291312)

Utilizator radugheoRadu Mihai Gheorghe radugheo Data 27 noiembrie 2018 21:25:32
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <cstdio>
#include <limits.h>
#define DIMBUFF 100005

using namespace std;

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

int n, k, i, maxim, poz1, poz2, v[500001], u, p, d[500001];
char buff[DIMBUFF];
int pp;

int numar() {
    int val = 0;
    while (!((buff[pp] >= '0' && buff[pp] <= '9')||buff[pp]=='-')) {
        pp++;
        if (pp == DIMBUFF) {
            fread(buff, 1, DIMBUFF, fin);
            pp = 0;
        }
    }
    int ok = 1;
    if(buff[pp] == '-'){
        ok = -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 ok*val;
}

int main()
{
    n = numar();
    k = numar();
    for (i=1; i<=n; i++){
        v[i] = numar();
    }
    maxim = INT_MIN;
    for (i=2; i<=n; i++){
        while (v[i] < v[d[u]] && p <= u){
            u--;
        }
        u++;
        d[u] = i;
        if (i - d[p] == k){
            p++;
        }
        if (i >= k){
            if (maxim < v[d[p]]){
                maxim = v[d[p]];
                poz1 = i;
            }
        }
    }

    fprintf(fout, "%d %d %d", poz1 - k + 1, poz1, maxim);
    return 0;
}