Cod sursa(job #2126804)

Utilizator EpureCarlaEpure Carla EpureCarla Data 9 februarie 2018 23:16:14
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int v[500005],i,dp[500005],semn;
char s[3500001];
int main()
{
    int n,k;
    fin>>n>>k;
    fin.get();
    fin.get(s,3500001);
    int lun=strlen(s);
    int p=1;
    for(i=0;i<=lun;++i)
    {
        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;
    int dr=0;
    int pozi;
    int minm=-1000000000;
    for(int i=1;i<=n;i++)
    {
        while(v[i]<v[dp[dr]]&&st<=dr)
            dr--;
        dr++;
        dp[dr]=i;
        if(i-dp[st]==k)
            st++;
        if(i>=k)
            if(minm<v[dp[st]])
            {
                pozi=i-k+1;
                minm=v[dp[st]];
            }
    }
    fout<<pozi<<' '<<pozi+k-1<<' '<<minm;
    return 0;
}
/*#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;
}
*/