Cod sursa(job #1722233)

Utilizator crysstyanIacob Paul Cristian crysstyan Data 27 iunie 2016 17:24:37
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <deque>
#include <cstring>
#define MAX 1 << 17

using namespace std;

ifstream f("secventa.in");
ofstream g("secventa.out");

deque <int> d,q;
int v[500001],i,n,pozi,pozf,k,val=-31000, poz;
char buf[MAX];

int readint(){
    int semn = 0;
    if(poz==MAX){f.read(buf, MAX); poz = 0;}
    while(buf[poz]<'0' or '9'<buf[poz]){
        poz++;
        if (buf[poz] == '-')
            semn = 1;
        if(poz==MAX){f.read(buf, MAX); poz = 0;}
    }
    int ans = 0;
    while('0'<=buf[poz] and buf[poz]<='9'){
        ans = ans*10 + buf[poz] - '0';
        poz++;
        if(poz==MAX){f.read(buf, MAX); poz = 0;}
    }
    if (semn == 1)
        return ans * -1;
    return ans;
}

int main()
{
    n = readint();
    k = readint();

    for (i=1; i<=n; ++i)
    {
        v[i] = readint();
        while (!d.empty() && v[d.back()]>v[i])
        d.pop_back();
        d.push_back(i);

        if (d.front()<=i-k) d.pop_front();

        if (v[d.front()]>val && i>=k)
        {
            val=v[d.front()];
            pozf=i;
        }
    }
    g<<pozf-k+1<<" "<<pozf<<" "<<val;

    return 0;
}