Cod sursa(job #1095467)

Utilizator IronWingVlad Paunescu IronWing Data 31 ianuarie 2014 02:28:19
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
/* 
 * File:   secventa.cpp
 * Author: Vlad
 *
 * Created on January 31, 2014, 2:05 AM
 */

#include <cstdio>
#include <deque>

using namespace std;

const int MAX_N = 500001;
const int MIN_VAL = -10000000;
int n, k;
int a[MAX_N];

void slidingWindowMinimum() {
    deque<int> q;
    for (int i = 1; i <= k; i++) {
        while (!q.empty() && a[q.back()] >= a[i]) {
            q.pop_back();
        }
        q.push_back(i);
    }
    int maxVal = MIN_VAL, leftIdx = 1;

    // minimum element in the window is the first in deque
    for (int i = k + 1; i <= n; ++i) {
        if (maxVal < a[q.front()]) {
            maxVal = a[q.front()];
            leftIdx = q.front();
        }

        while (!q.empty() && a[q.back()] >= a[i]) {
            // pop elements that can't be minimum in the
            // subsequent windows
            q.pop_back();
        }

        while (!q.empty() && q.front() <= i - k) {
            // pop elements that get out of the window
            q.pop_front();
        }

        q.push_back(i);
    }

    if (maxVal < a[q.front()]) {
        maxVal = a[q.front()];
        leftIdx = q.front();
    }

    printf("%d %d %d\n", leftIdx, leftIdx + k - 1, maxVal);
}

int main(int argc, char** argv) {

    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);

    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }

    slidingWindowMinimum();

    return 0;
}