Cod sursa(job #2394768)

Utilizator isav_costinVlad Costin Andrei isav_costin Data 1 aprilie 2019 21:50:18
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>
#include <cctype>
#include <deque>

#define MAXN 500000
#define INF 40000

using namespace std;

char buff[4096];
int p=4095;

inline char get_char()
{
	if( ++p==4096 )
    p=0, fread(buff,1,4096,stdin);

	return buff[p];
}

inline void get_int( int &nr )
{
	char ch;

	while( !isdigit(ch=get_char()) && ch!='-' );

	int semn=1;

	if( ch=='-' )
		semn=-semn, nr=0;
  else
		nr=(ch-'0');

	while( isdigit(ch=get_char()) )
    nr=nr*10+(ch-'0');

  nr*=semn;
}

int n, m;
int v[1+MAXN+1];

deque<int> dq;

inline void my_push_back( int p )
{
  while( !dq.empty() && v[p]<v[dq.back()] )
    dq.pop_back();

  dq.push_back(p);
}

inline void my_pop_front( int p )
{
  if( dq.front()==p )
    dq.pop_front();
}

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

  get_int(n), get_int(m);

  for( int i=1;i<m;i++ )
    get_int(v[i]), my_push_back(i);

  int dr, maxim=-INF;

  for( int i=m;i<=n;i++ )
  {
    get_int(v[i]), my_push_back(i);

    if( v[dq.front()]>maxim )
      maxim=v[dq.front()], dr=i;

    my_pop_front(i-m+1);
  }

  printf( "%d %d %d", dr-m+1, dr, maxim );

  return 0;
}