Cod sursa(job #2474360)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 15 octombrie 2019 08:23:55
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 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(int value) {
        while (value - cont[left] >= k && left < right)
            ++left;
        return this->cont[left];
    }
    void pushBack(int value) {
        cont[right++] = value;
    }
    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), ind1, ind2;
    for (int i = 0; i < k - 1; ++i) {
        deque.popBack(i);
        deque.pushBack(i);
    }
    for (int i = k - 1; i < n; ++i) {
        int min;
        deque.popBack(i);
        deque.pushBack(i);
        min = deque.getMin(i);
        if (arr[min] > max) {
            max = arr[min];
            ind1 = i - k + 1;
            ind2 = i;
        }
    }
    fout << ind1 + 1 << ' ' << ind2 + 1 << ' ' << max << '\n';
}

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