Cod sursa(job #2053323)

Utilizator RazvanatorHilea Razvan Razvanator Data 31 octombrie 2017 17:54:47
Problema Secventa Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int dq[500005];

char s[2550000];
int v[500005];
int n,k,cnt;
int min_st,min_dr;

void parse_1()
{
    int i=0;
    while (s[i]>='0' && s[i]<='9') {
        n=n*10+s[i]-'0';
        i++;
    }
    i++;
    while (s[i]>='0' && s[i]<='9') {
        k=k*10+s[i]-'0';
        i++;
    }

}

void parse_2()
{
    int k=0,x;
    bool neg=false;
    for (int i=1;i<=n;i++) {
        x=0;
        if (s[k]=='-') {neg=true;k++;}
        while (s[k]>='0' && s[k]<='9') {
            x=x*10+s[k]-'0';
            k++;
        }
        if (neg) x=-x;
        k++;
        neg=false;

        v[++cnt]=x;
    }
}

int main()
{
    fin.get(s,'\n');
    parse_1();
    fin>>ws;
    fin.get(s,2550000);
    parse_2();


    int st=0;
    int dr=-1;
    int maxim=-30010;

    st=0;
    dr=-1;
    maxim=-30010;
    min_st=n+1;
    min_dr=n+1;

    for (int i=1;i<=n;i++) {

        if(st<=dr && dq[st]==i-k)
        {
            st++;
        }
        while(st<=dr && v[i]<=v[dq[dr]])
        {
            dr--;
        }
        dq[++dr]=i;

        if (i >= k && v[dq[st]] > maxim)
        {
            maxim = v[dq[st]];
            min_st=i-k+1;
            min_dr=i;
        }
    }
    fout<<min_st<<" "<<min_dr<<" "<<maxim;
}