Submission #858138

#	Time	Username	Problem	Language	Result	Execution time	Memory
858138		mircea_007	Peru (RMI20_peru)	C++17	100 / 100	322 ms	57884 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;

  for( int i = 0 ; 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++ ){
    // adaugam v[i], scoatem v[i - k]

    // push
    while( !stack.empty() && v[stack.back()] < v[i] ){
      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] );
    stack.push_back( i );

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

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

    ans[i] = min( ans[i - k] + v[stack.front()], *samples.begin() );
  }

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

  return ret;
}

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