Cod sursa(job #1345960)

Utilizator VictoriaNevTascau Victoria VictoriaNev Data 17 februarie 2015 22:34:51
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <cctype>
#include <cstdlib>
#include <cstring>
#define NMAX 500000
using namespace std;
int n, k, i, j, st, sign, poz, dr, m, maxim, v[NMAX+1], d[NMAX+1];
char sir[5000000];
int main()
{
    ifstream cin("secventa.in");
    ofstream cout("secventa.out");
    cin>>n>>k;
    char c[1000];
    cin.getline(c,1000);
    cin.getline(sir,5000000);
    int semn, nr, j;

    i=0;
    j=1;
    while(j<=n)
    {
        if(sir[i]==' ')
            ++i;
        if(sir[i]=='-')
        {
            semn=1;
            ++i;
        }
        while(sir[i]>='0'&&sir[i]<='9')
        {
            v[j]=v[j]*10+sir[i]-'0';
            ++i;
        }
        if(semn)
        {
            v[j]=-v[j];
            semn=0;
        }
        ++j;
    }

    st=dr=1;
    maxim=1<<20;
    maxim=-maxim;
    for(i=1; i<=n; i++)
    {
        while(st<=dr&&v[d[dr]]>=v[i])
            dr--;
        dr++;
        d[dr]=i;
        if(i-k==d[st])
            st++;
        if(maxim<v[d[st]]&&i>=k)
            maxim=v[d[st]],poz=d[dr];


    }
    cout<<poz-k+1<<' '<<poz<<' '<<maxim;
    return 0;
}