Cod sursa(job #2667654)

Utilizator metallidethantralayerIon Cojocaru metallidethantralayer Data 3 noiembrie 2020 18:37:41
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;
const int NMAX = 500005;
const int BUFFMAX = 7000000;
int n, k, v[NMAX],mx=-1e9,i_s,i_f;

char buff[BUFFMAX];

void scan(int& x)
{
    static int i = 0;

    if (i == 0)
    {
        fread(buff, 1, BUFFMAX, stdin);
    }

    while (!isdigit(buff[i]) && buff[i] != '-')
        i++;

    int sign = buff[i] == '-' ? -1 : 1;
    if (sign == -1)
        i++;

    int num = 0;

    while (isdigit(buff[i]))
        num = num * 10 + buff[i++] - '0';

    x = sign * num;
}

deque <int> Q;
int main()
{
    freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
    scan(n);
    scan(k);
    for (int i = 1; i <= n; i++)
        scan(v[i]);
    for(int i=1; i<=n; i++)
    {
        while(!Q.empty()&&v[Q[Q.size()-1]]>v[i])
            Q.pop_back();
        Q.push_back(i);
        if(i>=k)
            if(mx<v[Q[0]])
                mx=v[Q[0]],i_s=i-k+1,i_f=i;
        if(i-k+1==Q[0])
            Q.pop_front();

    }
    printf("%d %d %d\n", i_s, i_f, mx);
    return 0;
}