Cod sursa(job #2487262)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 4 noiembrie 2019 13:53:11
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <iostream>
#include <fstream>
#define MaxN 500001
using namespace std;

int q[MaxN],Left=0,Right=-1,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;
}

void read()
{
    char s[3000000];
    ifstream f("secventa.in");
    f>>n>>k;
    f.get();
    f.getline(s,3000000);
    int i=1;
    int semn=1;
    int number=0;
    for(char* p=s;*p!= NULL;p++)
    {
        if(*p == '-')
            semn=-1;
        else if('0'<= *p && *p <='9')
            number=number*10+*p-'0';
        else
        {
            sir[i++]=number*semn;
            number=0;
            semn=1;
        }
    }
    f.close();
}

int main()
{
    ofstream g("secventa.out");
    read();
    for(int i=1;i<=k;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;
    }
    int st,dr,rez;
    dr=k;
    rez=sir[q[Left]];
    for(int i=k+1;i<=n;i++)
    {
        if(q[Left]<=i-k)
            Left++;
        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;
        if(sir[q[Left]]>rez)
        {
            dr=i;
            rez=sir[q[Left]];
        }
    }
    st=dr-k+1;
    sir[0]=-30001;
    while(rez <= sir[--st]);
    g<<st+1<<' '<<dr<<' '<<rez;
    g.close();
    return 0;
}