Submission #1222288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222288		onbert	Fish 2 (JOI22_fish2)	C++20	31 / 100	738 ms	13068 KiB

fish2

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 5;
int n;
int a[maxn], sum[maxn];
map<pair<int,int>, vector<int>> rng;

pair<int,int> eat(int i, int ll, int rr) {
    int l = i, r = i;
    while (true) {
        int oldl = l, oldr = r;
        int s = sum[r] - sum[l-1];
        int L = ll, R = l;
        while (L < R) {
            int mid = (L+R)/2;
            if (sum[l-1] - sum[mid-1] <= s) R = mid;
            else L = mid+1;
        }
        l = L;
        s = sum[r] - sum[l-1], L = r, R = rr;
        while (L < R) {
            int mid = (L+R+1)/2;
            if (sum[mid] - sum[r] <= s) L = mid;
            else R = mid-1;
        }
        r = L;
        if (l == oldl && r == oldr) break;
    }
    return {l, r};
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i=1;i<=n;i++) cin >> a[i];
    sum[0] = 0;
    for (int i=1;i<=n;i++) sum[i] = a[i] + sum[i-1];

    for (int i=1;i<=n;i++) {
        auto [l, r] = eat(i, 1, n);
        rng[{l, r}].push_back(i);
    }
    
    for (auto &[x, vec]:rng) {
        sort(vec.begin(), vec.end());
        vec.erase(unique(vec.begin(), vec.end()), vec.end());
        // cout << "range: " << x.first << " " << x.second << endl;
        // for (int i:vec) cout << i << " "; cout << endl;
    }

    int q;
    cin >> q;
    while (q--) {
        int type, ql, qr;
        cin >> type >> ql >> qr;
        if (type == 1) continue;
        auto [l, r] = eat(ql, 1, n);
        while (ql < l || r < qr) {
            pair<int,int> nxt;
            if (ql < l) nxt = eat(l-1, 1, n);
            else if (r < qr) nxt = eat(r+1, 1, n);
            l = nxt.first, r = nxt.second;
        }

        int ll = ql, rr = qr;
        while (true) {
            int nxt = eat(ll, ql, qr).second;
            if (nxt == qr) break;
            ll = nxt + 1;
        }
        while (true) {
            int nxt = eat(rr, ql, qr).first;
            if (nxt == ql) break;
            rr = nxt - 1;
        }

        int ans = upper_bound(rng[{l, r}].begin(), rng[{l, r}].end(), rr) - lower_bound(rng[{l, r}].begin(), rng[{l, r}].end(), ll);
        cout << ans << "\n";
    }

}

• Subtask 1: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 12
• Subtask 4: 23 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17