Cod sursa(job #2472350)

Utilizator ana.pintiliciucAna Maria Pintiliciuc ana.pintiliciuc Data 12 octombrie 2019 11:45:27
Problema Secventa Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <cstdio>
#include <deque>

using namespace std;

const int MAXN = 500005;

int n, k, d[MAXN];
int a[MAXN];
int st, dr;

void citire()
{
    scanf("%d %d", &n, &k);
    for(int i=0;i<n;i++)
        scanf("%d", &a[i]);
}

void addElement(int pos)
{
    while(dr > st && a[d[dr-1]] >= a[pos])
        dr--;
    d[dr] = pos;
    dr++;
}

int pickElement(int pos)
{
   while(pos - d[st] >= k) ///prea vechi
        st++;
   return d[st];
}

int start, fin;

void rezolvare()
{
    for (int i = 0; i < k-1; i++)
        addElement(i);
    int vmax = -30000;
    for (int i = k-1; i < n; i++){
        addElement(i);
        int baza = a[pickElement(i)];
        if(baza > vmax)
        {
            vmax = baza;
            start = i-k+1;
            fin = i;
        }
    }

    printf("%d %d %d", start+1, fin+1, vmax);
}

int main()
{
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
    citire();
    rezolvare();

    return 0;
}