Submission #1184279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184279		rxlfd314	Fish 3 (JOI24_fish3)	C++20	100 / 100	495 ms	66792 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

struct ST {
  struct Node {
    ll sum, Max;
    Node operator+(const Node &other) {
      return {sum + other.sum, max(Max, other.Max)};
    }
  };
  int N;
  vt<Node> st;
  ST(const int n) : N(n), st(n<<1) {}
  void update(int i, const Node v) {
    st[i += N] = v;
    while (i >>= 1)
      st[i] = st[i<<1] + st[i<<1|1];
  }
  Node query(int l, int r) {
    Node ret = {0, 0};
    for (l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
      if (l & 1)
        ret = ret + st[l++];
      if (r & 1)
        ret = ret + st[--r];
    }
    return ret;
  }
};

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  int N; ll D;
  cin >> N >> D;
  vt<ll> A(N+1), B(N+1), X(N+1), C(N+2);
  vt<int> bad(N+1), psum2(N+1);
  FOR(i, 1, N) {
    cin >> A[i];
    B[i] = A[i] % D;
    X[i] = X[i-1] - B[i-1] + (B[i-1] > B[i]) * D + B[i];
    C[i] = A[i] - X[i];
    psum2[i] = psum2[i-1] + (B[i-1] > B[i]);
    int lo = 0, hi = i-1;
    while (lo < hi) {
      const int mid = lo + hi + 1 >> 1;
      if (D * (psum2[i] - psum2[mid]) + B[i] > A[i])
        lo = mid;
      else
        hi = mid - 1;
    }
    bad[i] = lo;
    #ifdef DEBUG
    cout << i << ": " << C[i] << ' ' << X[i] << '\n';
    #endif
  }
  
  vt<int> stk, parent(N+1);
  vt<vt<int>> adj(N+2);
  vt<ll> depth(N+2), psum(N+2);
  ROF(i, N, 1) {
    while (size(stk) && C[stk.back()] > C[i])
      stk.pop_back();
    parent[i] = size(stk) ? stk.back() : N + 1;
    stk.push_back(i);
    depth[i] = C[i] - C[parent[i]] + depth[parent[i]];
    adj[parent[i]].push_back(i);
    #ifdef DEBUG
    cout << "parent " << i << ": " << parent[i] << ' ' << depth[i] << '\n';
    #endif
  }
  
  FOR(i, 1, N)
    psum[i] = psum[i-1] + depth[i];
  
  int Q; cin >> Q;
  vt<vt<ari2>> sweep(N+1);
  FOR(i, 0, Q-1) {
    int l, r;
    cin >> l >> r;
    sweep[r].push_back({l, i});
  }
  
  vt<ll> ans(Q);
  set<int> roots;
  ST st(N+1);
  vt<int> szs(N+1);
  FOR(i, 1, N) {
    szs[i] = 1;
    for (const auto &j : adj[i]) {
      szs[i] += szs[j];
      st.update(j, {0, bad[j]});
      roots.erase(roots.find(j));
    }
    roots.insert(i);
    st.update(i, {depth[i] * szs[i], bad[i]});
    for (const auto &[j, qi] : sweep[i]) {
      if (st.query(j, i).Max >= j)
        ans[qi] = -1;
      else {
        const int y = *roots.lower_bound(j);
        ans[qi] = psum[i] - psum[j-1] - st.query(y+1, i).sum - depth[y] * (y - j + 1);
        ans[qi] /= D;
#ifdef DEBUG
        cout << "yeet: " << psum[i] - psum[j-1] << ' ' << st.query(y+1, i).sum << ' ' << depth[y] << ' ' << (y - j + 1) << '\n';
#endif
      }
    }
  }

  for (const auto &i : ans)
    cout << i << '\n';
}

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