Cod sursa(job #2451823)

Utilizator Stefan_PiscuPiscu Stefan Constantin Stefan_Piscu Data 28 august 2019 12:46:53
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <stdio.h>
#include <ctype.h>
#include <fstream>

using namespace std;

class InParser
{
    private:
        FILE *fin;
        char *buff;
        int sp;

        char read_ch() {
            ++sp;
            if (sp == 4096) {
                sp = 0;
                fread(buff, 1, 4096, fin);
            }
            return buff[sp];
        }

    public:
        InParser(const char* nume) {
            fin = fopen(nume, "r");
            buff = new char[4096]();
            sp = 4095;
        }

        InParser& operator >> (int &n) {
            char c;
            while (!isdigit(c = read_ch()) && c != '-');
            int sgn = 1;
            if (c == '-') {
                n = 0;
                sgn = -1;
            } else {
                n = c - '0';
            }
            while (isdigit(c = read_ch())) {
                n = 10 * n + c - '0';
            }
            n *= sgn;
            return *this;
        }

        InParser& operator >> (long long &n) {
            char c;
            n = 0;
            while (!isdigit(c = read_ch()) && c != '-');
            long long sgn = 1;
            if (c == '-') {
                n = 0;
                sgn = -1;
            } else {
                n = c - '0';
            }
            while (isdigit(c = read_ch())) {
                n = 10 * n + c - '0';
            }
            n *= sgn;
            return *this;
        }
};


InParser fin("secventa.in");
ofstream fout("secventa.out");

int dq[500004], st, dr, v[500004], n, k, p;

int main()
{
    fin>>n>>k;
    int st=1, dr=0;
    for(int i=1;i<=n;++i) fin>>v[i];
    int maxi=-2000000000;
    for(int i=1;i<=n;++i)
    {
        while(v[dq[dr]]>=v[i]&&dr>=st) dr--;
        dq[++dr]=i;
        if(dq[dr]-dq[st]==k) st++;
        if(v[dq[st]]>maxi&&i>=k)
        {
            p=dq[dr];
            maxi=v[dq[st]];
        }
    }
    fout<<p-k+1<<" "<<p<<" "<<maxi<<"\n";
    return 0;
}