Cod sursa(job #2458813)

Utilizator driver71528@gmail.comTerec Andrei-Sorin [email protected] Data 21 septembrie 2019 16:01:12
Problema Secventa Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <iostream>
#include <fstream>
#define MaxN 500001
using namespace std;

int q[MaxN],Left=0,Right=0,n,k;
int sir[MaxN];

void push(int i)
{
    int st=Left,m;
    q[++Right]=i;
    while(st<Right)
    {
        m=(st+Right)/2;
        if(sir[i]<=sir[q[m]])
            Right=m;
        else
            st=m+1;
    }
    q[st]=i;
}

inline int minim()
{
    return sir[q[Left]];
}
int main()
{
    ifstream f("secventa.in");
    ofstream g("secventa.out");
    f>>n>>k;
    for(int i=1;i<=n;i++)
        f>>sir[i];
    f.close();
    q[Right]=1;
    for(int i=2;i<=k;i++)
        push(i);
    int bst,bdr,brez;
    bst=1;
    bdr=k;
    brez=minim();
    for(int i=k+1;i<=n;i++)
    {
        if(q[Left]<=i-k)
            Left++;
        push(i);
        if(minim()==brez && bdr==i-1)
            bdr++;
        else if(minim()>brez)
        {
            bdr=i;
            brez=minim();
            bst=i-k+1;
        }
    }
    g<<bst<<' '<<bdr<<' '<<brez;
    g.close();
    return 0;
}