Cod sursa(job #2472338)

Utilizator PandaChanTrusca Daria PandaChan Data 12 octombrie 2019 11:40:02
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
const int MAXN=500005;
int d[MAXN], a[MAXN];
int st, dr;
int n, k;
void citire()
{
    f>>n>>k;
    for(int i=0; i<n; i++)
        f>>a[i];
}
void add_elem(int poz)
{
    while(dr>st && a[d[dr-1]]>a[poz])
        dr--;
    d[dr]=poz;
    dr++;
}
int pick_elem(int poz)
{
    while(poz-d[st]>=k)
        st++;
    return d[st];
}
void rezolvare()
{
    for(int i=0; i<k-1; i++)
        add_elem(i);
    int vmax=-30000;
    int st, fn;
    for(int i=k-1; i<n; i++)
    {
        add_elem(i);
        int baza=a[pick_elem(i)];
        if(baza>vmax)
        {
            vmax=baza;
            st=i-k+1;
            fn=i;
        }
    }
    g<<st+1<<' '<<fn+1<<' '<<vmax;
}
int main()
{
    citire();
    rezolvare();
    return 0;
}