Cod sursa(job #744549)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 8 mai 2012 23:45:47
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <deque>

using namespace std;

const int nmax=500000, inf_n=-(1<<30);

char *buffer;
int v[nmax+1];
deque <int> d;

void read(int &x){
    int ok;
    
    while ((*buffer<'0'||*buffer>'9')&&*buffer!='-'){
        ++buffer;
    }
    
    if (*buffer=='-'){
        ok=-1;
        ++buffer;
    }else{
        ok=1;
    }

    x=0;
    while (*buffer>='0'&&*buffer<='9'){
       x=x*10+ok*(*buffer-'0');
       ++buffer;
    }
}

int main(){
    int n, k, fs, sol, sol_pos;

    assert(freopen("secventa.in", "r", stdin));
    fseek(stdin, 0, SEEK_END);
    fs=ftell(stdin);
    rewind(stdin);
    buffer=(char*)malloc(fs);
    assert(fread(buffer, 1, fs, stdin));

    read(n);
    read(k);
    
    sol=inf_n;
    for (int i=1; i<=n; ++i){
        read(v[i]);
        if (d.front()==i-k){
            d.pop_front();
        }
        while (!d.empty()&&v[d.back()]>v[i]){
            d.pop_back();
        }
        d.push_back(i);
        if (i>k&&v[d.front()]>sol){
            sol=v[d.front()];
            sol_pos=i;
        }
    }
    fclose(stdin);

    assert(freopen("secventa.out", "w", stdout));
    printf("%d %d %d\n", sol_pos-k+1, sol_pos, sol);
    fclose(stdout);

    return 0;
}