Cod sursa(job #2750579)

Utilizator hungntnktpHungntnktp hungntnktp Data 12 mai 2021 05:49:10
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<bits/stdc++.h>
using namespace std;
#define forinc(i,a,b) for(int i=a;i<=b;i++)
#define fordec(i,a,b) for(int i=a;i>=b;i--)
const int N=500010;
int a[N], f[N], n, k, st, ed, res=-1e5;
int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> k;
    forinc(i,1,n) cin >> a[i];
    deque<int> dq;
    forinc(i,1,n)
    {
        while(!dq.empty()&&dq.front()<=i-k) dq.pop_front();
        while(!dq.empty()&&a[dq.back()]>=a[i]) dq.pop_back();
        dq.push_back(i);
        if(i>=k&&a[dq.front()]>res)
        {
            res=a[dq.front()];
            ed=i;
        }
    }
    st=ed-k+1;
    fordec(i,st,1)
    {
        if(a[i]<res) return cout << i+1 << " " << ed << " " << res, 0;
    }
    cout << st << " " << ed << " " << res;
}