oj.uz

Submission #984701

# Submission time Handle Problem Language Result Execution time Memory
984701 2024-05-17T03:08:35 Z vjudge2 Fish 3 (JOI24_fish3) C++17
27 / 100
 161 ms 17632 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k, q;
    cin >> n >> k;
    vector<int> c(n+1), ac(n+1, 0), a(n+1, 0), b(n+1, 0), aff(n+1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        ac[i] = c[i];
    }
    int prv = n;
    for (int i = n - 1; i >= 1; i--) {
        if (ac[i] > ac[i + 1]) {
            int diff = ac[i] - ac[i + 1];
            diff = (diff + k - 1) / k;
            a[i] += diff;
            ac[i] -= diff * k;
        } else {
            int t = 0;
            for (int j = i + 1; j <= prv; j++) t++, aff[j] = t;
            prv = i;
        }
    }
    int t = 0;
    for (int j = 1; j <= prv; j++) t++, aff[j] = t;
    for (int i = 1; i <= n; i++) a[i] += a[i - 1];
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        // cout << a[r] - a[l - 1] << '\n';
        // cout << ((c[r] - ac[r]) / k) * (r - l + 1) << '\n';
        int L = ac[l], R = ac[r];
        L += (c[r] - R);
        if (L < 0) cout << "-1\n";
        else cout << a[r] - a[l - 1] - ((c[r] - ac[r]) / k) * min(aff[r], r - l + 1) << '\n';
    }
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 604 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 94 ms 13764 KB Output is correct
2 Correct 86 ms 17632 KB Output is correct
3 Correct 56 ms 3984 KB Output is correct
4 Correct 102 ms 17448 KB Output is correct
5 Correct 67 ms 17488 KB Output is correct
6 Correct 98 ms 17320 KB Output is correct
7 Correct 99 ms 17212 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 4944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 11864 KB Output is correct
2 Correct 108 ms 14004 KB Output is correct
3 Correct 67 ms 4688 KB Output is correct
4 Correct 112 ms 13844 KB Output is correct
5 Correct 161 ms 15820 KB Output is correct
6 Correct 114 ms 17280 KB Output is correct
7 Correct 115 ms 14744 KB Output is correct
8 Correct 115 ms 17236 KB Output is correct
9 Correct 98 ms 13148 KB Output is correct
10 Correct 68 ms 12972 KB Output is correct
11 Correct 101 ms 14024 KB Output is correct
12 Correct 102 ms 13136 KB Output is correct
13 Correct 108 ms 17128 KB Output is correct
14 Correct 83 ms 13072 KB Output is correct
15 Correct 125 ms 16980 KB Output is correct
16 Correct 83 ms 12952 KB Output is correct

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -