Cod sursa(job #2449694)

Utilizator ezioconnorVlad - Gabriel Iftimescu ezioconnor Data 20 august 2019 14:47:16
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, k, st, dr, rez = INT_MIN, semn, i, j;
int v[500001];
char s[4000001];
deque <pair <int, int>> dq;

int main()
{
    in >> n >> k;
    in.get();
    in.getline(s, 4000000);
    semn = 1;
    for (j = 1, i = 0; s[i]; ++i)
    {
        if (s[i] == '-')
            semn = -1;
        else if (isdigit(s[i]))
            v[j] = v[j] * 10 + (s[i] - '0');
        else
            v[j++] *= semn, semn = 1;
    }
    v[j] *= semn;
    for (int i = 1; i <= n; ++i)
    {
        while (!dq.empty() && v[i] <= dq.back().first)
            dq.pop_back();
        dq.push_back({v[i], i});
        if (dq.front().second == i - k)
            dq.pop_front();
        if (i >= k && rez < dq.front().first)
        {
            rez = dq.front().first;
            st = i - k + 1;
            dr = i;
        }
    }
    return out << st << " " << dr << " " << rez, 0;
}