Cod sursa(job #877145)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 12 februarie 2013 16:58:19
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<fstream>
#define In "secventa.in"
#define Out "secventa.out"
#define N 500004
using namespace std;
int n , k, x, sol, ul, pr, st, dr;
int q[N];
int poz[N];
ofstream fout(Out);
void Afis()
{
    int i;
    for(i=pr;i<=ul;i++)
        fout<<q[i]<<" ";
    fout<<"\n";
}

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