Submission #40752943

---

Source Code Expand

#include <bits/stdc++.h>

using i64 = long long;

constexpr int M = 1 << 17;
constexpr int inf = 1E9 + 1;

int A[M], B[M];

i64 sumA[2 * M];
int minB[2 * M];

bool cmp(int i, int j) {
    return B[i] < B[j];
}

void pull(int p, int l, int r) {
    int m = (l + r) / 2;
    sumA[p] = sumA[2 * p] + sumA[2 * p + 1];
    minB[p] = std::min({minB[2 * p], minB[2 * p + 1], m}, cmp);
}

void build(int p, int l, int r) {
    if (r - l == 1) {
        sumA[p] = A[l];
        return;
    }
    int m = (l + r) / 2;
    build(2 * p, l, m);
    build(2 * p + 1, m, r);
    pull(p, l, r);
}

void modifyA(int p, int l, int r, int x, int y) {
    if (r - l == 1) {
        sumA[p] = y;
        return;
    }
    int m = (l + r) / 2;
    if (x < m) {
        modifyA(2 * p, l, m, x, y);
    } else {
        modifyA(2 * p + 1, m, r, x, y);
    }
    pull(p, l, r);
}

void modifyB(int p, int l, int r, int x) {
    if (l >= x || r <= x) {
        return;
    }
    int m = (l + r) / 2;
    modifyB(2 * p, l, m, x);
    modifyB(2 * p + 1, m, r, x);
    pull(p, l, r);
}

i64 queryA(int p, int l, int r, int x, int y) {
    if (l >= y || r <= x) {
        return 0;
    }
    if (l >= x && r <= y) {
        return sumA[p];
    }
    int m = (l + r) / 2;
    return queryA(2 * p, l, m, x, y) + queryA(2 * p + 1, m, r, x, y);
}

int queryB(int p, int l, int r, int x, int y) {
    if (l >= y || r <= x) {
        return 0;
    }
    if (l >= x && r <= y) {
        return minB[p];
    }
    int m = (l + r) / 2;
    int res = std::min(queryB(2 * p, l, m, x, y), queryB(2 * p + 1, m, r, x, y), cmp);
    if (x < m && m < y) {
        res = std::min(res, m, cmp);
    }
    return res;
}

int findA(int p, int l, int r, int x, i64 &v) {
    if (r <= x) {
        return -1;
    }
    if (l >= x) {
        if (v >= sumA[p]) {
            v -= sumA[p];
            return -1;
        }
    }
    if (r - l == 1) {
        return r;
    }
    int m = (l + r) / 2;
    int res = findA(2 * p, l, m, x, v);
    if (res == -1) {
        res = findA(2 * p + 1, m, r, x, v);
    }
    return res;
}

int findAR(int p, int l, int r, int x, i64 &v) {
    if (l >= x) {
        return -1;
    }
    if (r <= x) {
        if (v >= sumA[p]) {
            v -= sumA[p];
            return -1;
        }
    }
    if (r - l == 1) {
        return l;
    }
    int m = (l + r) / 2;
    int res = findAR(2 * p + 1, m, r, x, v);
    if (res == -1) {
        res = findAR(2 * p, l, m, x, v);
    }
    return res;
}

int findSufB(int p, int l, int r, int x, int v) {
    if (l >= x || B[minB[p]] > v) {
        return l;
    }
    int m = (l + r) / 2;
    int res = findSufB(2 * p + 1, m, r, x, v);
    if (res == m && (x < m || B[m] > v)) {
        res = findSufB(2 * p, l, m, x, v);
    }
    return res;
}

int findPreB(int p, int l, int r, int x, int v) {
    if (r <= x || B[minB[p]] > v) {
        return r;
    }
    int m = (l + r) / 2;
    int res = findPreB(2 * p, l, m, x, v);
    if (res == m && (x > m || B[m] > v)) {
        res = findPreB(2 * p + 1, m, r, x, v);
    }
    return res;
}

int node(int l, int r) {
    int t = __builtin_ctz(r - l);
    return (1 << (17 - t)) + (l >> t);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    B[0] = inf;
    
    int N;
    std::cin >> N;
    
    for (int i = 0; i < N; i++) {
        std::cin >> A[i];
    }
    for (int i = 1; i < N; i++) {
        std::cin >> B[i];
    }
    B[N] = inf;
    
    build(1, 0, M);
    
    int Q;
    std::cin >> Q;
    
    while (Q--) {
        int T, P, V, L, R;
        std::cin >> T >> P >> V >> L >> R;
        L--;
        
        if (T == 1) {
            P--;
            A[P] = V;
            modifyA(1, 0, M, P, V);
        } else {
            B[P] = V;
            modifyB(1, 0, M, P);
        }
        
        while (R - L > 1) {
            i64 S = queryA(1, 0, M, L, R);
            i64 val = (S - 1) / 2;
            int p = findA(1, 0, M, L, val) - 1;
            
            int l1 = L, r1 = p, l2 = p + 1, r2 = R;
            i64 smid = A[p];
            int bl = inf, br = inf;
            
            while (r1 - l1 > 1 && r2 - l2 > 1) {
                int m1 = r1 - (r1 & -r1);
                int m2 = l2 + (l2 & -l2);
                if (m1 <= l1) {
                    m1 = r1 - (1 << std::__lg(r1 - l1 - 1));
                }
                if (m2 >= r2) {
                    m2 = l2 + (1 << std::__lg(r2 - l2 - 1));
                }
                int u = node(m1, r1);
                int v = node(l2, m2);
                i64 s = smid + sumA[u] + sumA[v];
                int Bl = std::min({bl, minB[u], B[r1]});
                int Br = std::min({br, minB[v], B[l2]});
                
                if (s > S / 2) {
                    if (Bl < Br) {
                        l1 = m1;
                    } else {
                        r2 = m2;
                    }
                } else {
                    if (Bl < Br) {
                        l2 = m2;
                        smid += sumA[v];
                        br = Br;
                    } else {
                        r1 = m1;
                        smid += sumA[u];
                        bl = Bl;
                    }
                }
            }
            
            int l, r;
            int vb = 0;
            
            if (r1 - l1 <= 1) {
                for (int i = l1; i <= r1; i++) {
                    i64 val = S / 2;
                    int j = findA(1, 0, M, i, val);
                    int q = B[queryB(1, 0, M, i, j)];
                    if (q > vb) {
                        l = i;
                        r = j;
                        vb = q;
                    }
                }
            } else {
                for (int j = l2; j <= r2; j++) {
                    i64 val = S / 2;
                    int i = findAR(1, 0, M, j, val);
                    int q = B[queryB(1, 0, M, i, j)];
                    if (q > vb) {
                        l = i;
                        r = j;
                        vb = q;
                    }
                }
            }
            
            L = std::max(L, findSufB(1, 0, M, l, vb));
            R = std::min(R, findPreB(1, 0, M, r, vb));
            
            if (R - L == 1) {
                break;
            }
            
            int m = queryB(1, 0, M, L, R);
            if (queryA(1, 0, M, L, m) >= queryA(1, 0, M, m, R)) {
                R = m;
            } else {
                L = m;
            }
        }
        
        std::cout << R << "\n";
    }
    
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:262:37: warning: ‘r’ may be used uninitialized in this function [-Wmaybe-uninitialized]
  262 |             R = std::min(R, findPreB(1, 0, M, r, vb));
      |                             ~~~~~~~~^~~~~~~~~~~~~~~~
./Main.cpp:261:37: warning: ‘l’ may be used uninitialized in this function [-Wmaybe-uninitialized]
  261 |             L = std::max(L, findSufB(1, 0, M, l, vb));
      |                             ~~~~~~~~^~~~~~~~~~~~~~~~

Judge Result