Submission #1200750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200750		algoproclub	Fish 3 (JOI24_fish3)	C++20	28 / 100	368 ms	46532 KiB

Main

// UUID: 58aa4312-42b8-4cff-86d7-75d99f849374
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 300'001;
const ll INF = 1e16;

struct segtree {
    vector<ll> tree;
    int n;

    segtree(int n) : n(n) {
        tree.resize(2*n);
    }

    void upd(int u, ll k) {
        tree[u += n] = k;
        for (u /= 2; u >= 1; u /= 2) {
            tree[u] = tree[2*u] + tree[2*u+1];
        }
    }

    ll qry(int l, int r) {
        l += n; r += n;
        ll res = 0;
        while (l <= r) {
            if (l % 2 == 1) res += tree[l++];
            if (r % 2 == 0) res += tree[r--];
            l /= 2; r /= 2;
        }
        return res;
    }
};

ll c[MAXN], ans[MAXN], pref[MAXN], bef[MAXN];
vector<pair<ll, ll>> qrys[MAXN];

void solve() {
    ll n, d; cin >> n >> d;
    for (int i = 1; i <= n; i++) cin >> c[i];
    partial_sum(c, c+MAXN, pref);

    int q; cin >> q;
    for (int i = 1; i <= q; i++) {
        int l, r; cin >> l >> r;
        qrys[r].emplace_back(l, i);
    }

    c[0] = -INF;
    stack<ll> st;
    st.push(0);
    segtree tree(n+1);
    set<int> pos;
    for (ll i = 1; i <= n; i++) {
        while (!st.empty() && c[st.top()] >= c[i]) {
            tree.upd(st.top(), 0);
            pos.erase(st.top());
            st.pop();
        }
        ll j = st.top();
        bef[i] = j;
        st.push(i);
        pos.insert(i);
        tree.upd(i, (i-j)*c[i]);
        for (auto [l, idx] : qrys[i]) {
            ll p = *pos.lower_bound(l);
            ll res = pref[i] - pref[l-1] - tree.qry(p+1, i);
            res -= c[p] * (p-l+1);
            ans[idx] = res;
        }
    }

    for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1; 
    // cin >> t;
    while (t--) solve();
    return 0;
}

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