Cod sursa(job #1744628)

Utilizator TincaMateiTinca Matei TincaMatei Data 20 august 2016 01:21:14
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <cstdio>
#include <deque>

using namespace std;
const int MAX_N = 500000;
int v[MAX_N];
deque<int>d;

const int INFINIT = 1000000;

const int BUF = 4096;

char c;
int cursor;
char buf[BUF];

void getC(FILE *fin) {
  if(cursor == BUF) {
    fread(buf, 1, BUF, fin);
    cursor = 0;
  }
  cursor++;
  c = buf[cursor - 1];
}

void ignSpace(FILE *fin) {
  getC(fin);
  while(c == ' ' || c == '\n')
    getC(fin);
}

int getNr(FILE *fin) {
  int n, semn;
  ignSpace(fin);
  if(c == '-') {
    semn = -1;
    getC(fin);
  } else
    semn = 1;
  n = 0;
  while('0' <= c && c <= '9') {
    n = n * 10 + c - '0';
    getC(fin);
  }
  return n * semn;
}

void add(int x) {
  while(!d.empty() && x < d.back())
    d.pop_back();
  d.push_back(x);
}

int main() {
  int n, i, k, max, maxSt;
  FILE *fin = fopen("secventa.in", "r");
  fscanf(fin, "%d%d", &n, &k);
  fread(buf, 1, BUF, fin);
  for(i = 0; i < k - 1; i++) {
    v[i] = getNr(fin);
    add(v[i]);
  }
  max = maxSt = -INFINIT;
  for(i = k - 1; i < n; i++) {
    v[i] = getNr(fin);
    add(v[i]);
    if(d.front() > max) {
      max = d.front();
      maxSt = i + 1 - k + 1;
    }
    if(v[i - k + 1] == d.front())
      d.pop_front();
  }
  fclose(fin);

  FILE *fout = fopen("secventa.out", "w");
  fprintf(fout, "%d %d %d", maxSt, maxSt + k - 1, max);
  fclose(fout);
  return 0;
}