Cod sursa(job #878049)

Utilizator eliseiDragoslav Elisei elisei Data 13 februarie 2013 20:26:05
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <iostream>
#include <fstream>
using namespace std;
int n,k;
int st[500005],poz[500005];
void Citire()
{
    int i,j,x,pr,ul;
    ifstream fin("secventa.in");
    fin>>n;
    fin>>k;
    fin>>x;
    st[1]=x;
    poz[1]=1;
    pr=ul=1;
    for(i=2;i<=k;i++)
    {
        fin>>x;
        while(pr<=ul && st[ul]>x)
        {
            ul--;
        }
        ul++;
        st[ul]=x;
        poz[ul]=i;
    }
    int maxim=-500000;
    int st2,dr;
    for(i=k+1;i<=n;i++)
    {
        fin>>x;
        while(pr<=ul && st[ul]>x)
        {
            ul--;
        }
        ul++;
        st[ul]=x;
        poz[ul]=i;
        if(i-poz[pr]>=k) pr++;
        if(maxim<st[pr])
        {

            maxim=st[pr];
            st2=i-k+1;
            dr=i;
        }
    }
   ofstream fout("secventa.out");
   fout<<st2<<" "<<dr<<" "<<maxim<<"\n";
   fout.close();
}
int main()
{
    Citire();

    return 0;
}

///vile,compus,predecesor campion
//secventa pe infoarean