Cod sursa(job #1027612)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 12 noiembrie 2013 21:27:07
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>
#include <cstring>
using namespace std;

int n, k, v[500005], i, semn, nr, x, st, dr, maxim, pmax, sol[500005], poz[500005], d[500005];
char s[4000000];

int main()
{
    ifstream f("secventa.in");
    ofstream g("secventa.out");
    f>>n;f>>k;
    f.get();
    f.get(s,4000000);
    semn=1;
    for(i=0;s[i]!=0;i++)
    {
        if(s[i]=='-')
            semn=0-1;
        else
        if(s[i]==' ')
        {
            x++;
            v[x]=nr*semn;
            nr=0;
            semn=1;
        }
        else
            nr=nr*10+s[i]-'0';
    }
    x++;
    v[x]=nr*semn;
    //for(i=1;i<=x;i++)
      //  g<<v[i]<<" ";
    st=1;dr=0;
    for(i=1;i<=n;i++)
    {
        while(dr>=st && v[i]<d[dr])
            dr--;
        dr++;
        d[dr]=v[i];poz[dr]=i;
        if(i-poz[st]==k)
            st++;
        sol[i]=d[st];
    }
    maxim=0;
    for(i=k;i<=n;i++)
        if(sol[i]>maxim)
        {
            maxim=sol[i];
            pmax=i;
        }
    g<<pmax-k+1<<" "<<pmax<<" "<<maxim;
    g<<"\n";
    f.close();g.close();
    return 0;
}