Cod sursa(job #2472364)

Utilizator mara_anghelinaAnghelina Mara mara_anghelina Data 12 octombrie 2019 11:51:44
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <iostream>
#include <fstream>
using namespace std;

const int MAXN=500041;

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

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

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

void addElement(int poz)
{
    while( dr>stg && a[d[dr-1]] > a[poz])
        dr--;
    d[dr]=poz;
    dr++;
}
int pickElement(int poz)
{
    while(poz-d[stg] >= k)///prea vechi
        stg++;
    return d[stg];
}

void solve()
{
    for(int i=0;i<k-1;i++)
        addElement(i);
    int maxi=-30000;
    int lo,hi;
    for(int i=k-1;i<n;i++)
    {
        addElement(i);
        int baza=a[pickElement(i)];
        if(baza>maxi)
        {
            maxi=baza;
            lo=i-k+1;
            hi=i;
        }

    }
    g<<lo+1<<" "<<hi+1<<" "<<maxi;
}

int main()
{
    read();
    solve();
    return 0;
}