Cod sursa(job #2536489)

Utilizator SochuDarabaneanu Liviu Eugen Sochu Data 2 februarie 2020 09:51:29
Problema Secventa Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("03")
#define N 500005

using namespace std;

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

int n , k;
char s[N];
short a[N];
deque < int > d;

int main()
{
    ios_base::sync_with_stdio(false) , f.tie(0) , g.tie(0);

    int inc = 0 , sf = 0 , i;
    short baza = -30003;

    f >> n >> k;

    f.get();
    int semn = 1 , nr = 0 , n = 0;

    f.getline(s , N);

    for(i = 0 ; s[i] ; i++)
    {
        if(s[i] == '-')
            semn = -1;
        else if(isdigit(s[i]))
            nr = nr * 10 + s[i] - '0';
        else
        {
            a[++n] = nr * semn;
            semn = 1;
            nr = 0;
        }
    }

    d.push_front(1);

    for(i = 1 ; i <= n ; ++i)
    {
        while(!d.empty() && a[i] <= a[d.back()])
            d.pop_back();

        d.push_back(i);

        if(d.front() == i - k)
            d.pop_front();

        if(i >= k)
        {
            if(a[d.front()] > baza)
            {
                baza = a[d.front()];
                inc = i - k + 1;
                sf = i;
            }
        }
    }

    g << inc << ' ' << sf << ' ' << baza;

    return 0;
}