oj.uz

Submission #993422

# Submission time Handle Problem Language Result Execution time Memory
993422 2024-06-05T15:10:35 Z abczz Fish 3 (JOI24_fish3) C++14
55 / 100
 1174 ms 122636 KB 
#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 >> 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 = 0;
    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];
      }
    }
    f += (b-a+1) * H[b];
    cout << (s - (f + ((b-a+1) * (L[a]-P[a]))))/d << '\n';
  }
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 7 ms 1628 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 792 ms 115860 KB Output is correct
2 Correct 740 ms 115112 KB Output is correct
3 Correct 457 ms 4692 KB Output is correct
4 Correct 669 ms 115028 KB Output is correct
5 Correct 666 ms 114764 KB Output is correct
6 Correct 733 ms 114632 KB Output is correct
7 Correct 720 ms 114600 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 8484 KB Output is correct
2 Correct 847 ms 122524 KB Output is correct
3 Correct 811 ms 122636 KB Output is correct
4 Correct 860 ms 122448 KB Output is correct
5 Correct 818 ms 122516 KB Output is correct
6 Correct 758 ms 116048 KB Output is correct
7 Correct 802 ms 115980 KB Output is correct
8 Correct 810 ms 119380 KB Output is correct
9 Correct 851 ms 119284 KB Output is correct
10 Correct 1174 ms 120248 KB Output is correct
11 Correct 1128 ms 120248 KB Output is correct
12 Correct 1054 ms 122056 KB Output is correct
13 Correct 1050 ms 122052 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 726 ms 94292 KB Output is correct
2 Correct 765 ms 115800 KB Output is correct
3 Correct 625 ms 30320 KB Output is correct
4 Correct 837 ms 119136 KB Output is correct
5 Correct 864 ms 109536 KB Output is correct
6 Correct 885 ms 122384 KB Output is correct
7 Correct 790 ms 95896 KB Output is correct
8 Correct 836 ms 122192 KB Output is correct
9 Correct 714 ms 115024 KB Output is correct
10 Correct 692 ms 114768 KB Output is correct
11 Correct 821 ms 119056 KB Output is correct
12 Correct 779 ms 118328 KB Output is correct
13 Correct 831 ms 122064 KB Output is correct
14 Correct 722 ms 118100 KB Output is correct
15 Correct 837 ms 122096 KB Output is correct
16 Correct 729 ms 118168 KB Output is correct

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 7 ms 1628 KB Output isn't correct
5 Halted 0 ms 0 KB -