Submission #903847

#	Time	Username	Problem	Language	Result	Execution time	Memory
903847		LucaIlie	Fish 2 (JOI22_fish2)	C++17	13 / 100	4056 ms	3364 KiB

fish2

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
int v[MAX_N + 1], leftt[MAX_N + 1], rightt[MAX_N + 1];
long long s[MAX_N + 1];

void init( int n ) {
    for ( int i = 1; i <= n; i++ )
        s[i] = s[i - 1] + v[i];

    for ( int i = 1; i < n; i++ ) {
        int l = 0, r = i + 1;
        while ( r - l > 1 ) {
            int mid = (l + r) / 2;
            if ( s[i] - s[mid - 1] >= v[i + 1] )
                l = mid;
            else
                r = mid;
        }
        leftt[i] = l;
    }

    for ( int i = 2; i <= n; i++ ) {
        int l = i - 1, r = n + 1;
        while ( r - l > 1 ) {
            int mid = (l + r) / 2;
            if ( s[mid] - s[i - 1] >= v[i - 1] )
                r = mid;
            else
                l = mid;
        }
        rightt[i] = r;
    }
}

int main() {
    cin.tie( NULL );
    cout.tie( NULL );
    ios_base::sync_with_stdio( false );
    
    int n;

    cin >> n;
    for ( int i = 1; i <= n; i++ )
        cin >> v[i];

    init( n );

    int q;
    cin >> q;
    while ( q-- ) {
        int t, l, r;

        cin >> t >> l >> r;

        if ( t == 1 ) {
            v[l] = r;
            init( n );
            continue;
        }

        int ans = 0;
        for ( int i = l; i <= r; i++ ) {
            int p;

            p = i;
            while ( p >= l + 1 && (rightt[p] <= i || (rightt[p] <= r && leftt[rightt[p] - 1] >= p)) )
                p--;

            if ( p != l )
                continue;

            p = i;
            while ( p <= r - 1 && (leftt[p] >= i || (leftt[p] >= l && rightt[leftt[p] + 1] <= p)) )
                p++;
            if ( p == r )
                ans++;
        }

        cout << ans << "\n";
    }

    return 0;
}

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