Submission #1112240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112240		zxcigan	Fish 3 (JOI24_fish3)	C++17	9 / 100	2067 ms	167964 KiB

Main

#include <bits/stdc++.h>

using namespace std;

mt19937_64 rng(time(0));

using ll = long long;
#define int long long

const int N = 2e5 + 1;

void solve() {
    int n, d; cin >> n >> d;
    vector<int> c(n + 1), pref (n + 1), a(n + 1), b(n + 1);
    vector<int>p2(n + 1);
    vector<int>p3(n + 1);
    vector<int>p4(n + 1);

    for (int i = 1; i <= n; ++i) {
        cin >> c[i];
        a[i] = c[i] / d;
        b[i] = c[i] % d;
        pref[i] = pref[i - 1] + c[i];
        p2[i] = p2[i - 1] + a[i];
    }
    for (int i = 1; i < n; ++i) {
        p3[i] = p3[i - 1] + bool (b[i] > b[i + 1]);
        p4[i] = p4[i - 1] + (b[i] > b[i + 1] ? i : 0);
    }
    int q; cin >> q;
    vector<int> id(n + 1);
    for (int i = 1; i <= n; ++i) {
        int nw = a[i];
        for (int j = i - 1; j >= 1; j -= 1) {
            if (a[j] >= nw) {
                if (b[j] > b[j + 1]) nw -= 1;
            } else {
                id[i] = j;
                break;
            }
        }
    }
    vector<vector<int>> W (20, vector<int> (n + 1));
    vector<vector<int>> binup (20, vector<int> (n + 1));
    vector<vector<int>> cost (20, vector<int> (n + 1));
    for (int i = n; i >= 1; --i) {
        binup[0][i] = id[i];
        int ps = id[i] + 1, r = i;
        int ans = p2[r - 1] - p2[ps - 1];
        ans -= a[r] * (r - ps);
        int all = p4[r - 1] - p4[ps - 1];
        int cnt = p3[r - 1] - p3[ps - 1];
        ans += all - (ps - 1) * cnt;
        W[0][i] += cnt;
        cost[0][i] += ans;
    }
    for (int j = 1; j < 20; ++j) {
        for (int i = 1; i <= n; ++i) {
            binup[j][i] = binup[j - 1][binup[j - 1][i]];
            cost[j][i] = cost[j - 1][i] + cost[j - 1][binup[j - 1][i]];
            W[j][i] = W[j - 1][i] + W[j - 1][binup[j - 1][i]];
        }
    }

    while (q--) {
        int l, r; cin >> l >> r;
        int v = r;
        int ans = 0;
        int mn = a[r];
        for (int pw = 19; pw >= 0; --pw) {
            if (binup[pw][v] > l) {
                ans += cost[pw][v];
                mn -= W[pw][v];
                v = binup[pw][v];
            }
        }
        mn = a[v];
        int ps = max (id[v] + 1, l);
        ans += p2[v - 1] - p2[ps - 1];
        ans -= a[v] * (v - ps);
        int all = p4[v - 1] - p4[ps - 1];
        int cnt = p3[v - 1] - p3[ps - 1];
        ans += all - (ps - 1) * cnt;
        mn -= cnt;
        if (mn < 0) {
            cout << "-1\n";
            continue;
        }
        cout << ans << '\n';

    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // LOCAL
    int T = 1;
    while (T--) solve();
    return 0;
}

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