제출 #993424

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
993424		abczz	Fish 3 (JOI24_fish3)	C++14	100 / 100	715 ms	122708 KiB

Main

#include <iostream>
#include <vector>
#include <queue>
#include <array>
#define ll long long

using namespace std;

vector <ll> V;
ll n, d, q, a, b, f, s, C[300000], L[300000], P[300000], H[300000], G[300000], bl[300000][19], ps[300000][19];

struct SegTree{
  ll st[1200000];
  void build(ll id, ll l, ll r) {
    if (l == r) {
      st[id] = H[l];
      return;
    }
    ll mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    st[id] = min(st[id*2], st[id*2+1]);
  }
  ll query(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql) return 1e18;
    else if (ql <= l && r <= qr) return st[id];
    ll mid = (l+r)/2;
    return min(query(id*2, l, mid, ql, qr), query(id*2+1, mid+1, r, ql, qr));
  }
}ST;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> d;
  for (int i=0; i<n; ++i) {
    cin >> C[i];
    L[i] = C[i] % d;
    if (i) P[i] = ((L[i]-L[i-1]+d) % d) + P[i-1];
    H[i] = C[i]-P[i];
    G[i] = H[i] + (i ? G[i-1] : 0);
    while (!V.empty()) {
      auto u = V.back();
      if (H[u] >= H[i]) V.pop_back();
      else break;
    }
    if (V.empty()) bl[i][0] = i;
    else {
      ps[i][0] = H[i] * (i-V.back());
      bl[i][0] = V.back();
    }
    //cout << i << " " << bl[i][0] << " " << ps[i][0] << endl;
    V.push_back(i);
  }
  ST.build(1, 0, n-1);
  for (int j=1; j<19; ++j) {
    for (int i=0; i<n; ++i) {
      bl[i][j] = bl[bl[i][j-1]][j-1];
      ps[i][j] = ps[i][j-1] + (bl[i][j] != bl[i][j-1] ? ps[bl[i][j-1]][j-1] : 0);
    }
  }
  cin >> q;
  while (q--) {
    cin >> a >> b;
    --a, --b;
    if (ST.query(1, 0, n-1, a, b) < L[a]-P[a]) {
      cout << "-1\n";
      continue;
    }
    f = (b-a+1) * (L[a]-P[a]);
    s = G[b] - (a ? G[a-1] : 0) + ((b-a+1) * (L[a]-P[a]));
    /*cout << s << endl;
    for (int i=0; i<n; ++i) {
      cout << H[i] + (L[a] - P[a]) << " ";
    }
    cout << endl;*/
    for (int j=18; j>=0; --j) {
      if (bl[b][j] >= a) {
        f += ps[b][j];
        b = bl[b][j];
      }
    }
    //cout << f << endl;
    f += (b-a+1) * H[b];
    cout << (s - f)/d << '\n';
  }
}

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