Submission #1018319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018319		erray	Fish 3 (JOI24_fish3)	C++17	100 / 100	202 ms	44244 KiB

Main

// author: erray
#include <bits/stdc++.h>

#ifdef DEBUG
  #include "debug.h"
#else
  #define debug(...) void(37)
#endif

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N;
  int64_t D;
  cin >> N >> D;
  vector<int64_t> C(N);
  for (int i = 0; i < N; ++i) {
    cin >> C[i];
  }
  reverse(C.begin(), C.end()); //stupid 

  vector<int64_t> suf_md(N);
  suf_md[N - 1] = C[N - 1] % D;
  for (int i = N - 2; i >= 0; --i) {
    suf_md[i] = suf_md[i + 1] + (D + (C[i] - C[i + 1]) % D) % D;
  }
  vector<int64_t> a(N);
  for (int i = 0; i < N; ++i) {
    a[i] = C[i] - suf_md[i];
    assert(a[i] % D == 0);
    a[i] /= D;
  }
  vector<int64_t> pref(N + 1);
  for (int i = 0; i < N; ++i) {
    pref[i + 1] = pref[i] + a[i];
  }

  int Q;
  cin >> Q;
  vector<int> L(Q), R(Q);
  vector<vector<int>> qs(N);
  for (int i = 0; i < Q; ++i) {
    int ll, rr;
    cin >> ll >> rr;
    --ll, --rr;
    L[i] = N - rr - 1;    //this is stupid too
    R[i] = N - ll - 1;
    qs[L[i]].push_back(i);
  }

  vector<int64_t> ans(Q);
  struct S {
    int ind;
    int64_t pref;
  };
  auto Cost = [&](int l, int r) {
    return (pref[r + 1] - pref[l]) - a[l] * (r - l + 1);
  };

  vector<S> st;   
  st.push_back(S{N, 0});
  for (int i = N - 1; i >= 0; --i) {
    while (int(st.size()) > 1 && a[st.back().ind] >= a[i]) {
      st.pop_back();
    }
    st.push_back(S{i, st.back().pref + Cost(i, st.back().ind - 1)});
    for (auto id : qs[i]) {
      int r = R[id];
      debug(id, r);
      int last = int(lower_bound(st.begin(), st.end(), r, [&](S t, int x) {
        return t.ind > x;
      }) - st.begin());
      if (a[st[last].ind] * D + suf_md[r] < 0) {
        ans[id] = -1;
      } else {
        ans[id] = st.back().pref - st[last].pref + Cost(st[last].ind, r);
      }
    }   
  }
  for (int i = 0; i < Q; ++i) {
    cout << ans[i] << '\n';
  }
}                  

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