Cod sursa(job #1441225)

Utilizator SwagginInMyJaysaaaaaaaaaaaas SwagginInMyJays Data 23 mai 2015 22:38:25
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <bits/stdc++.h>

using namespace std;

const int dmax = 500003;

deque < int > D;

char s[dmax]; int a[dmax];

// acest parser NU imi apartine, este al lui Adrian Budau

class Scanner {
  public:
    Scanner(string file, int buffer_size = 32768):
            buffer_size_(buffer_size) {
        file_ = fopen(file.c_str(), "r");
        buffer_ = new char[buffer_size];
        pointer_ = buffer_ + buffer_size_;
    }

    Scanner& operator>>(int &object) {
        object = 0;
        while (next() < '0' or next() > '9')
            advance();
        while (next() >= '0' and next() <= '9') {
            object = object * 10 + next() - '0';
            advance();
        }
        return *this;
    }

  private:
    char next() {
        if (pointer_ == buffer_ + buffer_size_) {
            pointer_ = buffer_;
            fread(buffer_, 1, buffer_size_, file_);
        }
        return *pointer_;
    }

    void advance() {
        ++pointer_;
    }

    FILE *file_;
    int buffer_size_;
    char *buffer_, *pointer_;
};
int main(){
    Scanner cin ("secventa.in");
    ofstream cout ("secventa.out");
    int N, K, start, end, worst = -dmax;
    cin >> N >> K;
    for (int i = 1; i <= N; i++)
        cin >> a[i];
    for (int i = 1; i <= N; i++){
            while ( !D.empty() && a[i] <= a[D.back()]) D.pop_back();
            D.push_back(i);
            if (D.front() == i - K   ) D.pop_front();
            if (i >= K){
                    if (a[D.front()] > worst) worst = a[D.front()], start = i - K + 1 , end = i;
            }
    }
    cout << start << " " << end << " " << worst;
    return 0;
}