Cod sursa(job #2498887)

Utilizator alexradu04Radu Alexandru alexradu04 Data 24 noiembrie 2019 18:52:38
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb

#include <iostream>
#include <fstream>
#define MaxN 500001
using namespace std;

int q[MaxN],Left=0,Right=-1,n,k;
int sir[MaxN];
void push(int i)
{
  int st=Left,m;
  q[++Right]=i;
  while(st<Right)
  {
    m=(st+Right)/2;
    if(sir[i]<=sir[q[m]])
      Right=m;
    else
      st=m+1;
  }
  q[st]=i;
}

void read()
{
  char s[3000000];
  ifstream f("secventa.in");
  f>>n>>k;
  f.get();
  f.getline(s,3000000);
  int i=1;
  int semn=1;
  int number=0;
  for(char* p=s; *p!= NULL; p++)
  {
    if(*p == '-')
      semn=-1;
    else if('0'<= *p && *p <='9')
      number=number*10+*p-'0';
    else
    {
      sir[i++]=number*semn;
      number=0;
      semn=1;
    }
  }
  f.close();
}

int main()
{
  ofstream g("secventa.out");
  read();
  for(int i=1; i<=k; i++)
  {
    int st=Left,m;
    q[++Right]=i;
    while(st<Right)
    {
      m=(st+Right)/2;
      if(sir[i]<=sir[q[m]])
        Right=m;
      else
        st=m+1;
    }
    q[st]=i;
  }
  int st,dr,rez;
  dr=k;
  rez=sir[q[Left]];
  for(int i=k+1; i<=n; i++)
  {
    if(q[Left]<=i-k)
      Left++;
    int st=Left,m;
    q[++Right]=i;
    while(st<Right)
    {
      m=(st+Right)/2;
      if(sir[i]<=sir[q[m]])
        Right=m;
      else
        st=m+1;
    }
    q[st]=i;
    if(sir[q[Left]]>rez)
    {
      dr=i;
      rez=sir[q[Left]];
    }
  }
  st=dr-k+1;
  sir[0]=-30001;
  while(rez <= sir[--st]);
  g<<st+1<<' '<<dr<<' '<<rez;
  g.close();
  return 0;
}