Submission #1298380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298380		retarde	Fish 3 (JOI24_fish3)	C++20	100 / 100	645 ms	136100 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];
    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];
    for (int i = 1; i <= n; i++) tmp.push_back({a[i], i});
    buildpre(); buildst(1, 1, 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};
        }
    }

    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;
        }

        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];

        cout << sm/d << '\n';
    }
}

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