Cod sursa(job #2938181)

Utilizator vlad414141414141Vlad Ionescu vlad414141414141 Data 11 noiembrie 2022 19:10:12
Problema Secventa Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>
#include <deque>

using namespace std;

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

deque <int> v;
int n, k, x[500041], maxi=-31000, aux;

void read()
{
    fin >> n >> k;
    for (int i=0;i<n;++i)
        fin >> x[i];
    v.push_front(0);
    for (int i=1;i<k;++i)
    {
        if(x[i]<x[v.front()])
        {
            v.clear();
            v.push_front(i);
        }
        else
        {
           while(x[i]<x[v.back()])
            {
                v.pop_back();
            }
            v.push_back(i);
        }
    }
  //  fout << x[v.front()] << " ";
   maxi=x[v.front()];
   aux=v.front();

    for (int i=k;i<n;++i)
    {
        if (v.front()<i-k+1)
            v.pop_front();
        if (x[i]<x[v.front()])
        {
            v.clear();
            v.push_front(i);
        }
        else{
            while(x[i]<x[v.back()])
            {
                v.pop_back();
            }
            v.push_back(i);
        }
   //    fout << x[v.front()] << "----" << i << "    ";
        if (x[v.front()]>maxi)
        {
            maxi=x[v.front()];
            aux=i-k+1;
         //  cout << aux << " " << maxi << "\n";
        }
    }
    aux++;
    fout << aux << " " << aux+k-1 << " " << maxi;

}

int main()
{
    read();
    return 0;
}