제출 #1287687

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287687		duckindog	Fish 2 (JOI22_fish2)	C++20	25 / 100	4094 ms	2396 KiB

fish2

#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
int n, q;
int a[N];
long long pref[N];

int minL[N], maxR[N];

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + a[i];

    cin >> q;
    while (q--) { 
        int type; cin >> type;

        if (type == 1) { 
            int p, x; cin >> p >> x;
            a[p] = x;
            for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + a[i];
        } else { 
            int l, r; cin >> l >> r;

            int answer = 0;
            for (int i = l; i <= r; ++i) minL[i] = maxR[i] = i;
            for (int i = l; i <= r; ++i) { 
                auto&  itL = minL[i];
                auto&  itR = maxR[i];
                
                for (;;) { 
                    bool canGo = false;
                    if (itL > l && a[itL - 1] <= pref[itR] - pref[itL - 1]) { 
                        int nitL = min(itL, minL[itL - 1]),
                            nitR = max(itR, maxR[itL - 1]);
                        itL = nitL;
                        itR = nitR;
                        canGo = true;
                    }
                    if (itR < r && a[itR + 1] <= pref[itR] - pref[itL - 1]) { 
                        int nitL = min(itL, minL[itR + 1]),
                            nitR = max(itR, maxR[itR + 1]);
                        itL = nitL;
                        itR = nitR;
                        canGo = true;
                    }
                
                    if (!canGo) break;
                }
                
                if (itL == l && itR == r) { 
                    answer += 1;
                }
            }
            cout << answer << "\n";
        }
    }
}

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