Cod sursa(job #877270)

Utilizator Pintilie_AndreiFII-Pintilie Andrei Pintilie_Andrei Data 12 februarie 2013 18:42:21
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include<fstream>

using namespace std;
int n , k, x, sol, ul, pr, st, dr;
int q[500004];
int poz[500004];
ofstream fout("secventa.out");

int main()
{
    int i;
    ifstream fin("secventa.in");
    fin>>n>>k>>x;
    ul = -1;
    ul++;
    q[ul] = x;
    poz[ul] = 1;
    //Afis();
    sol = - 300000;
    for(i=2;i<=n;i++)
    {
        fin>>x;
        while(pr<=ul && q[ul]>=x)
            ul--;
            ul++;
        q[ul] = x;
        poz[ul] = i;
        if(i-poz[pr]>=k)
            pr++;
        if(i>=k && q[pr]>sol)
        {
            sol = q[pr];
            st = i-k+1;
            dr = i;
        }
     //   Afis();
    }
    fout<<st<<" "<<dr<<" "<<sol<<"\n";
    return 0;
}