#	User	Rating
1	tourist	4009
2	jiangly	3773
3	Radewoosh	3646
4	ecnerwala	3624
5	jqdai0815	3620
5	Benq	3620
7	orzdevinwang	3612
8	Geothermal	3569
8	cnnfls_csy	3569
10	Um_nik	3396

#	User	Contrib.
1	Um_nik	164
2	cry	160
2	maomao90	160
4	-is-this-fft-	159
5	atcoder_official	158
5	awoo	158
7	adamant	155
8	nor	154
9	maroonrk	152
10	Dominater069	149

Unexpected TLE with Segment tree

My solution to 1919F1 - Wine Factory (Easy Version) involved a few observations

Since the capacity of pipes are infinite in the easy version, each tank will transfer all remaining water to the next tank, and we can imagine the last tank dumping water outside
Now suppose we can also add water in from the left. How will the water that is dumped out from the right change?
I realized that there is a base amount that will always be dumped. As I starting adding water from the left, there will be initially no change, but after a certain cutoff, the the amount of water dumped will increase.
So a system of water tanks can be characterized by two values — base and cutoff
Also two systems of water tanks can be composed. We can derive the base and cutoff of the larger system.
Using a segment tree, we can exploit this to make updates fast
The total amount of water and wine is conserved.

The logic seems right enough, since it ran till test 10, but encountered a TLE there. However the time complexity is O(n logn) for building the segment tree and O(q logn) for answering the queries. The constant factors also don't seem very large. I made some optimizations (replaced pair <int, int> with array) and tried again without success. What is the cause of this?

My solution

#include <bits/stdc++.h>
using namespace std;
    
#define int long long
    
const int MAXN = 1e5 + 1;

// Globals
    
int n;
int a[MAXN];
int b[MAXN];
    
    
// Segment Tree
    
typedef pair <int, int> pii;

inline pii value(int i) {
    if(a[i] >= b[i]) // extra water
        return {a[i] - b[i], 0};
    else //too little water
        return {0, b[i] - a[i]};
}
    
inline pii combine(pii x, pii y) {
    auto [base_x, cutoff_x] = x;
    auto [base_y, cutoff_y] = y;
    
    int base_z, cutoff_z;
    
    base_z = base_y;
    if(base_x > cutoff_y)
        base_z += base_x - cutoff_y;
    
    cutoff_z = cutoff_x;
    if(base_x < cutoff_y)
        cutoff_z += cutoff_y - base_x;
    
    return {base_z, cutoff_z};
}
    
pii tree[4*MAXN];
    
inline void update_helper(int p, int tl, int tr, int i) {
    if(tl == p && tr == p) 
        tree[i] = value(p);
    else {
        int tm = (tl + tr) / 2;
        if(p <= tm)
            update_helper(p, tl, tm, 2*i);
        else
            update_helper(p, tm+1, tr, 2*i+1);
        tree[i] = combine(tree[2*i], tree[2*i+1]);
    }
}
    
    
inline void update(int p) {
    update_helper(p, 0, n - 1, 1);
}
    
inline void build_helper(int size, int tl, int tr, int i) {
    if(tl == tr) {
        if(tl < size)
            tree[i] = value(tl);
        else
            tree[i] = {0, 0};
    } else {
        int tm = (tl + tr) / 2;
        build_helper(size, tl, tm, 2*i);
        build_helper(size, tm + 1, tr, 2*i+1);
        tree[i] = combine(tree[2*i], tree[2*i+1]);
    }
}
    
inline void build(int size) {
    build_helper(size, 0, n - 1, 1);
}
    
    
    
void solve() {
    cin >> n;
    
    int q;
    cin >> q;
    
    for(int i = 0; i < n; i++)
        cin >> a[i];
    
    for(int i = 0; i < n; i++)
        cin >> b[i];
    
    for(int i = 0; i < n - 1; i++) {
        int x;
        cin >> x;
    }
    
    build(n);
    
    int total = 0;
    for(int i = 0; i < n; i++)
        total += a[i];
    
    while(q-- > 0) {
        int p, x, y, z;
        cin >> p >> x >> y >> z;
    
        p--;
    
        total += x - a[p];
        a[p] = x;
        b[p] = y;
        update(p);
    
        auto [base, cutoff] = tree[1];
        cout << total - base << "\n";
    }
}
        
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);    
    
    int t = 1;
    
    while(t-- > 0) 
        solve();
}

Links to my attempts

243453221 My submission
243492717 An optimized version

jmichael's blog

Unexpected TLE with Segment tree