Submission #1222266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222266		onbert	Fish 2 (JOI22_fish2)	C++20	8 / 100	4091 ms	7480 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];
vector<int> rng[maxn];

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 = R;
        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++) rng[i] = {i};

    // for (int i=1;i<=n;i++) {
    //     auto [l, r] cur = eat(i);
    //     rng[l].push_back(r);
    // }

    int q;
    cin >> q;
    while (q--) {
        int type, ll, rr;
        cin >> type >> ll >> rr;
        int ans = 0;
        for (int i=ll;i<=rr;i++) {
            auto [l, r] = eat(i, ll, rr);
            ans += (l == ll && r == rr);
        }
        cout << ans << "\n";
    }

}

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