oj.uz

Submission #993424

# Submission time Handle Problem Language Result Execution time Memory
993424 2024-06-05T15:15:42 Z abczz Fish 3 (JOI24_fish3) C++14
100 / 100
 715 ms 122708 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.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.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 Correct 2 ms 1628 KB Output is correct
5 Correct 2 ms 1628 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 2 ms 1628 KB Output is correct
9 Correct 2 ms 1628 KB Output is correct
10 Correct 2 ms 1624 KB Output is correct
11 Correct 3 ms 1628 KB Output is correct
12 Correct 4 ms 1628 KB Output is correct
13 Correct 2 ms 1628 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 111416 KB Output is correct
2 Correct 309 ms 110648 KB Output is correct
3 Correct 71 ms 1876 KB Output is correct
4 Correct 230 ms 110336 KB Output is correct
5 Correct 221 ms 110380 KB Output is correct
6 Correct 274 ms 110164 KB Output is correct
7 Correct 286 ms 110272 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 5728 KB Output is correct
2 Correct 326 ms 114768 KB Output is correct
3 Correct 347 ms 114772 KB Output is correct
4 Correct 335 ms 114772 KB Output is correct
5 Correct 333 ms 114740 KB Output is correct
6 Correct 335 ms 111696 KB Output is correct
7 Correct 385 ms 111692 KB Output is correct
8 Correct 365 ms 111696 KB Output is correct
9 Correct 369 ms 111700 KB Output is correct
10 Correct 645 ms 112584 KB Output is correct
11 Correct 715 ms 112576 KB Output is correct
12 Correct 546 ms 114384 KB Output is correct
13 Correct 546 ms 114252 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 89876 KB Output is correct
2 Correct 352 ms 111496 KB Output is correct
3 Correct 179 ms 26452 KB Output is correct
4 Correct 346 ms 111492 KB Output is correct
5 Correct 346 ms 102480 KB Output is correct
6 Correct 354 ms 114772 KB Output is correct
7 Correct 326 ms 89144 KB Output is correct
8 Correct 350 ms 114768 KB Output is correct
9 Correct 284 ms 110688 KB Output is correct
10 Correct 275 ms 110672 KB Output is correct
11 Correct 341 ms 111444 KB Output is correct
12 Correct 294 ms 110672 KB Output is correct
13 Correct 361 ms 114484 KB Output is correct
14 Correct 255 ms 110416 KB Output is correct
15 Correct 410 ms 114484 KB Output is correct
16 Correct 256 ms 110288 KB Output is correct

Subtask #5
36.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 Correct 2 ms 1628 KB Output is correct
5 Correct 2 ms 1628 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 2 ms 1628 KB Output is correct
9 Correct 2 ms 1628 KB Output is correct
10 Correct 2 ms 1624 KB Output is correct
11 Correct 3 ms 1628 KB Output is correct
12 Correct 4 ms 1628 KB Output is correct
13 Correct 2 ms 1628 KB Output is correct
14 Correct 369 ms 111416 KB Output is correct
15 Correct 309 ms 110648 KB Output is correct
16 Correct 71 ms 1876 KB Output is correct
17 Correct 230 ms 110336 KB Output is correct
18 Correct 221 ms 110380 KB Output is correct
19 Correct 274 ms 110164 KB Output is correct
20 Correct 286 ms 110272 KB Output is correct
21 Correct 109 ms 5728 KB Output is correct
22 Correct 326 ms 114768 KB Output is correct
23 Correct 347 ms 114772 KB Output is correct
24 Correct 335 ms 114772 KB Output is correct
25 Correct 333 ms 114740 KB Output is correct
26 Correct 335 ms 111696 KB Output is correct
27 Correct 385 ms 111692 KB Output is correct
28 Correct 365 ms 111696 KB Output is correct
29 Correct 369 ms 111700 KB Output is correct
30 Correct 645 ms 112584 KB Output is correct
31 Correct 715 ms 112576 KB Output is correct
32 Correct 546 ms 114384 KB Output is correct
33 Correct 546 ms 114252 KB Output is correct
34 Correct 313 ms 89876 KB Output is correct
35 Correct 352 ms 111496 KB Output is correct
36 Correct 179 ms 26452 KB Output is correct
37 Correct 346 ms 111492 KB Output is correct
38 Correct 346 ms 102480 KB Output is correct
39 Correct 354 ms 114772 KB Output is correct
40 Correct 326 ms 89144 KB Output is correct
41 Correct 350 ms 114768 KB Output is correct
42 Correct 284 ms 110688 KB Output is correct
43 Correct 275 ms 110672 KB Output is correct
44 Correct 341 ms 111444 KB Output is correct
45 Correct 294 ms 110672 KB Output is correct
46 Correct 361 ms 114484 KB Output is correct
47 Correct 255 ms 110416 KB Output is correct
48 Correct 410 ms 114484 KB Output is correct
49 Correct 256 ms 110288 KB Output is correct
50 Correct 347 ms 122708 KB Output is correct
51 Correct 344 ms 116048 KB Output is correct
52 Correct 378 ms 119380 KB Output is correct
53 Correct 674 ms 120360 KB Output is correct
54 Correct 582 ms 122056 KB Output is correct
55 Correct 342 ms 122444 KB Output is correct
56 Correct 268 ms 118140 KB Output is correct
57 Correct 238 ms 114984 KB Output is correct
58 Correct 229 ms 115024 KB Output is correct
59 Correct 374 ms 120400 KB Output is correct
60 Correct 273 ms 118352 KB Output is correct
61 Correct 645 ms 120184 KB Output is correct
62 Correct 344 ms 117708 KB Output is correct
63 Correct 595 ms 121800 KB Output is correct
64 Correct 283 ms 118096 KB Output is correct