oj.uz

답안 #1000578

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1000578 2024-06-17T20:47:19 Z PurpleCrayon Fish 3 (JOI24_fish3) C++17
9 / 100
 2000 ms 17968 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));

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

    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) {
            ans += store[c];
            c = prv[c];
        }

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

        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

# 결과 실행 시간 메모리 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 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 7 ms 604 KB Output is correct
13 Correct 2 ms 600 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2003 ms 16168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 5112 KB Output is correct
2 Execution timed out 2067 ms 17968 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2060 ms 14828 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 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 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 7 ms 604 KB Output is correct
13 Correct 2 ms 600 KB Output is correct
14 Execution timed out 2003 ms 16168 KB Time limit exceeded
15 Halted 0 ms 0 KB -