Cod sursa(job #2786609)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 21 octombrie 2021 11:43:23
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

const int maxN = 500000;
int n, k, v[maxN + 5], ans = -0x3f3f3f3f, l, r;
string s;
deque <int> dq;

int main()
{
    fin >> n >> k >> ws;
    getline(fin, s);
    int ind = 0;
    for(int i = 1; i <= n; i++)
    {
        char c = s[ind];
        int nr = 0, semn = 1;
        if(c == ' ')
            c = s[++ind];
        if(c == '-')
        {
            semn = -1;
            c = s[++ind];
        }
        while(ind < s.size() && s[ind] != ' ')
        {
            nr = nr * 10 + (c - '0');
            c = s[++ind];
        }
        v[i] = semn * nr;
    }
    for(int i = 1; i <= k - 1; i++)
    {
        while(!dq.empty() && v[dq.back()] > v[i])
            dq.pop_back();
        dq.push_back(i);
    }
    for(int i = k; i <= n; i++)
    {
        while(!dq.empty() && v[dq.back()] > v[i])
            dq.pop_back();
        dq.push_back(i);
        if(dq.front() == i-k)
            dq.pop_front();
        if(i >= k && v[dq.front()] > ans)
        {
            ans = v[dq.front()];
            l = i - k + 1;
            r = i;
        }
    }
    fout << l << ' ' << r << ' ' << ans;
    return 0;
}