Submission #1053644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053644		juicy	Fish 3 (JOI24_fish3)	C++17	28 / 100	136 ms	38264 KiB

Main

#include <bits/stdc++.h>

using namespace std;

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

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
 
  int n; long long d; cin >> n >> d;
  auto get = [&](long long i, long long j) {
    if ((i -= j) < 0) {
      i += d;
    }
    return i;
  };
  vector<long long> c(n), pf(n), a(n), sum(n);
  for (int i = 0, rem = 0; i < n; ++i) {
    cin >> c[i];
    pf[i] = (i ? pf[i - 1] : 0) + get(c[i] % d, rem);
    rem = c[i] % d;
    a[i] = c[i] - pf[i];
    sum[i] = (i ? sum[i - 1] : 0) + a[i];
  }
  int q; cin >> q;
  vector<array<int, 3>> queries;
  for (int i = 0; i < q; ++i) {
    int l, r; cin >> l >> r; --l, --r;
    queries.push_back({l, r, i});
  }
  sort(queries.begin(), queries.end(), [&](const auto &a, const auto &b) {
    return a[1] < b[1];
  });
  vector<pair<int, long long>> st = {{-1, 0}};
  vector<long long> res(q);
  auto Sum = [&](int l, int r) {
    return sum[r] - (l == 0 ? 0 : sum[l - 1]);
  };
  auto qry = [&](int i, int j) -> long long {
    auto it = lower_bound(st.begin(), st.end(), pair<int, long long>{i, 0});
    auto [p, s] = *it;
    long long rem = c[i] % d;
    if (a[p] + pf[i] - rem < 0) {
      return -1;
    }
    long long res = st.back().second - s + a[p] * (p - i + 1);
    return (Sum(i, j) - res) / d;
  };  
  for (int i = 0, j = 0; i < n; ++i) {
    while (st.size() > 1 && a[st.back().first] >= a[i]) {
      st.pop_back();
    }
    st.push_back({i, st.back().second + (i - st.back().first) * a[i]});
    while (j < q && queries[j][1] == i) {
      res[queries[j][2]] = qry(queries[j][0], i);
      ++j;
    }
  }
  for (int i = 0; i < q; ++i) {
    cout << res[i] << "\n";
  }
  return 0;
}

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