Cod sursa(job #2016507)

Utilizator GeoeyMexicanuBadita George GeoeyMexicanu Data 29 august 2017 15:54:51
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <iostream>
#include <fstream>
#define INF 3000010

using namespace std;
ofstream g("secventa.out");

int a[500010],deq[500010],max1=-INF,i,j,n,k,sol1,sol2,frnt,bck;
class parser {
    using integer = int;
    static const int strMax = 35e5 + 5;

    ifstream in;
    char str[strMax],*p;
    bool failed;

    public:
    parser(string s) {
        in.open(s);
        in.get(str,strMax,1);
        //cout<<str<<'\n';
        p = str;
        failed = false;
    }

    parser& operator>> (integer& nr) {
        bool neg = 0;
        while ( !( ('0' <= *p && *p <= '9') || *p == '\0') ) {
            if (*p == '-') {
                neg ^= 1;
            }
            ++p;
        }

        if (*p == '\0') {
            nr = 0;
            failed = true;
            return *this;
        }

        nr = 0;
        while ('0' <= *p && *p <= '9') {
            nr = nr * 10 + *p++ - '0';
        }
        if (neg) {nr = -nr;}

        return *this;
    }

    bool fail() {
        return failed;
    }

    void print() {
        cout<<str<<'\n';
    }

    void close() {
        in.close();
    }
};
parser pin("secventa.in");

int main()
{
    pin>>n>>k;
    frnt=1;
    bck=0;
    for(i=1;i<=n;i++)
    {
        pin>>a[i];
        while(frnt<=bck && a[i]<=a[deq[bck]]){
            bck--;
        }
        deq[++bck]=i;
        if(deq[frnt]<=i-k)
            frnt++;
        if(i>=k)
        {
            if(max1<a[deq[frnt]])
            {
                max1=a[deq[frnt]];
                sol1=deq[bck];
            }
        }
    }
    g<<sol1-k+1<<" "<<sol1<<" "<<max1;
    return 0;
}