Submission #1089532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089532		LePhiPhat	Peru (RMI20_peru)	C++17	100 / 100	135 ms	93328 KiB

peru

// @author: Le Phi Phat
#include "peru.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "algo/debug.cpp"
#else
#define debug(...) 42
#define debugArr(...) 42
#endif
using namespace std;

template <class X, class Y> bool mini(X &x, const Y &y) {
  if (x > y) {
    x = y;
    return true;
  }
  return false;
}
template <class X, class Y> bool maxi(X &x, const Y &y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}

using i64 = long long;

using vi = vector<int>;

template <class T> class minStack {
public:
  stack<pair<T, T>> st;

  T getMin() { return st.top().second; }

  T empty() { return st.empty(); }

  int size() { return st.size(); }

  void push(T x) {
    T mn = x;
    if (!empty()) {
      mini(mn, getMin());
    }
    st.push(make_pair(x, mn));
  }

  void pop() { st.pop(); }

  T top() { return st.top().first; }

  void swap(minStack<T> &another) { st.swap(another.st); }
};

template <class T> class minDeque {
public:
  minStack<T> stackF, stackB, stackTmp;

  void rebalance() {
    bool flag = false;
    if (stackF.empty()) {
      stackF.swap(stackB);
      flag = true;
    }

    int sz = stackF.size() / 2;

    while (sz--) {
      stackTmp.push(stackF.top());
      stackF.pop();
    }

    while (!stackF.empty()) {
      stackB.push(stackF.top());
      stackF.pop();
    }

    while (!stackTmp.empty()) {
      stackF.push(stackTmp.top());
      stackTmp.pop();
    }

    if (flag) {
      stackF.swap(stackB);
    }
  }

  bool empty() { return (stackF.empty() && stackB.empty()); }

  int size() { return (stackB.size() + stackF.size()); }

  void push_back(T x) { stackB.push(x); }

  void push_front(T x) { stackF.push(x); }

  void pop_back() {
    assert(stackB.size() || stackF.size());
    if (stackB.empty())
      rebalance();
    stackB.pop();
  }

  void pop_front() {
    assert(stackB.size() || stackF.size());
    if (stackF.empty())
      rebalance();
    stackF.pop();
  }

  T back() {
    if (stackB.empty())
      rebalance();
    return stackB.top();
  }

  T front() {
    if (stackF.empty())
      rebalance();
    return stackF.top();
  }

  T getMin() {
    assert(stackB.size() || stackF.size());

    if (stackF.empty())
      return stackB.getMin();
    if (stackB.empty())
      return stackF.getMin();

    return min(stackF.getMin(), stackB.getMin());
  }
};

void debugNl(minDeque<int> de) {
  cout << "[ ";
  while (de.stackF.size()) {
    cout << de.stackF.top() << ", ";
    de.stackF.pop();
  }
  vector<int> v;
  while (de.stackB.size()) {
    v.push_back(de.stackB.top());
    de.stackB.pop();
  }

  while (not v.empty()) {
    cout << v.back() << ", ";
    v.pop_back();
  }

  cout << "]\n";
}

const i64 MOD = 1'000'000'007;

i64 mul(i64 a, i64 b) { return (a % MOD) * (b % MOD) % MOD; }

int solve(int N, int K, int *S) {
  vector<i64> dp(N + 1, 1e16), save(N + 1, 1e16);
  vector<i64> a(N + 1);
  for (int i = 1; i <= N; i++) {
    a[i] = S[i - 1];
  }

  deque<int> de;
  minDeque<i64> val;
  // multiset<i64> ms;

  dp[0] = 0;
  de.push_back(0);

  for (int i = 1; i <= N; i++) {
    while (!de.empty() && a[de.back()] <= a[i]) {
      int p = de.back();
      de.pop_back();
      if (!de.empty()) {
        val.pop_back();
        // ms.erase(ms.find(dp[de.back()] + a[p]));
      }
    }

    while (!de.empty() && i - de.front() >= K) {
      int p = de.front();
      de.pop_front();

      if (!de.empty()) {
        val.pop_front();
        // ms.erase(ms.find(dp[p] + a[de.front()]));
      }
    }

    if (!de.empty()) {
      val.push_back(dp[de.back()] + a[i]);
      // ms.insert(dp[de.back()] + a[i]);
    }

    de.push_back(i);

    mini(dp[i], dp[max(0, i - K)] + a[de.front()]);

    if (!val.empty()) {
      mini(dp[i], val.getMin());
    }
  }

  // for (int i = 1; i <= N; i++) {
  //   cout << dp[i] << " \n"[i == N];
  // }

  i64 cur = 1, ans = 0;
  for (int i = N; i >= 1; i--) {
    ans = (ans % MOD + mul(cur, dp[i])) % MOD;
    cur = mul(cur, 23);
  }

  return ans;
}

// #ifdef LOCAL
// signed main() {
//   ios::sync_with_stdio(0);
//   cout.tie(0);
//   cin.tie(0);
// #ifdef LOCAL
//   freopen("in", "r", stdin);
// #endif
//   int N = 8, K = 2;
//   cin >> N >> K;

//   int a[N];

//   for (int i = 0; i < N; i++) {
//     cin >> a[i];
//   }

//   cout << solve(N, K, a);
// }
// #endif

Compilation message (stderr)

peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:175:11: warning: unused variable 'p' [-Wunused-variable]
  175 |       int p = de.back();
      |           ^
peru.cpp:184:11: warning: unused variable 'p' [-Wunused-variable]
  184 |       int p = de.front();
      |           ^

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