Cod sursa(job #1418544)

Utilizator dinuandAndrei-Mario Dinu dinuand Data 13 aprilie 2015 14:01:00
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <vector>
#include <limits>
#include <memory>

using namespace std;

ofstream out("secventa.out");

class Reader {
  public:
    Reader(const string& filename):
            m_stream(filename),
            m_pos(kBufferSize - 1),
            m_buffer(new char[kBufferSize]) {
        next();
    }
   
    Reader& operator>>(int& value) {
        value = 0;
        int sign;
        while ((current() < '0' || current() > '9') && current() != '-') {
            sign = 1;
            next();
        }
        while ((current() >= '0' && current() <= '9') || current() == '-') {
            if (current() == '-')  {
                sign = -1;
                next();
            }
            value = value * 10 + current() - '0';
            next();
        }
        if (sign < 0) value *= sign;
        return *this;
    }
   
  private:
    const int kBufferSize = 32768;
   
    char current() {
        return m_buffer[m_pos];
    }
   
    void next() {
        if (!(++m_pos != kBufferSize)) {
            m_stream.read(m_buffer.get(), kBufferSize);
            m_pos = 0;
        }
    }
   
    ifstream m_stream;
    int m_pos;
    unique_ptr<char[]> m_buffer;
};

int main()
{
    int N, K;

    Reader fin("secventa.in");

    fin >> N >> K; 

    vector<int>V(N + 1);
    for (int i = 1; i <= N; i++) fin >> V[i];

    deque<int> dq;
    int maxMin = numeric_limits<int>::min(), finalEnd = 1;
    for (int i = 1; i <= N; i++) {

        while (!dq.empty() && V[i] < V[ dq.back() ]) dq.pop_back();

        dq.push_back(i);

        if (dq.front() <= i - K) dq.pop_front();

        if (i >= K) {
            if (V[ dq.front() ] > maxMin) {
                maxMin = V[ dq.front() ];
                finalEnd = i; 
            }
        }
    }

    out << finalEnd - K + 1 << " " << finalEnd << " " << maxMin << '\n'; 

    return 0;
}