Cod sursa(job #2306439)

Utilizator UnseenMarksmanDavid Catalin UnseenMarksman Data 22 decembrie 2018 12:54:30
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <iostream>
#include <fstream>
#define maxn 500000
using namespace std;

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

int n, k, maxim=-30001, v[maxn+2];
int dq[maxn+2], fr=1, bk=0, posi, posj;

int main()
{
    fin>>n>>k;
    for(int i=1; i<=k; i++)
    {
        fin>>v[i];
        if(v[i]<=v[dq[fr]])
        {
            bk=fr;
            dq[bk]=i;
        }
        else if(v[dq[bk]]<v[i])
        {
            dq[++bk]=i;
        }
        else
        {
            int st=fr, dr=bk, mid;
            while(st<dr)
            {
                mid=(st+dr)/2;
                if(v[dq[mid]]<v[i])
                {
                    st=mid+1;
                }
                else
                {
                    dr=mid;
                }
            }
            mid=(st+dr)/2;
            if(v[dq[mid]]>=v[i]) mid--;
            bk=mid;
            dq[++bk]=i;
        }
        //while(fr<=bk&&v[i]<=v[dq[bk]]) bk--;
    }
    if(maxim<v[dq[fr]])
    {
        maxim=v[dq[fr]];
        posj=1;
        posi=k;
    }
    for(int i=k+1; i<=n; i++)
    {
        fin>>v[i];
        if(v[i]<=v[dq[fr]])
        {
            bk=fr;
            dq[bk]=i;
        }
        else if(v[dq[bk]]<v[i])
        {
            dq[++bk]=i;
        }
        else
        {
            int st=fr, dr=bk, mid;
            while(st<dr)
            {
                mid=(st+dr)/2;
                if(v[dq[mid]]<v[i])
                {
                    st=mid+1;
                }
                else
                {
                    dr=mid;
                }
            }
            mid=(st+dr)/2;
            if(v[dq[mid]]>=v[i]) mid--;
            bk=mid;
            dq[++bk]=i;
        }
        //while(fr<=bk&&v[i]<=v[dq[bk]]) bk--;
        if(i-dq[fr]>=k)
        {
            fr++;
        }
        if(maxim<v[dq[fr]])
        {
            maxim=v[dq[fr]];
            posi=i;
            posj=i-k+1;
        }
    }
    fout<<posj<<' '<<posi<<' '<<maxim<<'\n';
    return 0;
}