Submission #646338

#	Time	Username	Problem	Language	Result	Execution time	Memory
646338		Alex_tz307	Peru (RMI20_peru)	C++17	100 / 100	106 ms	65756 KiB

peru

#include <bits/stdc++.h>
#include "peru.h"
 
using namespace std;
 
const int base = 23;
const int mod = 1e9 + 7;
const int kN = 2e6 + 5e5;
const int64_t INF = 1e18L;
 
int a[1 + kN], st[1 + kN], prv[1 + kN], nxt[1 + kN], dqMax[kN], dq[kN], stk[1 + kN];
int64_t dp[1 + kN];
 
void minSelf(int64_t &x, int64_t y) {
  if (y < x) {
    x = y;
  }
}
 
int64_t cost(int index) {
  return dp[prv[index]] + a[index];
}
 
int add(int x, int y) {
  x += y;
  if (x >= mod) {
    x -= mod;
  }
  return x;
}
 
int mult(int x, int y) {
  return (int64_t)x * y % mod;
}
 
int solve(int n, int k, int* v) {
  for (int i = 1; i <= n; ++i) {
    a[i] = v[i - 1];
  }
 
  int vf = 0;
  for (int i = 1; i <= n; ++i) {
    nxt[i] = n + 1;
    
    while (vf && a[st[vf]] <= a[i]) { /// <=
      nxt[st[vf]] = i;
      vf -= 1;
    }
    
    prv[i] = st[vf];
    st[++vf] = i;
  }
 
  int res = 0, l = 0, r = -1, lmax = 0, rmax = -1;
  vf = 0;
  for (int i = 1; i <= n; ++i) {
    while (vf && a[stk[vf]] <= a[i]) { /// <=
      vf -= 1;
    }
 
    if (nxt[i] - prv[i] >= k) {
      while (l <= r && cost(i) <= cost(dq[r])) {
        r -= 1;
      }
      dq[++r] = i;
    } else if (vf == 0 || cost(i) < cost(stk[vf])) {
      stk[++vf] = i;
    }
 
    while (l <= r && prv[dq[l]] <= i - k) {
      l += 1;
    }
 
    while (lmax <= rmax && a[dqMax[rmax]] <= a[i]) {
      rmax -= 1;
    }
    dqMax[++rmax] = i;
    while (dqMax[lmax] <= i - k) {
      lmax += 1;
    }
 
    if (i >= k) {
      dp[i] = dp[i - k] + a[dqMax[lmax]];
    } else {
      dp[i] = a[dqMax[lmax]];
    }
    if (l <= r) {
      minSelf(dp[i], cost(dq[l]));
    }
    if (vf) {
      minSelf(dp[i], cost(stk[vf]));
    }
 
    res = add(mult(res, base), dp[i] % mod);
  }
 
  return res;
}

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