Cod sursa(job #2231337)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 13 august 2018 21:03:57
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.91 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 500001;
int deq[NMAX], v[NMAX];

class Writer {
  public:
    Writer(ostream& stream):
        m_stream(stream),
        m_buffer(new char[kBufferSize]) {
        memset(m_buffer.get(), 0, sizeof(char) * kBufferSize);
        m_pos = 0;
    }

    Writer& operator<<(int a) {
        int many = 0;
        if (a < 0) {
            a = -a;
            putchar('-');
        }

        do {
            digit_buffer[many++] = a % 10 + '0';
            a /= 10;
        } while (a > 0);
        for (int i = many - 1; i >= 0; --i)
            putchar(digit_buffer[i]);
        return *this;
    }

    Writer& operator<<(const char *s) {
        for (; *s; ++s)
            putchar(*s);
        return *this;
    }

    ~Writer() {
        m_stream.write(m_buffer.get(), m_pos);
    }

  private:
    void putchar(char c) {
        m_buffer[m_pos++] = c;
        if (m_pos == kBufferSize) {
            m_stream.write(m_buffer.get(), m_pos);
            m_pos = 0;
        }
    }

    static const int kBufferSize = 32768;
    ostream& m_stream;
    unique_ptr<char[]> m_buffer;
    char digit_buffer[30];
    int m_pos;
};

class Reader {
  public:
    Reader(istream& stream):
            m_stream(stream),
            m_pos(kBufferSize - 1),
            m_buffer(new char[kBufferSize]) {
        next();
    }

    Reader& operator>>(int& value) {
        value = 0;
        bool sign = false;
        while ((current() < '0' || current() > '9') && current() != '-')
            next();

        if (current() == '-') {
            sign = true;
            next();
        }

        while (current() >= '0' && current() <= '9') {
            value = value * 10 + current() - '0';
            next();
        }
        if (sign)
            value = -value;
        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;
        }
    }

    istream& m_stream;
    int m_pos;
    unique_ptr<char[]> m_buffer;
};

int main()
{

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

    Reader input(cin);
    Writer output(cout);

    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i ++)
        cin >> v[i];
    int st = 1, dr = 1;
    deq[1] = 1;
    int sol = -30005, rsol = 1, lsol = 1;
    for(int i = 2; i <= n; i ++) {
        while(st <= dr && v[i] < v[deq[dr]])
            dr --;
        deq[++dr] = i;
        if(k <= i && sol < v[deq[st]]) {
            sol = v[deq[st]];
            rsol = i;
        }
        if(deq[dr] - deq[st] == k-1)
            st ++;
    }
    cout << rsol - k + 1 << " " << rsol << " " << sol;
    return 0;
}