oj.uz

Submission #646336

# Submission time Handle Problem Language Result Execution time Memory
646336 2022-09-29T15:00:39 Z Alex_tz307 Peru (RMI20_peru) C++17
0 / 100
 1 ms 340 KB 
#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) {
    prv[i] = 0;
    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]);
  }

  return res;
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 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 340 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 340 KB Output isn't correct
2 Halted 0 ms 0 KB -