Cod sursa(job #1604161)

Utilizator aimrdlAndrei mrdl aimrdl Data 18 februarie 2016 00:05:40
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include <deque>
 
using namespace std;
 
struct item {
    int val;
    int pos;
};
 
int main (void) {
    ios_base::sync_with_stdio(false);
     
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
         
    int n, k;
     
    cin >> n >> k;
    int v[n];
     
    deque<int> l;
     
    int max = -99999, endSol = 0;
     
    for (int i = 0; i < k; ++i) {
        cin >> v[i];
        while (!l.empty() && v[i] <= v[l.back()]) {
            l.pop_back();
        }
        
        l.push_back(i);
    }
         
         
    max = v[l.front()];
    endSol = l.front();
     
    for (int i = k; i < n; ++i) {    
        cin >> v[i];
        while (!l.empty() && v[i] <= v[l.back()]) {
            l.pop_back();
        }
         
        l.push_back(i);
         
        if (l.front() <= i - k) l.pop_front();
         
        if (v[l.front()] > max) {
            max = v[l.front()];
            endSol = i;
        }
    }
     
    cout << endSol - k + 2 << " " << endSol + 1 << " " << max;
     
    return 0;
}