Submission #401768

#	Time	Username	Problem	Language	Result	Execution time	Memory
401768		rama_pang	Peru (RMI20_peru)	C++17	100 / 100	311 ms	244808 KiB

peru

#include "peru.h"

#include <bits/stdc++.h>
using namespace std;

using lint = long long;
const lint INF = 1e18;

const int MAX = 2.5e6 + 5;

int N, K;
int A[MAX];

lint dp[MAX];
int left_geq[MAX];

int minqhead = 0;
int minqtail = 0;
pair<int, long long> minq[MAX];

int minstsz = 0;
int minst[MAX];

void InsertMinQueue(int p, long long x) {
  while (minqhead < minqtail && minq[minqtail - 1].second >= x) {
    minqtail--;
  }
  minq[minqtail++] = {p, x};
}

void PopQueue(int p) {
  while (minqhead < minqtail && minq[minqhead].first < p) {
    minqhead++;
  }
}

int cost[MAX]; // cost[i] = maximum value in [i - K + 1, i]
int at_most[MAX]; // at_most[i] = farthest segment for current subtree
vector<int> adj[MAX]; // adjacency list

void Dfs(int u, lint alt_dp) { // subtrees form a contiguous segment, so when we DFS we visit them in order 0, 1, 2, ..
  PopQueue(u - K);
  dp[u] = min({alt_dp, dp[max(u - K, 0)] + cost[u], minqhead == minqtail ? INF : minq[minqhead].second});

  reverse(begin(adj[u]), end(adj[u]));
  assert(is_sorted(begin(adj[u]), end(adj[u])));

  for (auto v : adj[u]) {
    if (u + K < at_most[v]) {
      InsertMinQueue(u, dp[u] + A[v]);
      // Note that, nxt_v has distance > K to u, so dp[u] wouldn't exist anymore in minQueue
      Dfs(v, alt_dp);
    } else {
      Dfs(v, min(alt_dp, dp[u] + A[v]));
    }
  }
}

int solve(int n, int k, int* v) {
  N = n, K = k;
  for (int i = 0; i < N; i++) {
    A[i + 1] = v[i];
  }

  { // Compute left_geq[i] = greatest j < i, s.t. V[j] >= V[i]
    for (int i = 1; i <= N; i++) {
      while (minstsz > 0 && A[minst[minstsz - 1]] < A[i]) {
        minstsz--;
      }
      left_geq[i] = minstsz == 0 ? 0 : minst[minstsz - 1];
      minst[minstsz++] = i;
    }
    minstsz = 0;
  }

  { // Compute cost[i]
    minq[minqtail++] = {0, 0}; // for maxQueue
    for (int i = 1; i <= N; i++) {
      while (minqhead < minqtail && minq[minqhead].first <= i - K) {
        minqhead++;
      }
      while (minqhead < minqtail && minq[minqtail - 1].second <= A[i]) {
        minqtail--;
      }
      minq[minqtail++] = {i, A[i]};
      cost[i] = minq[minqhead].second;
    }
    minqhead = minqtail = 0;
  }

  for (int i = N; i >= 1; i--) {
    int p = left_geq[i];
    adj[p].emplace_back(i);
    at_most[i] = max(at_most[i], i);
    at_most[p] = max(at_most[p], at_most[i]);
  }

  Dfs(0, INF);

  int ans = 0;
  for (int i = 1; i <= N; i++) {
    ans = (1ll * ans * 23 + dp[i]) % int(1e9 + 7);
  }

  return ans;
}

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