Submission #1288007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288007		duckindog	Fish 2 (JOI22_fish2)	C++20	100 / 100	626 ms	33864 KiB

fish2

#include <bits/stdc++.h>

using namespace std;

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

const int MAX = 1'000'000'001;
namespace IT { 
    struct Info { 
        int sum, cnt, valueEd;
        Info(int sum = 0, int cnt = 0, int valueEd = 0) : sum(sum), cnt(cnt), valueEd(valueEd) {}
    };

    struct Node { 
        int valueL, valueR, sum, cnt;
        vector<Info> L, R;
        Node() : valueL(0), valueR(0), sum(0), cnt(0), L(), R() {}
    };

    Node merge(const Node& lt, const Node& rt) { 
        Node ret;
        ret.valueL = lt.valueL;
        ret.valueR = rt.valueR;
        ret.sum = min(MAX, lt.sum + rt.sum);
        ret.L = lt.L;
        ret.R = rt.R;
        
        vector<Info> vtL = lt.R, vtR = rt.L;
        vtL.push_back({lt.sum, lt.cnt, 0});
        vtR.push_back({rt.sum, rt.cnt, 0});
        vector<Info> addL, addR;

        { // left
            int itL = 0, itR = -1, cnt = vtL[0].cnt;
            int sum = -1, bound = -1;
            for (;;) { 
                sum = min(MAX, vtL[itL].sum + (itR == -1 ? 0 : vtR[itR].sum));
                bound = (itR == -1 ? rt.valueL : vtR[itR].valueEd);
                
                if (sum >= bound && itR < (int)vtR.size() - 1) itR += 1;
                else if (itL == (int)vtL.size() - 1) break;
                else { 
                    if (sum < vtL[itL].valueEd) { 
                        if (itR == (int)vtR.size() - 1) 
                            addR.push_back({sum, cnt, vtL[itL].valueEd});
                        cnt = 0;
                    }
                    cnt += vtL[++itL].cnt;
                }
            }
            if (itR == (int)vtR.size() - 1) ret.cnt += cnt;
            else ret.L.push_back({sum, cnt, bound});
        }
        
        swap(vtL, vtR);

        { // right
            vector<Info> add;
            int itL = 0, itR = -1, cnt = vtL[0].cnt;
            int sum = -1, bound = -1;
            for (;;) { 
                sum = min(MAX, vtL[itL].sum + (itR == -1 ? 0 : vtR[itR].sum));
                bound = (itR == -1 ? lt.valueR : vtR[itR].valueEd);

                if (sum >= bound && itR < (int)vtR.size() - 1) itR += 1;
                else if (itL == (int)vtL.size() - 1) break;
                else { 
                    if (sum < vtL[itL].valueEd) { 
                        if (itR == (int)vtR.size() - 1) 
                            addL.push_back({sum, cnt, vtL[itL].valueEd});
                        cnt = 0;
                    }
                    cnt += vtL[++itL].cnt;
                }
            }
            if (itR == (int)vtR.size() - 1) ret.cnt += cnt;
            else ret.R.push_back({sum, cnt, bound});
        }

        for (const auto& node : addL) ret.L.push_back(node);
        for (const auto& node : addR) ret.R.push_back(node);

        return ret;
    }

    Node f[N << 2];
    void build(int s, int l, int r) { 
        if (l == r) { 
            f[s].valueL = f[s].valueR = f[s].sum = a[l];
            f[s].cnt = 1;
            return;
        }
        int mid = (l + r) >> 1;
        build(s << 1, l, mid);
        build(s << 1 | 1, mid + 1, r);
        f[s] = merge(f[s << 1], f[s << 1 | 1]);
    }
    void update(int s, int l, int r, int p, int x) { 
        if (l == r) { 
            f[s].valueL = f[s].valueR = f[s].sum = x;
            f[s].cnt = 1;
            return;
        }
        int mid = (l + r) >> 1;
        if (p <= mid) update(s << 1, l, mid, p, x);
        else update(s << 1 | 1, mid + 1, r, p, x);
        f[s] = merge(f[s << 1], f[s << 1 | 1]);
    }
    Node query(int s, int l, int r, int u, int v) { 
        if (u <= l && r <= v) return f[s];
        int mid = (l + r) >> 1;
        if (v <= mid) return query(s << 1, l, mid, u, v);
        if (u > mid) return query(s << 1 | 1, mid + 1, r, u, v);
        return merge(query(s << 1, l, mid, u, v), query(s << 1 | 1, mid + 1, r, u, v));
    }
}

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

    IT::build(1, 1, n);
    cin >> q;
    while (q--) { 
        int type; cin >> type;
        if (type == 1) { 
            int p, x; cin >> p >> x;
            IT::update(1, 1, n, p, x);
        } else { 
            int l, r; cin >> l >> r;
            cout << IT::query(1, 1, n, l, r).cnt << "\n";
        }
    }
}

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