Submission #858136

#	Time	Username	Problem	Language	Result	Execution time	Memory
858136		mircea_007	Peru (RMI20_peru)	C++17	0 / 100	1 ms	348 KiB

peru

#include "peru.h"

#include <set>
#include <deque>

#define magic_sauce inline __attribute__((always_inline))
using ll = long long;

const ll INF = 1e18;
const int MOD = 1e9 + 7;

magic_sauce ll min( ll a, ll b ){ return a < b ? a : b; }
magic_sauce ll max( ll a, ll b ){ return a > b ? a : b; }

int ans_hash( int n, ll v[] ){
  int ret = 0;

  for( int i = 0 ; i < n ; i++ )
    ret = (ret * 23LL + v[i]) % MOD;

  return ret;
}

/*

  ans[i] = min{ ans[max{ i - k, prev_bigger( x ) }] + x | x=v[i]..+INF }
  // echivalent:
  ans[i] = min{ ans[j] + max{ v[j+1..i] } | j=i-k..i-1 }

  // folosim stiva de maxime partiale
  // ans este crescator => daca avem un interval [st, dr] de maxime partiale egale atunci clar alegem pe st
  // daca x[0..k-1] sunt pozitiile din stiva
  // atunci are sens sa luam doar o pozitie de tipul x[i] + 1
  // obs: santinela x[-1] = i-k
  // tinem pozitiile de acest tip intr-un multiset
*/

int solve( int n, int k, int *v ){
  ll *ans = new ll[n];

  std::multiset<ll> samples;
  std::deque<int> stack;

  ans[0] = v[0];
  stack.push_back( 0 );

  for( int i = 1 ; i < k ; i++ ){
    while( !stack.empty() && v[stack.back()] < v[i] )
      stack.pop_back();
    stack.push_back( i );

    ans[i] = v[stack.front()];
  }

  // sample stack succesors
  for( int i = 0 ; i + 1 < (int)stack.size() ; i++ )
    samples.insert( ans[stack[i]] + v[stack[i + 1]] );
  samples.insert( +INF ); // santinela
  
  for( int i = k ; i < n ; i++ ){
    ans[i] = min( ans[i - k] + v[stack.front()], *samples.begin() );

    // adaugam v[i + 1], scoatem v[i - k + 1]
    if( i + 1 < n ){
      // push
      while( !stack.empty() && v[stack.back()] < v[i + 1] ){
        int popped = stack.back();
        stack.pop_back();
        
        if( !stack.empty() )
          samples.erase( samples.find( ans[stack.back()] + v[popped] ) );
      }

      if( !stack.empty() )
        samples.insert( ans[stack.back()] + v[i + 1] );
      stack.push_back( i + 1 );

      // pop
      int j = i - k + 1; // pentru convenienta
      if( stack.front() == j ){
        stack.pop_front();

        if( !stack.empty() )
          samples.erase( samples.find( ans[j] + v[stack.front()] ) );
      }
    }
  }

  ll ret = ans_hash( n, ans );
  delete []ans;

  return ret;
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 31
• Subtask 3: 0 / 51