Cod sursa(job #2126090)

Utilizator refugiatBoni Daniel Stefan refugiat Data 9 februarie 2018 07:42:31
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream si("secventa.in");
ofstream so("secventa.out");
int v[500005];
int dp[500005];
char s[3500001];
int main()
{
    int n,k;
    si>>n>>k;
    si.get();
    si.get(s,3500001);
    int l=strlen(s),p=1;
    for(int i=0;i<=l;++i)
    {
        int semn=1;
        if(s[i]=='-')
        {
            semn=0;
            i++;
        }
        while(s[i]>='0'&&s[i]<='9')
        {
            v[p]=v[p]*10+s[i]-'0';
            i++;
        }
        if(semn==0)
            v[p]=-v[p];
        p++;
    }
    int st=1,fi=0;
    int pozi,minm=-1000000000;
    for(int i=1;i<=n;i++)
    {
        while(v[i]<v[dp[fi]]&&st<=fi)
            fi--;
        fi++;
        dp[fi]=i;
        if(i-dp[st]==k)
            st++;
        if(i>=k)
            if(minm<v[dp[st]])
            {
                pozi=i-k+1;
                minm=v[dp[st]];
            }
    }
    so<<pozi<<' '<<pozi+k-1<<' '<<minm;
    return 0;
}