Cod sursa(job #2268800)

Utilizator elenaisaiaElena Isaia elenaisaia Data 25 octombrie 2018 12:46:24
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

long long n,k,a[500010];
deque<long long>d;

void citire()
{
    ifstream fin("secventa.in");
    fin>>n>>k;
    for(long long i=0;i<n;++i)
        fin>>a[i];
}

void fctdeque()
{
    long long maxmin=a[0],poz=0,poz1=0,poz2=0;
    d.push_back(0);
    for(long long i=1;i<n;++i)
    {
        if(!d.empty())
            while(a[d.back()]>=a[i])
            {
                d.pop_back();
                if(d.empty())
                    break;
            }
        d.push_back(i);
        if(i>=k-1&&!d.empty())
        {
            if(d.back()-d.front()>=k)
                d.pop_front();
            if(a[d.front()]>maxmin)
            {
                maxmin=a[d.front()];
                poz=d.front();
                poz1=i-k+2;
                poz2=i+1;
            }
        }
    }
    ofstream fout("secventa.out");
    fout<<poz1<<" "<<poz2<<" "<<maxmin;
}

int main()
{
    citire();
    fctdeque();
    return 0;
}