Submission #1203463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203463		LucaIlie	Fish 3 (JOI24_fish3)	C++20	20 / 100	313 ms	169932 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct range {
    long long startH, endH, cost;
    int len;
};  


const int MAX_N = 3e5;
const int MAX_LOG_N = 18;
const long long INF = 1e18;
int n;
long long d;
long long a[MAX_N + 1];
range nxt[MAX_LOG_N + 1][MAX_N + 1];

range operator + (range &a, range &b) {
    long long delay = 0;

    if (b.endH < a.startH)
        delay = (a.startH - b.endH + d - 1) / d;

    range ans;
    ans.startH = b.startH;
    ans.endH = a.endH - delay * d;
    ans.cost = a.cost + b.cost + delay * a.len;
    ans.len = a.len + b.len;

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> d;
    for (int i = 1; i <= n; i++) 
        cin >> a[i];
    a[0] = -1;

    for (int i = 1; i <= n; i++) 
        nxt[0][i] = {a[i], a[i], 0, 1};

    for (int p = 1; (1 << p) <= n; p++) {
        for (int i = (1 << p); i <= n; i++) {
            nxt[p][i] = nxt[p - 1][i - (1 << (p - 1))] + nxt[p - 1][i];
            //printf("%d %d %lld %lld\n", p, i, nxt[p][i].endH, nxt[p][i].cost);
        }
    }

    int q;
    cin >> q;
    for (; q > 0; q--) {
        int l, r;
        cin >> l >> r;

        range ans = {a[r], a[r], 0, 1};
        r--;
        for (int p = log2(n); p >= 0; p--) {
            if (r - (1 << p) + 1 >= l) {
                ans = nxt[p][r] + ans; 
                r -= (1 << p);
            }
        }

        cout << (ans.endH < 0 ? -1 : ans.cost) << "\n";
    }

    return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 7
• Subtask 3: 0 / 28
• Subtask 4: 20 / 20
• Subtask 5: 0 / 36