Cod sursa(job #2631888)

Utilizator andreic06Andrei Calota andreic06 Data 1 iulie 2020 14:56:00
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;
const int N = 5e5;
const int INF = 2e9;
int v[N];

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

int main()
{

   int n, k;
   int maxx, Begin, End;

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

   deque < int > dq;
   maxx = -INF, Begin = End = -1;
   for ( int i = 1; i <= n; i ++ ) {
      while ( !dq.empty () && v[i] <= v[dq.back ()] )
        dq.pop_back ();
      dq.push_back ( i );

      if ( dq.front () + k <= i )
        dq.pop_front ();
      if ( i >= k )
        if ( v[dq.front ()] > maxx )
          maxx = v[dq.front()], Begin = i - k + 1, End = i;
   }

   fout << Begin << ' ' << End << ' ' << maxx;
    return 0;
}