Submission #1169761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169761		fryingduc	Fish 3 (JOI24_fish3)	C++20	100 / 100	492 ms	125460 KiB

Main

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 3e5 + 5;
const int LG = 19;
int n, q;
long long d, c[maxn];
long long prf[maxn], df[maxn];
long long ps[maxn];
long long st[maxn][LG + 1];

vector<int> g[maxn];
int pr[maxn], up[maxn][LG + 1];
long long dep[maxn];

void pre_dfs(int u) {
  for (auto v : g[u]) {
    up[v][0] = u;
    for (int i = 1; i <= LG; ++i) {
      up[v][i] = up[up[v][i - 1]][i - 1];
    }
    dep[v] = dep[u] + 1ll * (v - u) * (c[v] - prf[v]);
    pre_dfs(v);
  }
}

long long qry(int l, int r) {
  int p = 31 - __builtin_clz(r - l + 1);
  return min(st[l][p], st[r - (1 << p) + 1][p]);
}

void solve() {
  cin >> n >> d;
  for (int i = 1; i <= n; ++i) {
    cin >> c[i];
  }
  for (int i = 1; i <= n; ++i) {
    df[i] = (d + (c[i] % d) - (c[i - 1] % d)) % d;
    prf[i] = prf[i - 1] + df[i];
    ps[i] = ps[i - 1] + c[i] - prf[i];
    st[i][0] = c[i] - prf[i];
  }
  for (int j = 1; j <= LG; ++j) {
    for (int i = 1; i + (1 << j) <= n + 1; ++i) {
      st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    }
  }
  stack<int> st;
  for (int i = 1; i <= n; ++i) {
    while (!st.empty() and c[st.top()] - prf[st.top()] >= c[i] - prf[i]) st.pop();
    pr[i] = (st.empty() ? 0 : st.top());
    g[pr[i]].push_back(i);
    st.push(i);
  }
  pre_dfs(0);
  cin >> q;
  while (q--) {
    int l, r; cin >> l >> r;
    long long offset = prf[l] - (c[l] % d);
    if (qry(l, r) + offset < 0) {
      cout << -1 << '\n';
      continue;
    }
    int u = r;
    long long res = 0;
    for (int i = LG; i >= 0; --i) {
      if (up[u][i] >= l) {
        u = up[u][i];
      }
    }
    res = dep[r] - dep[u] + 1ll * (c[u] - prf[u]) * (u - l + 1);
    res = (ps[r] - ps[l - 1] - res);
    cout << res / d << '\n';
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 7 / 7
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36