oj.uz

Submission #858136

# Submission time Handle Problem Language Result Execution time Memory
858136 2023-10-07T13:00:29 Z mircea_007 Peru (RMI20_peru) C++17
0 / 100
 1 ms 348 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -