Cod sursa(job #2005149)

Utilizator MihalachiRazvanMihalachi Razvan MihalachiRazvan Data 26 iulie 2017 14:43:55
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <string.h>
#define dim  500001
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int n,k,a[dim],minimax=-30001,pozi,dp[dim];
    char s[3500001];
int main()
{
    fin>>n>>k;
    fin.get();
 fin.get(s, 3500001);
        int p=1,semn,st,fi,l=strlen(s);
        for(int i=0;i<l;i++)
        {
            semn=1;
            if(s[i]=='-')
                {semn=0;
                 i++;}
                while(s[i]>='0'&&s[i]<='9')
                {
                    a[p]=a[p]*10+s[i]-'0';
                    i++;
                }
                if(semn==0)
                    a[p]=-a[p];
                p++;
        }
        st=1;
        fi=0;
        st=1;
        fi=0;
       for(int i=1;i<=n;i++)
       {
              while(a[i]<a[dp[fi]]&&st<=fi)
                    fi--;
              fi++;
              dp[fi]=i;
              if(i-dp[st]==k)
                st++;
              if(i>=k)
              {
                  if(minimax<a[dp[st]])
                  {
                     pozi=i-k+1;
                     minimax=a[dp[st]];
                  }
              }
       }
       fout<<pozi<<"  "<<pozi+k-1<<"  "<<minimax;

    return 0;
}