Cod sursa(job #2938219)

Utilizator MDrianMincu Florin Adrian MDrian Data 11 noiembrie 2022 19:51:48
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
/**#include <bits/stdc++.h>
#include <deque>
#include <fstream>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
deque <int> dq;
int a[500001];
long long s,n,k;
int main()
{
    f>>n>>k;
    for (int i=1;i<=n;i++)
    {
        f>>a[i];
        while (!dq.empty()&&a[dq.back()]>a[i])
            dq.pop_back();
        if (!dq.empty()&&dq.front()==i-k)
            dq.pop_front();
        dq.push_back(i);
        if (i>=k)s+=a[dq.front()];
    }
    f.close();
    g<<s;
    g.close();
    return 0;
}*/


#include <bits/stdc++.h>
#include <deque>
#include <fstream>
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
int a[500001],n,k,b,bm=-30000,st=500001,sf=500001,x;
deque <int> dq;
int main()
{
    f>>n>>k;
    for (int i=1; i<=n; i++)
    {
        f>>a[i];
        while (!dq.empty()&&a[dq.back()]>a[i])
            dq.pop_back();
        if (!dq.empty()&&dq.front()==i-k)
            dq.pop_front();
        dq.push_back(i);
        b=a[dq.front()];
            if (b>bm)
            {
                bm=b;
                st=dq.front();
                sf=dq.back();
            }
            else if (b==bm&&dq.front()<st)
            {
                bm=b;
                st=dq.front();
                sf=dq.back();
            }
            else if (dq.front()==st&&dq.back()<sf)
            {
                bm=b;
                st=dq.front();
                sf=dq.back();
            }
    }
    f.close();
    g<<st<<" "<<sf<<" "<<bm;
    g.close();
    return 0;
}