Cod sursa(job #2473815)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 14 octombrie 2019 12:39:54
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

const int MAXN = 5 * 1e5, MAXVAL = 3 * 1e4;
int arr[MAXN], n, k;

struct minCmp {
    bool operator() (int a, int b) const {
        return a < b;
    }
};

template <class Compare>
class Deque {
private:
    int cont[MAXN], left, right;
    Compare cmp;
public:
    Deque() {
        left = 0;
        right = 0;
    }
    int getMin() const{
        return this->cont[left];
    }
    void pushBack(int value) {
        cont[right++] = value;
    }
    void popFront(int value) {
        while (value - cont[left] >= k && left < right)
            ++left;
    }
    void popBack(int value) {
        while (arr[value] < arr[cont[right - 1]] && right > left)
            --right;
    }
};

void read() {
    fin >> n >> k;
    for (int i = 0; i < n; ++i)
        fin >> arr[i];
}

void solve() {
    Deque<minCmp> deque;
    int max = -(MAXVAL + 1), ind;
    deque.pushBack(0);
    deque.popBack(1);
    deque.pushBack(1);
    for (int i = 2; i < n; ++i) {
        int min;
        deque.popBack(i);
        deque.popFront(i);
        deque.pushBack(i);
        min = deque.getMin();
        if (arr[min] > max) {
            max = arr[min];
            ind = min;
        }
    }
    fout << ind + 1 << ' ' << ind + k << ' ' << max << '\n';
}

int main() {
    read();
    solve();
    return 0;
}