Cod sursa(job #3032037)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 21 martie 2023 12:38:16
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream  cin("secventa.in");
ofstream cout("secventa.out");
const int N = 5 * 1e5 + 9, Inf = 0x3f3f3f3f;
int n,k,v[N];
int ans = -Inf,poz = -1;

class dqueue
{
private:
    deque<pair<int,int>> dq;
public:
    void push(int val,int ind)
    {
        while(!dq.empty() && dq.back().first >= val)
            dq.pop_back();
        dq.push_back({val,ind});
    }
    int query(int ind)
    {
        while(!dq.empty() && dq.front().second < ind)
            dq.pop_front();

        if(dq.size() == 0)return -1;
        return dq.front().first;
    }
};

int main()
{
    cin>>n>>k;
    for(int i = 1; i <= n; ++i)
        cin>>v[i];

    dqueue dq;
    for(int i = 1; i < k; ++i)
        dq.push(v[i],i);
    for(int i = k; i <= n; ++i)
    {
        dq.push(v[i],i);
        int mn = dq.query(i-k+1);
        if(ans < mn)
        {
            ans = mn;
            poz = i;
        }
    }

    cout<<poz-k+1<<' '<<poz<<' '<<ans;
    return 0;
}