Cod sursa(job #3190994)

Utilizator David2007David Preda David2007 Data 8 ianuarie 2024 15:51:24
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,q,st=1,dr,max1=-2100000000,pos,i;
int v[500005],d[500005];

void push (int a)
{
    while (st<=dr&&v[d[dr]]>v[a])
    {
        d[dr]=0;
        dr--;
    }
    dr++;
    d[dr]=a;
}

void slide(int poz)
{
    while (st<=dr&&d[st]<=poz)
    {
        d[st]=0;
        st++;
    }
}

int main()
{
    f>>n>>q;
    for(i=1;i<=n;i++)
    {
        f>>v[i];
        push(i);
        slide(i-q);
        if(i>=q&&v[d[st]]>max1)
        {
            max1=v[d[st]];
            pos=i;
        }
    }
    g<<pos-q+1<<" "<<pos<<" "<<max1;
}