Cod sursa(job #1753031)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 5 septembrie 2016 18:37:09
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<fstream>
#include<cstdio>
#define DIM 500005
#define DIM1 1000000
using namespace std;
int n, k, i, sol, p, u, ii, r;
int v[DIM], d[DIM];
char s[DIM1 + 5];
FILE * fin = fopen("secventa.in", "r");
FILE * fout = fopen("secventa.out", "w");
int num(){
    while( (s[r] < '0' || s[r] > '9') && s[r] != '-'){
        r++;
        if(r == DIM1){
            r = 0;
            fread(s, 1, DIM1, fin);
        }
    }
    int x = 0, ok = 0;
    if(s[r] == '-'){
        ok = 1;
        r++;
        if(r == DIM1){
            r = 0;
            fread(s, 1, DIM1, fin);
        }
    }
    while(s[r] >= '0' && s[r] <= '9'){
        x = x * 10 + s[r] - '0';
        r++;
        if(r == DIM1){
            r = 0;
            fread(s, 1, DIM1, fin);
        }
    }
    if(ok == 1){
        x = -x;
    }
    return x;
}
int main(){
    fread(s, 1, DIM, fin);
    n = num();
    k = num();
    for(i = 1; i <= n; i++){
        v[i] = num();
    }
    sol = -30000000;
    p = 1;
    for(i = 1; i <= n; i++){
        while(p <= u && v[ d[u] ] > v[i]){
            u--;
        }
        u++;
        d[u] = i;
        if(i >= k){
            if(d[p] == i - k){
                p++;
            }
            if(v[ d[p] ] > sol){
                sol = v[ d[p] ];
                ii = i;
            }
        }
    }
    fprintf(fout, "%d %d %d\n", ii - k + 1, ii, sol);
    return 0;
}