Submission #1268580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268580		Icelast	Fish 2 (JOI22_fish2)	C++20	5 / 100	83 ms	3396 KiB

fish2

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
void sub1(int n){
    vector<ll> a(n+2);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    a[0] = a[n+1] = INF;
    int q;
    cin >> q;
    for(int i = 1; i <= q; i++){
        int t, x, y, L, R;
        cin >> t;
        if(t == 1){
            cin >> x >> y;
            a[x] = y;
        }else{
            cin >> L >> R;
            int ans = 0;
            for(int i = L; i <= R; i++){
                int l = i, r = i;
                ll sum = a[i];
                for(int j = 1; j <= n; j++){
                    if(l-1 >= L && sum >= a[l-1]){
                        sum += a[l-1];
                        l--;
                    }
                    if(r+1 <= R && sum >= a[r+1]){
                        sum += a[r+1];
                        r++;
                    }
                }
                if(l == L && r == R){
                    ans++;
                }
            }
            cout << ans << "\n";
        }
    }
}
void sub2(int n){
    vector<ll> a(n+2);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    a[0] = a[n+1] = INF;
    int q;
    cin >> q;
    int t, L, R;
    cin >> t >> L >> R;
    vector<ll> f(n+1), g(n+1);
    vector<ll> pf(n+2, 0);
    for(int i = 1; i <= n; i++){
        pf[i] = pf[i-1] + a[i];
    }
    pf[n+1] = INF;
    for(int i = 1; i <= n; i++){
        if(pf[i-1] < a[i]){
            f[i] = -1;
            continue;
        }
        f[i] = upper_bound(pf.begin(), pf.end(), pf[i-1]-a[i]) - pf.begin();
    }
    for(int i = 1; i <= n; i++){
        g[i] = lower_bound(pf.begin(), pf.end(), pf[i]+a[i]) - pf.begin();
    }
    for(int i = 1; i <= n; i++){

    }
}
void solve(){
    int n;
    cin >> n;
    if(n <= 500){
        sub1(n);
    }else{
        sub2(n);
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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