Cod sursa(job #206738)

Utilizator cata00Catalin Francu cata00 Data 9 septembrie 2008 11:34:17
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 500010
#define MAX_FILE_SIZE 5000000

int a[MAX], left[MAX], right[MAX], stack[MAX];
int n, k, sp;
int best_start, best_base;

void read(void) {
  char buffer[MAX_FILE_SIZE];
  FILE *f = fopen("secventa.in", "rt");
  fscanf(f, "%d %d", &n, &k);
  fread(buffer, MAX_FILE_SIZE, 1, f);
  fclose(f);

  int ptr = 0;
  for (int i = 0; i < n; i++) {
    a[i] = atoi(buffer + ptr);
    if (i < n - 1) {
      while (isspace(buffer[ptr])) {
        ptr++;
      }
      while (!isspace(buffer[ptr])) {
        ptr++;
      }
    }
  }
}

void compute_right() {
  int top;
  sp = 0;

  for (int i = 0; i < n; i++) {
    while (sp && (a[i] < a[stack[sp - 1]])) {
      top = stack[sp - 1];
      right[top] = i - top - 1;
      sp--;
    }
    stack[sp++] = i;
  }
  while (sp) {
    top = stack[sp - 1];
    right[top] = n - top - 1;
    sp--;
  }
}

void compute_left() {
  int top;
  sp = 0;

  for (int i = n - 1; i >= 0; i--) {
    while (sp && (a[i] < a[stack[sp - 1]])) {
      top = stack[sp - 1];
      left[top] = top - i - 1;
      sp--;
    }
    stack[sp++] = i;
  }
  while (sp) {
    top = stack[sp - 1];
    left[top] = top;
    sp--;
  }
}

void scan(void) {
  best_base = -1000000;

  for (int i = 0; i < n; i++) {
    if (left[i] + right[i] + 1 >= k && a[i] > best_base) {
      best_base = a[i];
      best_start = i - left[i];
    }
  }
}

void write() {
  FILE *f = fopen("secventa.out", "wt");
  fprintf(f, "%d %d %d\n", best_start + 1, best_start + k, best_base);
  fclose(f);
}

int main() {
  read();
  compute_right();
  compute_left();
  scan();
  write();
  return 0;
}