Submission #1193256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193256		mannshah1211	Fish 3 (JOI24_fish3)	C++20	27 / 100	732 ms	60840 KiB

Main

/**
 *   author: tourist
 *   created: 29.04.2025 17:36:20
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

struct Segment {
  int l, r;

  Segment(int _l, int _r) : l(_l), r(_r) {}
};

class segtree {
 public: 
  vector<__int128> sums, add;
  int n;

  segtree(int _n) : n(_n) {
    sums.resize(4 * n);
    add.resize(4 * n);
  }

  void modify(int l, int r, __int128 x, int ll, int rr, int v) {
    if (ll >= r || l >= rr) {
      return;
    }
    if (ll >= l && rr <= r) {
      add[v] += x;
      sums[v] += ((__int128) (rr - ll)) * x;
      return;
    }
    int m = (ll + rr) >> 1;
    modify(l, r, x, ll, m, 2 * v + 1);
    modify(l, r, x, m, rr, 2 * v + 2);
    sums[v] = sums[2 * v + 1] + sums[2 * v + 2];
  }

  void modify(int l, int r, int x) {
    modify(l, r, x, 0, n, 0);
  }

  __int128 get(int l, int r, int ll, int rr, int v) {
    if (ll >= l && rr <= r) {
      return sums[v];
    }
    if (ll >= r || l >= rr) {
      return 0;
    }
    int m = (ll + rr) >> 1;
    add[2 * v + 1] += add[v];
    add[2 * v + 2] += add[v];
    sums[2 * v + 1] += ((__int128) (m - ll)) * add[v];
    sums[2 * v + 2] += ((__int128) (rr - m)) * add[v];
    add[v] = 0;
    return get(l, r, ll, m, 2 * v + 1) + get(l, r, m, rr, 2 * v + 2);
  }

  __int128 get(int l, int r) {
    return get(l, r, 0, n, 0);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  long long d;
  cin >> d;
  vector<long long> a(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  vector<vector<pair<int, int>>> at(n + 1);
  int q;
  cin >> q;
  for (int qq = 0; qq < q; qq++) {
    int l, r;
    cin >> l >> r;
    at[r].emplace_back(l, qq);
  } 
  vector<long long> ans(q);
  vector<Segment> st;
  st.push_back(Segment(0, 0));
  segtree seg(n + 1);
  for (int i = 1; i <= n; i++) {
    st.push_back(Segment(i, i));
    while (st.size() >= 2) {
      Segment top = st.back(), sec = st[st.size() - 2]; 
      __int128 sf = a[top.l] - (d * seg.get(top.l, top.l + 1)), fs = a[sec.r] - (d * seg.get(sec.r, sec.r + 1));
      if (sf >= fs) {
        break;
      } else {
        __int128 more = (fs - sf + d - 1) / d;
        seg.modify(sec.l, sec.r + 1, more);
        st.pop_back();
        st.pop_back();
        st.push_back(Segment(sec.l, top.r));
      }
    }
    for (auto [l, id] : at[i]) {
      ans[id] = seg.get(l, i + 1);
      if (a[l] < (__int128) d * (__int128) seg.get(l, l + 1)) {
        ans[id] = -1;
      }
    }
  }
  for (int i = 0; i < q; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}

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