Cod sursa(job #2776203)

Utilizator Ana100Ana-Maria Tomoiala Ana100 Data 18 septembrie 2021 20:14:05
Problema Secventa Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream cin("secventa.in");
ofstream cout("secventa.out");
int a[500005];
deque<int>dq;
int main()
{
    int n,k,poz1,poz2,poz3,max1=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=k;i++)
    {
        while(dq.size()>0 and a[i]<=a[dq.back()])
        {
            dq.pop_back();
        }
        dq.push_back(i);
    }
    max1=a[dq.front()];
    poz1=dq.front();
    for(int i=k+1;i<=n;i++)
    {
        while(dq.size()>0 and a[i]<=a[dq.back()])
        {
            dq.pop_back();
        }
        dq.push_back(i);
        while(dq.size()>0 and dq.front()<i-k+1)
        {
            dq.pop_front();
        }
        if(a[dq.front()]>max1)
        {
          max1=a[dq.front()];
          poz1=dq.front();
          poz2=i;
        }
    }
    cout<<poz2-k+1<<" "<<poz2<<" "<<max1;
    /*
    int n,k,max1=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=k+1;i++)
    {
        while(dq.size()>0 and a[i]<=a[dq.back()])
        {
            dq.pop_back();
        }
        dq.push_back(i);
        while(dq2.size()>0 and a[i]>=a[dq2.back()])
        {
            dq2.pop_back();
        }
        dq2.push_back(i);
    }
    max1=a[dq2.front()]-a[dq.front()];
    //cout<<a[dq2.front()]<<" "<<a[dq.front()]<<" "<<max1<<endl;
    for(int i=k+2;i<=n;i++)
    {
        //cout<<i<<endl;
        while(dq.size()>0 and a[i]<=a[dq.back()])
        {
            dq.pop_back();
        }
        dq.push_back(i);
        while(dq.size()>0 and dq.front()<i-k)
        {
            dq.pop_back();
        }
        while(dq2.size()>0 and a[i]>=a[dq2.back()])
        {
            dq2.pop_front();
        }
        dq2.push_back(i);
        while(dq.size()>0 and dq2.front()<i-k)
        {
            dq2.pop_front();
        }
        max1=max(max1,(a[dq2.front()]-a[dq.front()]));
    }
    cout<<max1;
    */
    return 0;
}