Cod sursa(job #1722230)

Utilizator crysstyanIacob Paul Cristian crysstyan Data 27 iunie 2016 17:18:31
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <deque>
#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 = 0;
char buf[MAX];

int readint(){
    if(poz==MAX){f.read(buf, MAX); poz = 0;}
    while(buf[poz]<'0' or '9'<buf[poz]){
        poz++;
        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;}
    }
    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;
}