Submission #1125621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125621		_8_8_	Fish 2 (JOI22_fish2)	C++20	100 / 100	913 ms	78080 KiB

fish2

#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;

const int  N = (int)2e5 + 12, MOD = 998244353;

int n, q, a[N];
ll f[N];

struct dat{
    ll cnt, sum, out;
};
struct node{
    vector<dat> x, y;
    int l, r, res = 0;
    ll sum = 0;
    bool e = 1;
    void init(int i) {
        l = r = i;
        sum = a[i];
        e = 0;
        res = 1;
    }
}t[N * 4];

void add(int pos, ll val) {
    while(pos <= n) {
        f[pos] += val;
        pos += pos & -pos;
    }
}
ll get(int i) {
    ll ret = 0;
    while(i) {
        ret += f[i];
        i -= i & -i;
    }
    return ret;
}
ll get(int l, int r) {
    return get(r) - get(l - 1);
}
node merge(node l, node r) {
    if(l.e) return r;
    if(r.e) return l;
    node res;
    res.e = 0;
    res.l = l.l;res.r = r.r;
    res.sum = l.sum + r.sum;
    l.y.push_back({l.res, l.sum, 0});
    r.x.push_back({r.res, r.sum, 0});
    res.y = r.y;
    res.x = l.x;
    {
        int pl = 0, pr = -1, tot = l.y[0].cnt;
        while(true) {
            ll sum = l.y[pl].sum + (pr == -1 ? 0 : r.x[pr].sum);
            ll c = (pr == -1 ?  a[r.l] : r.x[pr].out);
            if(pr + 1 < (int)r.x.size() && sum >= c) {
                pr++;
                continue;
            } else if(pl == (int)l.y.size() - 1) break;
            else {
                if(sum >= l.y[pl].out) {
                    tot += l.y[++pl].cnt;
                } else {
                    if(pr == (int)r.x.size() - 1) {
                        res.y.push_back({tot, sum, l.y[pl].out});
                    }
                    tot = l.y[++pl].cnt;
                }
            }
        }
        if(pr == (int)r.x.size() - 1) res.res += tot;
        else res.x.push_back({tot, l.sum + (pr == -1 ? 0 : r.x[pr].sum), (pr == -1 ? a[r.l] : r.x[pr].out)});
    }
    {
        int pr = 0, pl = -1, tot = r.x[0].cnt;
        while(true) {
            ll sum = r.x[pr].sum + (pl == -1 ? 0 : l.y[pl].sum);
            ll c = (pl == -1 ? a[l.r] : l.y[pl].out);
            if(pl + 1 < (int)l.y.size() && sum >= c) {
                pl++;
                continue;
            } 
            else if(pr == (int)r.x.size() - 1) break;
            else {
                if(sum >= r.x[pr].out) {
                    tot += r.x[++pr].cnt;
                } else {
                    if(pl == (int)l.y.size() - 1) {
                        res.x.push_back({tot, sum, r.x[pr].out});
                    }
                    tot = r.x[++pr].cnt;
                }
            }
        }
        if(pl == (int)l.y.size() - 1) res.res += tot;
        else res.y.push_back({tot, (pl == -1 ? 0    : l.y[pl].sum) + r.sum, (pl == -1 ? a[l.r] : l.y[pl].out)});
    }
    sort(res.x.begin(), res.x.end(), [&](dat a, dat b){
        return a.sum < b.sum; 
    });
    sort(res.y.begin(), res.y.end(), [&](dat a, dat b){
        return a.sum < b.sum;
    });
    return res;
}

void build(int v = 1, int tl = 1, int tr = n) {
    if(tl == tr) {
        t[v].init(tl);
    } else {
        int tm = (tl + tr) >> 1;
        build(v + v, tl, tm);
        build( v + v + 1, tm + 1, tr);
        t[v] = merge(t[v + v], t[v + v + 1]);
    }
}
void upd(int pos, int val, int v = 1, int tl = 1, int tr = n) {
    if(tl == tr) {
        t[v].init(tl);
    } else {
        int tm = (tl + tr) >> 1;
        if(pos <= tm) upd(pos, val, v + v, tl, tm);
        else upd(pos, val, v + v + 1, tm + 1, tr);
        t[v] = merge(t[v + v], t[v + v + 1]);
    }
}
node qr(int l, int r, int v = 1, int tl = 1, int tr = n) {
    if(l > r || tl > r || l > tr) {
        node nv;
        return nv;
    }
    if(tl >= l && tr <= r) return t[v];
    int tm = (tl + tr) >> 1;
    return merge(qr(l, r, v + v, tl, tm), qr(l, r, v + v + 1, tm + 1, tr));
}
void test() {
    cin >> n;
    
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        add(i, a[i]);
    }
    build();
    // return;
    int q;
    cin >> q;
    while(q--) {
        int tp, l, r;
        cin >> tp >> l >> r;
        if(tp == 1) {
            add(l, r - a[l]);
            a[l] = r;
            upd(l, r);
        } else {
            cout << qr(l, r).res << '\n';
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t = 1, f = clock();
    // cin >> t;

    while(t--) {
        test();
    }
    // cout << (clock() - f) * 1.0 / CLOCKS_PER_SEC << '\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