Cod sursa(job #3252300)

Utilizator paull122Paul Ion paull122 Data 29 octombrie 2024 10:11:55
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <bits/stdc++.h>

#define VMAX 100000
#define NMAX 500000
#define LOG 20
#define INF (long long)(1e9)
#define BASE 10007
#define MOD 1000000007
#define ll  long long int

#define ADD 1000001

#define NIL 0

using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");


int n,k;
int a[NMAX+1];
int main()
{
    fin >> n >> k;
    for(int i=1;i<=n;i++)
    {
        fin >> a[i];
    }
    deque<int> minq;
    for(int i=1;i<=k-1;i++)
    {
        while(!minq.empty() && a[minq.back()] >= a[i])
        {
            minq.pop_back();
        }
        minq.push_back(i);
    }
    int st=0,dr=0,res=-INF;
    for(int i=k;i<=n;i++)
    {
        while(!minq.empty() && a[minq.back()] >= a[i])
        {
            minq.pop_back();
        }
        minq.push_back(i);
        if(res < a[minq.front()])
        {
            res = a[minq.front()];
            st=i-k+1;
            dr=i;
        }
        if(minq.front() <= i-k+1)
        {
            minq.pop_front();
        }
    }
    fout << st << ' ' << dr << ' ' << res << '\n';
}