Cod sursa(job #1719575)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 19 iunie 2016 17:17:20
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 500005;

struct PII {
    int x, y;
};

int v[NMAX];

const int BMAX = 50005;

class hpstream {
private:
    FILE *file;
    int   buff;
    char  str[BMAX];

    inline char nextch(void) {
        if(buff==BMAX) {
            fread(str, 1, BMAX, file);
            buff = 0;
        }
        return str[buff++];
    }

public:
    hpstream() {}
    hpstream(const char *str) {
        file = fopen(str, "r");
        buff = BMAX;
    }

    inline hpstream &operator>> (int &arg) {
        char ch, sgn=1;

        arg = 0;

        while(!isdigit(ch=nextch()) && ch!='-');

        if(ch=='-') {
            sgn=-1;
            ch=nextch();
        }
        arg=ch-'0';
        while(isdigit((ch=nextch())))
            arg=arg*10+ch-'0';

        arg*=sgn;

        return *this;
    }

    void close(void) {
        fclose(file);
    }
};

int main(void) {
    hpstream f("secventa.in");
    ofstream g("secventa.out");

    int n, k, st, dr, a, b, ans;
    deque<PII> dq;


    f>>n>>k;
    for(int i=1; i<=n; ++i)
        f>>v[i];

    for(st=dr=1; dr<=k; ++dr) {
        while(!dq.empty() && v[dr]<dq.back().x)
            dq.pop_back();
        dq.push_back({v[dr], dr});
    }

    a = 1;
    b = k;
    ans = dq.front().x;

    for(++st; dr<=n; ++dr) {
        while(!dq.empty() && dr-dq.front().y>=k)
            dq.pop_front();
        while(!dq.empty() && v[dr]<=dq.back().x)
            dq.pop_back();

        dq.push_back({v[dr], dr});

        if(dq.front().x>ans) {
            a   = dr-k+1;
            b   = dr;
            ans = dq.front().x;
        }
    }

    g<<a<<' '<<b<<' '<<ans<<' '<<'\n';

    f.close();
    g.close();
    return 0;
}