Cod sursa(job #1775751)

Utilizator grimmerFlorescu Luca grimmer Data 10 octombrie 2016 18:03:25
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <fstream>
#include <deque>
using namespace std;
int v[500001];
deque<int> q;
int max_base = -99999;

class InputReader {
public:
  InputReader() {}
  InputReader(const char *file_name) {
    input_file = fopen(file_name, "r");
    cursor = 0;
    fread(buffer, SIZE, 1, input_file);
  }
  inline InputReader &operator >>(int &n) {
    while (buffer[cursor] < '0' || buffer[cursor] > '9') {
      advance();
    }
    n = 0;
    while ('0' <= buffer[cursor] && buffer[cursor] <= '9') {
      n = n * 10 + buffer[cursor] - '0';
      advance();
    }
    return *this;
  }
private:
  FILE *input_file;
  static const int SIZE = 1 << 17;
  int cursor;
  char buffer[SIZE];
  inline void advance() {
    ++ cursor;
    if (cursor == SIZE) {
      cursor = 0;
      fread(buffer, SIZE, 1, input_file);
    }
  }
};

InputReader cin("secventa.in");
ofstream cout("secventa.out");

int main()
{
    int i, k, n, l, r;
    cin>>n>>k;

    for(i = 1; i <= n; ++i){
        cin>>v[i];

        while(!q.empty() && v[q.back()] >= v[i]){
            q.pop_back();
        }

        q.push_back(i);

        while(q.front() == i-k){
            q.pop_front();
        }

        if(i >= k){
            if(v[q.front()] > max_base){
                max_base = v[q.front()];
                l = i - k + 1;
                r = i;
            }
        }
    }

    cout<<l<<" "<<r<<" "<<max_base;
    return 0;
}