Submission #1298355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298355		retarde	Fish 3 (JOI24_fish3)	C++20	28 / 100	565 ms	125456 KiB

Main

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

const int mxn = 3e5 + 5;
int n, d;
int a[mxn];
int pfx[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 build() {
    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);
    }
}

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});}
    build(); for (int i = 1; i <= n; i++) pfx[i] = pfx[i - 1] + a[i];

    // 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;
        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 << '\n';
    }
}

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