Cod sursa(job #2217756)

Utilizator TooHappyMarchitan Teodor TooHappy Data 2 iulie 2018 01:06:34
Problema Secventa Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>
using namespace std;
 
ifstream in("secventa.in");
ofstream out("secventa.out");

const int NMax = 5e5 + 10;

int n, k, v[NMax];
deque< int > dq;

void ReadData() {
    in >> n >> k;

    char s[NMax]; in.get();
    in.getline(s, NMax - 1);

    int i = 0, sign, cnt = 1, len = strlen(s);
    while(i < len) {
        if(s[i] == '-') {
            sign = -1;
            ++i;
        } else {
            sign = 1;
        }

        int nr = 0;
        while(s[i] >= '0' && s[i] <= '9') {
            nr = nr * 10 + (s[i] - '0');
            ++i;
        }

        v[cnt++] = nr * sign;
        ++i;
    }
}
 
int main() {
    ios::sync_with_stdio(false); in.tie(0); out.tie(0);

    ReadData();

    int bazaMaxima = INT_MIN, left = -1, right = -1;
    for(int i = 1; i <= n; ++i) {
        while(!dq.empty() && v[i] <= v[dq.back()]) {
            dq.pop_back();
        }
        dq.push_back(i);
 
        if(dq.front() == i - k) {
            dq.pop_front();
        }
 
        if(i >= k && v[dq.front()] > bazaMaxima) {
            bazaMaxima = v[dq.front()];
            left = i - k + 1;
            right = i;
        }
    }
 
    out << left << " " << right << " " << bazaMaxima << "\n";
 
    return 0;
}