Cod sursa(job #2783978)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 15 octombrie 2021 14:44:13
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <string>
using namespace std;

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

deque <int> v;
int nums[500005];
int n, k;
int ans = -0x3f3f3f3f;

int main()
{
    ios::sync_with_stdio(false);
    fin >> n >> k >> ws;

    string str;
    getline(fin, str);

    int currIdx = 0;
    str += ' ';
    for (int i = 0; i < n; i++)
    {
        char curr = str[currIdx];
        int num = 0;
        if (curr == ' ')
        {
            curr = str[++currIdx];
        }
        bool isNeg = false;
        if (curr == '-')
        {
            isNeg = true;
            curr = str[++currIdx];
        }
        while (curr != ' ')
        {
            num *= 10;
            num += curr - '0';
            curr = str[++currIdx];
        }
        if (isNeg)
            nums[i] = -num;
        else
            nums[i] = num;
    }


    int down, up;
    down = 0;
    up = k - 1;
    for (int i = down; i <= up; i++)
    {
        int curr = nums[i];
        while (!v.empty() && v.back() > curr)
        {
            v.pop_back();
        }
        v.push_back(curr);
    }
    int u, d;
    while (up < n)
    {
        if (ans < v.front())
        {
            u = up + 1;
            d = down + 1;
            ans = v.front();
        }
        if (nums[down] == v.front())
        {
            v.pop_front();
        }
        up++;
        down++;
        int curr = nums[up];

        while (!v.empty() && v.back() > curr)
        {
            v.pop_back();
        }
        v.push_back(curr);
    }

    fout << d<< ' ' << u << ' ' << ans;

    return 0;
}