Submission #1112243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112243		zxcigan	Fish 3 (JOI24_fish3)	C++17	100 / 100	680 ms	227880 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 = 3e5 + 1;
int lg[N];
void build_lg () {
    for (int i = 0; i < N; ++ i) lg[i] = __lg(i);
}
struct sparse {
    vector < int > t[21];

    void build (vector<int>&e) {
        int _n = (int)e.size();
        for (int i = 0; i <= 20; ++ i) {
            t[i].resize (_n + 1, -1e18);
        }

        for (int i = 1; i <= _n; ++ i) {
            t[0][i] = e[i];
        }


        for (int l = 1; l <= 20; ++ l) {
            for (int i = 1; i <= _n - (1ll << l) + 1; ++ i) {
                t[l][i] = min (t[l - 1][i], t[l - 1][i + (1ll << (l - 1))]);
            }
        }
    }

    int get (int l, int r) {
        if (l > r) return 1e18;
        int L = lg[r - l + 1];
        return min (t[L][l], t[L][r - (1ll << L) + 1]);
    }
} T;

void solve() {
    build_lg();
    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);
    vector<int> e(n + 1);
    for (int i = 1; i <= n; ++i) e[i] = a[i] - p3[i];
    T.build (e);
    for (int i = 1; i <= n; ++i) {
        int l = 1, r = i - 1;
        while (l < r) {
            int mid = (1 + r + l) >> 1;
            if (T.get(mid, i - 1) >= a[i] - p3[i - 1]) r = mid - 1;
            else l = mid;
        }
        if (T.get (l, i - 1) < a[i] - p3[i - 1]) id[i] = l;
    }
    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: 7 / 7
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36