oj.uz

Submission #1000573

# Submission time Handle Problem Language Result Execution time Memory
1000573 2024-06-17T20:09:47 Z PurpleCrayon Fish 3 (JOI24_fish3) C++17
0 / 100
 2000 ms 10488 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);
    }

    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 (prv[c] + 1 >= l) {
            ll p = 0;
            for (int i = c; i > prv[c] + 1; i--) {
                p -= diff[i];
                ans += p;
            }

            c = prv[c];
        }

        ll p = 0;
        for (int i = c; i >= l; i--) {
            p -= diff[i];
            ans += p;
        }

        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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 2099 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2033 ms 10488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2075 ms 5716 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2075 ms 9312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 2099 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -