oj.uz

Submission #984708

# Submission time Handle Problem Language Result Execution time Memory
984708 2024-05-17T03:12:30 Z vjudge2 Fish 3 (JOI24_fish3) C++17
20 / 100
 119 ms 17352 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 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 1 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 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 82 ms 11932 KB Output is correct
2 Correct 87 ms 13908 KB Output is correct
3 Correct 66 ms 4680 KB Output is correct
4 Correct 103 ms 13908 KB Output is correct
5 Correct 104 ms 15700 KB Output is correct
6 Correct 112 ms 17316 KB Output is correct
7 Correct 106 ms 14792 KB Output is correct
8 Correct 114 ms 17352 KB Output is correct
9 Correct 76 ms 13140 KB Output is correct
10 Correct 74 ms 12880 KB Output is correct
11 Correct 96 ms 13904 KB Output is correct
12 Correct 99 ms 13584 KB Output is correct
13 Correct 112 ms 17192 KB Output is correct
14 Correct 80 ms 13084 KB Output is correct
15 Correct 119 ms 16944 KB Output is correct
16 Correct 78 ms 12964 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 1 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -