Cod sursa(job #3258450)

Utilizator md_kosminGlod Cosmin Stefan md_kosmin Data 22 noiembrie 2024 15:05:08
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <fstream>
#include <deque>
#include <vector>
using namespace std;

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

deque<int> window;
int n, k, nr;
int pos, val;
vector<int> nums;

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> nr;
        nums.push_back(nr);
    }
    // initial deque - first window
    for (int i = 0; i < k; ++i) {
        while (!window.empty() && nums[i] < nums[window.back()])
            window.pop_back();
        window.push_back(i);
    }
    // the maximum value of the first window
    // is the front element of the deque
    pos = 0;
    val = nums[window.front()];

    if (window.front() == 0) // first element of array
        window.pop_front();

    for (int i = k; i < n; ++i) {
        while (!window.empty() && nums[i] < nums[window.back()])
            window.pop_back();
        
        window.push_back(i);
        if (nums[window.front()] > val) {
            val = nums[window.front()];
            pos = i - k + 1;
        }
        if (window.front() == i - k + 1)
            window.pop_front();
    }
    
    int lim = pos + k;
    
    while (pos - 1 >= 0 && nums[pos - 1] > val)
        pos --;
    
    cout << pos + 1 << ' ' << lim << val;

    cin.close();
    cout.close();
    
    return 0;
}