Cod sursa(job #2375936)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 8 martie 2019 13:02:10
Problema Secventa Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <iostream>
#include <deque>
#include <climits>
using namespace std;

deque <int>D;

int n, k, maxi = INT_MIN;
int a[500005];
int isi;
int main()
{
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
    scanf("%d %d", &n, &k);
    scanf("%d", &a[1]);
    D.push_front(1);
    for(int i=2; i<=n; i++)
    {
        scanf("%d", &a[i]);
        while(!D.empty() && a[D.back()] > a[i])
            D.pop_back();
        D.push_back(i);

        while(!D.empty() && D.front()<i-k+1)
            D.pop_front();

        if(i >= k)
        {
            if(a[D.front()] > maxi)
            {
                maxi = a[D.front()];
                isi = D.front();
            }
        }
    }
    int i = isi;
    while(a[i] >= maxi && i>=1)
        i--;
    i++;
    printf("%d %d %d", i, i+k-1, maxi);
    return 0;
}