Cod sursa(job #2122912)

Utilizator DavidLDavid Lauran DavidL Data 5 februarie 2018 17:22:30
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>
#define MAX 500005
using namespace std;
ifstream fi("secventa.in");
ofstream fo("secventa.out");

int n,k;
int A[5*MAX];
int poz,val;
int a,b,maxim=-30005;

void update(int nod,int l,int r)
{
    if (l>poz || r<poz)
        return;
    if (l==r)
    {
        A[nod]=val;
        return;
    }
    int mij=(l+r)/2;
    if (poz<=mij)
        update(2*nod,l,mij);
    else
        update(2*nod+1,mij+1,r);
    A[nod]=min(A[2*nod],A[2*nod+1]);
}

void query(int nod,int l,int r)
{
    if (r-l+1<k)
        return;
    if (A[nod]>maxim)
    {
        maxim=A[nod];
        a=l;
        b=r;
    }
    if (A[nod]==maxim)
    {
        if (l<a || (l==a && r<b))
        {
            maxim=A[nod];
            a=l;
            b=r;
        }
    }
    int mij=(l+r)/2;
    query(2*nod,l,mij);
    query(2*nod+1,mij+1,r);
}

int main()
{
    fi>>n>>k;
    for (int i=1; i<=n; i++)
        A[i]=30005;
    for (int i=1; i<=n; i++)
    {
        int x;
        fi>>x;
        poz=i,val=x;
        update(1,1,n);
    }

    query(1,1,n);
    fo<<a<<" "<<b<<" "<<maxim;
    return 0;
}