Cod sursa(job #2631902)

Utilizator andreic06Andrei Calota andreic06 Data 1 iulie 2020 15:08:25
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <iostream>
#include <cstdio>
#include <deque>

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

char get_ch () {
    static int bp = dim;
    char buff[dim];

    if ( bp == dim ) {
      fread ( buff, 1, dim, stdin );
      bp = 0;
    }
    return buff[bp++];
}

int get_int () {
   int nr = 0, semn = 1;
   char ch;

   while ( isspace ( ch = get_ch () ) );

   if ( ch == '-' )
     semn = -1, ch = get_ch ();

   do
     nr = nr * 10 + ch - '0';
   while ( !isspace ( ch = get_ch () ) );

   return nr * semn;
}

int main()
{
   freopen ( "secventa.in", "r", stdin );
   freopen ( "secventa.out", "w", stdout );

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

   n = get_int (), k = get_int ();
   for ( int i = 1; i <= n; i ++ )
      v[i] = get_int ();

   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;
   }

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