Cod sursa(job #2472342)

Utilizator AndreiGSGhiurtu Andrei AndreiGS Data 12 octombrie 2019 11:41:28
Problema Secventa Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <fstream>
using namespace std;

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

const int MAXN = 500041;
///d contine elem intre [st, dr]
int d[MAXN];
int a[MAXN];
int st, dr;
int n, k;

void citire()
{
    f>>n>>k;
    for(int i=0; i<n; i++)
        f>>a[i];
}

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

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

void rez()
{
    for(int i=0; i<k-1; i++)
        addElement(i);
    int maxi=-30005, imin=0, imax=0;
    for(int i=k-1; i<n; i++)
    {
        addElement(i);
        int baza=a[pickElement(i)];
        if(baza>maxi)
        {
            maxi=baza;
            imin=i-k+1;
            imax=i;
        }
    }
    g<<imin+1<<" "<<imax+1<<" "<<maxi;
}

int main()
{
    citire();
    rez();
    return 0;
}