Cod sursa(job #2447181)

Utilizator claudiu.gatinaFMI Claudiu Gatina claudiu.gatina Data 12 august 2019 12:43:50
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <iostream>
#include <cstdio>
#include <vector>
#define OFFSET 30000
#define MAXINT 30000
#define NMAX 500010
#define MININT -30010
using namespace std;

short int v[NMAX];
int st[NMAX];
int dr[NMAX];
int n, k;
int x;
char fileText[5000000];

void calcStDr(int i)
{
  for (int j = i - 1; j > 0; j = st[j])
  {
    if (v[j] < v[i])
    {
      st[i] = j;
      return;
    }
    else
      dr[j] = i;
  }
}

void read()
{
  FILE* file = fopen("secventa.in", "r");
  fgets(fileText, 5000000, file);

  int i = 0;
  while (fileText[i] != ' ')
    n = n * 10 + (fileText[i++] - '0');
  ++i;

  while (fileText[i] != '\n')
    k = k * 10 + (fileText[i++] - '0');
  

  fgets(fileText, 5000000, file);

  fclose(file);
  i = 0;
  int currentPos = 1;

  int sign = 1;
  while (fileText[i] != 0)
  {
    switch (fileText[i])
    {
    case '-':
      sign = -1;
      break;
    case ' ':
      v[currentPos] *= sign;
      sign = 1;
      ++currentPos;
      break;
    default:
      v[currentPos] = v[currentPos] * 10 + (fileText[i] - '0');
    }
    ++i;
  }
  v[n] *= sign;
}

int main()
{
  freopen("secventa.out", "w", stdout);

  read();

  for (int i = 1; i <= n; ++i)
    calcStDr(i);

  short int maxSupport = MININT;
  int startPos = 0;

  for (int i = 1; i <= n; ++i)
    if (v[i] > maxSupport && ((dr[i] == 0) ? n + 1 : dr[i]) - st[i] - 1 >= k)
    {
      maxSupport = v[i];
      startPos = st[i] + 1;
    }

  printf("%d %d %d", startPos, startPos + k - 1, maxSupport);

  return 0;
}