Cod sursa(job #3242394)

Utilizator Andrei-Dani-10Pisla Andrei Daniel Andrei-Dani-10 Data 11 septembrie 2024 20:03:56
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include <utility>
#include <deque>
using namespace std;
ifstream in("secventa.in");
ofstream out("secventa.out");
int n, k, x, maxi, st, dr; deque < pair <int, int> > dq;

int main(){
    in>>n>>k;
    for(int i = 1; i <= k; i++){
        in>>x;
        for(; !dq.empty() && dq.back().first >= x; dq.pop_back());
        dq.push_back(make_pair(x, i));
    }
    maxi = dq.front().first; st = 1; dr = k;
    for(int i = k + 1; i <= n; i++){
        in>>x;
        for(; !dq.empty() && dq.front().second < (i - k + 1); dq.pop_front());
        for(; !dq.empty() && dq.back().first >= x; dq.pop_back());
        dq.push_back(make_pair(x, i));
        if(maxi < dq.front().first){
            maxi = dq.front().first;
            st = i - k + 1; dr = i;
        }
    }
    out<<st<<" "<<dr<<" "<<maxi;
    return 0;
}