Cod sursa(job #1565092)

Utilizator tudorcomanTudor Coman tudorcoman Data 10 ianuarie 2016 13:32:29
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb

#include <cstdio>
#include <cctype>
#include <deque>

const int maxN = 500000;
std :: deque<int> D;
int v[maxN], N, K, pos;
int ans = -(1 << 30);

const int maxSize = 1048576;

class ReadStream {
private:
  int cursor;
  char buf[maxSize];
  FILE *f;
  inline void move() {
    ++ cursor;
    if(cursor == maxSize) {
      cursor = 0;
      fread(buf, maxSize, 1, f);
    }
  }
  inline int todig(char c) {
    return c - '0';
  }

public:
  ReadStream(const char *fname) {
    f = fopen(fname, "r");
    cursor = 0;
    fread(buf, maxSize, 1, f);
  }

  ReadStream &operator >> (int& N) {
    char sign = '+';
    while(!isdigit(buf[cursor])) {
      sign = buf[cursor];
      move();
    }

    N = 0;
    while(isdigit(buf[cursor])) {
      N = N * 10 + todig(buf[cursor]);
      move();
    }

    if(sign == '-')
      N = -N;
    return *this;
  }

  ReadStream &operator >> (float& N) {
    char sign = '+';
    while(!isdigit(buf[cursor])) {
      sign = buf[cursor];
      move();
    }
    N = 0;
    while(isdigit(buf[cursor])) {
      N = N * 10 + todig(buf[cursor]);
      move();
    }

    if(buf[cursor] == '.') {
      float p = 0.1;
      move();
      while(isdigit(buf[cursor])) {
        N = N + p * todig(buf[cursor]);
        p *= 0.1;
        move();
      }
    }

    if(sign == '-')
      N = -N;
    return *this;
  }
};

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

  in >> N >> K;
  for(register int i = 0; i < N; ++ i) {
    in >> v[i];
    while(!D.empty() and v[i] < v[D.back()])
      D.pop_back();
    D.push_back(i);
    if(i - D.front() >= K)
      D.pop_front();
    if(i >= K - 1 and v[D.front()] > ans) {
      ans = v[D.front()];
      pos = i - K + 1;
    }
  }
  printf("%d %d %d\n", pos + 1, pos + K, ans);
  return 0;
}