Cod sursa(job #1735251)

Utilizator robx12lnLinca Robert robx12ln Data 29 iulie 2016 13:06:25
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include<cstdio>
#include<deque>
#define INF 2000000000
#define DIM 30005
using namespace std;
FILE * fin  = fopen("secventa.in",  "r");
FILE * fout = fopen("secventa.out", "w");
int n, k, v[500005], maxim, st, dr;
deque<int> d;
char buffer[DIM];
int poz = 0;
/*
void citeste( int &numar ){
    numar = 0;
    char semn = '+';
    while( buffer[poz] < '0' || buffer[poz] > '9' ){
        semn = buffer[poz];
        poz++;
        if( poz == DIM ){
             fread( buffer, 1, DIM, stdin);
             poz = 0;
        }
    }
    while( buffer[poz] >= '0' || buffer[poz] <= '9' ){
        numar = numar * 10 + ( buffer[poz] - '0' );
        poz++;
        if( poz == DIM ){
             fread( buffer, 1, DIM, stdin);
             poz = 0;
        }
    }
    if( semn == '-' ){
        numar = -numar;
    }
    return ;
}
*/
int main(){
    fscanf( fin, "%d%d", &n, &k );
    //fread( buffer, 1, DIM, stdin);
    for( int i = 1; i <= n; i++ ){
        //citeste( v[i] );
        fscanf( fin, "%d", &v[i] );
    }
    maxim = -INF;
    for( int i = 1; i <= n; i++ ){
        while( !d.empty() && v[d.back()] > v[i]  ){
            d.pop_back();
        }
        d.push_back(i);
        if( d.front() <= i - k ){
            d.pop_front();
        }
        if( i >= k ){
            if( maxim < v[d.front()] ){
                maxim = v[d.front()];
                st = i - k + 1;
                dr = st + k - 1;
            }
        }
    }
    fprintf( fout, "%d %d %d", st, dr, maxim );
    return 0;
}