Submission #1298374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298374		retarde	Fish 3 (JOI24_fish3)	C++20	0 / 100	2102 ms	131460 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int mxn = 3e5 + 5;
int n, d;
int a[mxn], pfx[mxn], bad[mxn], seg[4 * mxn];
pair<int, int> up[mxn][20];
vector<pair<int, int>> tmp;

int sum(int l, int r) {
    if (r < l) return (int)0;
    return pfx[r] - pfx[l - 1];
}

int pre[mxn];
void buildpre() {
    sort(tmp.begin(), tmp.end());
    set<int> add;
    for (auto &x : tmp) {
        int v = x.first, i = x.second;
        if (!add.size()) {
            pre[i] = (int)0;
            add.insert(-i);
            continue;
        }
        if (-*add.rbegin() > i) {
            pre[i] = (int)0;
            add.insert(-i);
            continue;
        }
        pre[i] = -(*add.lower_bound(-i));
        add.insert(-i);
    }
}

void buildst(int x, int l, int r) {
    if (l == r) {
        seg[x] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    buildst(x * 2, l, mid);
    buildst(x * 2 + 1, mid + 1, r);
    seg[x] = min(seg[x * 2], seg[x * 2 + 1]);
}

int queryst(int x, int l, int r, int ql, int qr) {
    if (r < ql || qr < l) return 1e18;
    if (ql <= l && r <= qr) return seg[x];
    int mid = (l + r) / 2;
    return min(queryst(x * 2, l, mid, ql, qr), queryst(x * 2 + 1, mid + 1, r, ql, qr));
}

signed main() {
    cout.tie(nullptr); cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> n >> d;
    for (int i = 1; i <= n; i++) {cin >> a[i]; tmp.push_back({a[i], i});}
    for (int i = 2; i <= n; i++) if ((a[i] % d) < (a[i - 1] % d)) bad[i]++;
    for (int i = 2; i <= n; i++) bad[i] += bad[i - 1];
    for (int i = 1; i <= n; i++) a[i] -= (a[i] % d + bad[i] * d);
    for (int i = 1; i <= n; i++) pfx[i] = pfx[i - 1] + a[i];
    buildpre(); buildst(1, 1, n);

    // cout << "a:\n";
    // for (int i = 1; i <= n; i++) cout << a[i] << " ";
    // cout << '\n';

    // cout << "bad:\n";
    // for (int i = 1; i <= n; i++) cout << bad[i] << " ";
    // cout << '\n';

    // cout << "pre:\n";
    // for (int i = 1; i <= n; i++) cout << pre[i] << " ";
    // cout << '\n';

    for (int i = 1; i <= n; i++) up[i][0] = {pre[i], sum(pre[i] + 1, i) - (i - pre[i]) * a[i]};
    for (int j = 1; j < 20; j++) {
        for (int i = 1; i <= n; i++) {
            up[i][j] = {up[up[i][j - 1].first][j - 1].first, up[i][j - 1].second + up[up[i][j - 1].first][j - 1].second};
        }
    }

    // for (int i = 1; i <= n; i++) {
    //     cout << sum(pre[i] + 1, i) << " - " << (i - pre[i]) * a[i] << '\n';
    //     cout << up[i][0].fi << " -> " << i << ": " << up[i][0].se << '\n';
    // }

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

        // if (queryst(1, 1, n, l, r) + bad[l] * d < 0) {
        //     cout << "-1\n";
        //     continue;
        // }
        bool fnd = false;
        for (int i = l; i <= r; i++) {
            if (a[i] + bad[l] * d < 0) {
                cout << "-1\n";
                fnd = true;
                break;
            }
        }
        if (fnd) continue;

        int sm = 0; int curr = r;
        for (int i = 19; i >= 0; i--) {
            if (up[curr][i].first >= l) {
                sm += up[curr][i].second;
                curr = up[curr][i].first;
            } 
        }
        sm += sum(l, curr) - (curr - l + 1) * a[curr];

        assert((sm % d) == 0);
        cout << sm/d << '\n';
    }
}

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