oj.uz

Submission #1000579

# Submission time Handle Problem Language Result Execution time Memory
1000579 2024-06-17T20:48:42 Z PurpleCrayon Fish 3 (JOI24_fish3) C++17
36 / 100
 2000 ms 30436 KB 
#include <bits/stdc++.h>
using namespace std;

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 3e5+10, MOD = 1e9+7;
const ll INF = 1e18+10;

ll ceil_div(ll x, ll y) {
    return (x + y - 1) / y;
}

void solve() {
    int n; ll k; cin >> n >> k;
    vector<ll> a(n); for (auto& x : a) cin >> x;
    vector<ll> diff(n-1);
    for (int i = 0; i < n-1; i++) {
        if (a[i] <= a[i+1])
            diff[i] = max(0LL, (a[i+1] - a[i]) / k);
        else
            diff[i] = -ceil_div(a[i] - a[i+1], k);
    }

    vector<ll> ps_diff = diff;
    for (int i = 1; i < n-1; i++) {
        ps_diff[i] += ps_diff[i-1];
    }

    vector<int> prv(n-1, -2); // previous thing less than it

    vector<int> stk;
    for (int i = 0; i < n-1; i++) {
        while (sz(stk) && ps_diff[stk.back()] >= ps_diff[i]) stk.pop_back();
        if (sz(stk)) prv[i] = stk.back();
        else prv[i] = ps_diff[i] > 0 ? -1 : -2;
        stk.push_back(i);
    }

    vector<ll> suf1 = diff; suf1.push_back(0);
    for (int i = sz(diff)-1; i >= 0; i--) {
        suf1[i] += suf1[i+1];
    }

    vector<ll> suf2 = suf1;
    for (int i = sz(diff)-1; i >= 0; i--) {
        suf2[i] += suf2[i+1];
    }

    auto qry = [&](int l, int r) {
        if (l > r) return 0LL;
        return -(suf2[l] - suf2[r+1] - suf1[r+1] * (r - l + 1));
    };

    vector<ll> store(n-1);
    for (int i = 0; i < n-1; i++) {
        store[i] = qry(prv[i] + 2, i);
    }

    int q; cin >> q;
    while (q--) {
        int l, r; cin >> l >> r, --l, --r;
        if (l == r) {
            ll ans = 0;
            ll p = 0;
            for (int i = r-1; i >= l; i--) {
                if (p >= diff[i]) {
                    p -= diff[i];
                } else {
                    p = 0;
                }

                ans += p;
            }

            if (a[l] - k * p >= 0)
                cout << ans << '\n';
            else
                cout << -1 << '\n';

            continue;
        }

        ll ans = 0;
        int c = r-1;
        while (c >= 0 && prv[c] + 1 >= l) { // slow
            ans += store[c]; 
            c = prv[c];
        }

        ll p = 0;
        if (l <= c) {
            p -= (suf1[l] - suf1[c+1]);
        }
        ans += qry(l, c);

        if (a[l] - k * p >= 0)
            cout << ans << '\n';
        else
            cout << -1 << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

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 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 8 ms 640 KB Output is correct
13 Correct 1 ms 604 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 21800 KB Output is correct
2 Correct 79 ms 21800 KB Output is correct
3 Correct 41 ms 3924 KB Output is correct
4 Correct 72 ms 21192 KB Output is correct
5 Correct 73 ms 21184 KB Output is correct
6 Correct 79 ms 22404 KB Output is correct
7 Correct 71 ms 20992 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 5204 KB Output is correct
2 Correct 127 ms 24364 KB Output is correct
3 Correct 148 ms 30180 KB Output is correct
4 Correct 128 ms 30436 KB Output is correct
5 Correct 131 ms 28888 KB Output is correct
6 Correct 95 ms 24104 KB Output is correct
7 Correct 92 ms 22312 KB Output is correct
8 Correct 101 ms 25896 KB Output is correct
9 Correct 101 ms 25680 KB Output is correct
10 Execution timed out 2057 ms 21628 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 18364 KB Output is correct
2 Correct 73 ms 23040 KB Output is correct
3 Correct 59 ms 9552 KB Output is correct
4 Correct 91 ms 26684 KB Output is correct
5 Correct 89 ms 26944 KB Output is correct
6 Correct 95 ms 28796 KB Output is correct
7 Correct 88 ms 25376 KB Output is correct
8 Correct 91 ms 30268 KB Output is correct
9 Correct 77 ms 22576 KB Output is correct
10 Correct 70 ms 22824 KB Output is correct
11 Correct 88 ms 26128 KB Output is correct
12 Correct 86 ms 26176 KB Output is correct
13 Correct 102 ms 29996 KB Output is correct
14 Correct 85 ms 24108 KB Output is correct
15 Correct 97 ms 29736 KB Output is correct
16 Correct 89 ms 25740 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 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 8 ms 640 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 114 ms 21800 KB Output is correct
15 Correct 79 ms 21800 KB Output is correct
16 Correct 41 ms 3924 KB Output is correct
17 Correct 72 ms 21192 KB Output is correct
18 Correct 73 ms 21184 KB Output is correct
19 Correct 79 ms 22404 KB Output is correct
20 Correct 71 ms 20992 KB Output is correct
21 Correct 54 ms 5204 KB Output is correct
22 Correct 127 ms 24364 KB Output is correct
23 Correct 148 ms 30180 KB Output is correct
24 Correct 128 ms 30436 KB Output is correct
25 Correct 131 ms 28888 KB Output is correct
26 Correct 95 ms 24104 KB Output is correct
27 Correct 92 ms 22312 KB Output is correct
28 Correct 101 ms 25896 KB Output is correct
29 Correct 101 ms 25680 KB Output is correct
30 Execution timed out 2057 ms 21628 KB Time limit exceeded
31 Halted 0 ms 0 KB -