Cod sursa(job #1374259)

Utilizator andrei_r_97Radoi Andrei andrei_r_97 Data 5 martie 2015 01:15:18
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>
#include <cstring>

#define MAX 500000
#define INF 30000

using namespace std;

int a[MAX + 1];
char sir[8 * MAX + 1];
int coadaD[MAX];

void read(int n) {

  gets(sir);
  sir[strlen(sir)] = ' ';

  int nr = 0, contor = 1;
  bool negative = false;

  for (int i = 0; sir[i]; i++) {
    if (sir[i] == ' ') {
      if (negative) {
        nr = (-1) * nr;
      }
      a[contor++] = nr;
      nr = 0;
      negative = false;
    }
    else {
      if (sir[i] == '-') {
        negative = true;
      }
      else {
        nr = nr * 10 + (sir[i] - '0');
      }
    }
  }
}

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

  int n, k, i;
  scanf("%d %d\n", &n, &k);

  read(n);

  int minim = (-1) * INF;
  int minStart = 0, minStop = 0;
  int Front = 1, Back = 0;
  for (i = 1; i <= n; i++) {

    while (Front <= Back && a[i] <= a[coadaD[Back]])
      Back--;

    coadaD[++Back] = i;

    if (i >= k && a[coadaD[Front]] > minim) {
      minim = a[coadaD[Front]];
      minStart = i - k + 1;
      minStop = i;
    }

    if (coadaD[Front] == i - k + 1)
      Front++;

  }

  printf("%d %d %d", minStart, minStop, minim);

  return 0;
}