Cod sursa(job #1744623)

Utilizator TincaMateiTinca Matei TincaMatei Data 20 august 2016 00:58:47
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <cstdio>
#include <deque>

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

const int INFINIT = 1000000;

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);
  for(i = 0; i < k - 1; i++) {
    fscanf(fin, "%d", &v[i]);
    add(v[i]);
  }
  max = maxSt = -INFINIT;
  for(i = k - 1; i < n; i++) {
    fscanf(fin, "%d", &v[i]);
    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;
}