Cod sursa(job #2394742)

Utilizator isav_costinVlad Costin Andrei isav_costin Data 1 aprilie 2019 21:18:10
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>
#include <deque>

#define MAXN 500000
#define INF 40000

using namespace std;

ifstream cin( "secventa.in" );
ofstream cout( "secventa.out" );

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()
{
  cin>>n>>m;

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

  int dr, maxim=-INF;

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

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

    my_pop_front(i-m+1);
  }

  cout<<dr-m+1<<" "<<dr<<" "<<maxim;

  return 0;
}