結果

問題 No.2861 Slime Party
ユーザー EM 13
提出日時 2025-09-29 09:18:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,251 bytes
コンパイル時間 6,395 ms
コンパイル使用メモリ 201,400 KB
実行使用メモリ 22,400 KB
最終ジャッジ日時 2025-09-29 09:19:17
合計ジャッジ時間 22,207 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 11 OLE * 1 -- * 64
権限があれば一括ダウンロードができます

ソースコード

diff # 

//ai slop that does not work 

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

using ll = long long;

// Fenwick (BIT) for point updates, prefix sums
struct Fenwick {
    int n;
    vector<ll> bit;
    Fenwick() {}
    Fenwick(int n): n(n), bit(n+1, 0) {}
    void add(int idx, ll delta) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += delta;
    }
    ll sumPrefix(int idx) const {
        ll res = 0;
        for (; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }
    ll sumRange(int l, int r) const {
        if (l > r) return 0;
        return sumPrefix(r) - sumPrefix(l-1);
    }
};

// Segment tree that stores range maximums of A,
// and supports "first index in [ql,qr] with A[i] >= val"
// and "last index in [ql,qr] with A[i] >= val".
struct SegTreeMax {
    int n;
    vector<ll> st; // max on interval

    SegTreeMax() {}
    SegTreeMax(const vector<ll>& A) { build(A); }

    void build(const vector<ll>& A) {
        n = (int)A.size() - 1; // A is 1-indexed
        st.assign(4*n+4, LLONG_MIN);
        buildRec(1, 1, n, A);
    }

    void buildRec(int p, int l, int r, const vector<ll>& A) {
        if (l == r) {
            st[p] = A[l];
            return;
        }
        int m = (l + r) >> 1;
        buildRec(p<<1, l, m, A);
        buildRec(p<<1|1, m+1, r, A);
        st[p] = max(st[p<<1], st[p<<1|1]);
    }

    // Find first i in [ql,qr] with A[i] >= val. Return n+1 if none.
    int first_ge(int ql, int qr, ll val) const {
        if (ql > qr) return n+1;
        return firstRec(1, 1, n, ql, qr, val);
    }
    int firstRec(int p, int l, int r, int ql, int qr, ll val) const {
        if (qr < l || r < ql || st[p] < val) return n+1; // none here
        if (l == r) return l;
        int m = (l + r) >> 1;
        int left = firstRec(p<<1, l, m, ql, qr, val);
        if (left != n+1) return left;
        return firstRec(p<<1|1, m+1, r, ql, qr, val);
    }

    // Find last i in [ql,qr] with A[i] >= val. Return 0 if none.
    int last_ge(int ql, int qr, ll val) const {
        if (ql > qr) return 0;
        return lastRec(1, 1, n, ql, qr, val);
    }
    int lastRec(int p, int l, int r, int ql, int qr, ll val) const {
        if (qr < l || r < ql || st[p] < val) return 0; // none here
        if (l == r) return l;
        int m = (l + r) >> 1;
        int right = lastRec(p<<1|1, m+1, r, ql, qr, val);
        if (right != 0) return right;
        return lastRec(p<<1, l, m, ql, qr, val);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    ll L;
    if (!(cin >> N >> L)) {
        return 0;
    }

    vector<ll> A(N+1), X(N+1);
    for (int i = 1; i <= N; ++i) cin >> A[i];
    for (int i = 1; i <= N; ++i) cin >> X[i];

    int Q;
    cin >> Q;

    // Data structures
    SegTreeMax segA(A);     // static in A (A_i are all distinct and never change)
    Fenwick bitX(N);        // dynamic in X
    for (int i = 1; i <= N; ++i) bitX.add(i, X[i]);

    auto solve_for_k = [&](int c) -> ll {
        // Start between c and c+1, current level t = L
        ll t = L;
        // Iterate to least fixed point t = L + sum_X( component of {i | A[i] < t} that touches gap )
        while (true) {
            // nearest blockers (A[i] >= t) around the gap
            int left_blocker  = segA.last_ge(1, c, t);        // 0 if none
            int right_blocker = segA.first_ge(c+1, N, t);     // N+1 if none

            int L2 = left_blocker + 1;
            int R2 = right_blocker - 1;

            ll gain = (L2 <= R2) ? bitX.sumRange(L2, R2) : 0LL;
            ll t2 = L + gain;
            if (t2 == t) return t;
            // For safety (shouldn't happen if X_i >= 0): if t2 < t, still stop
            if (t2 < t) return t; 
            t = t2;
        }
    };

    for (int qi = 0; qi < Q; ++qi) {
        int type;
        cin >> type;
        if (type == 1) {
            int a; ll b;
            cin >> a >> b;
            ll delta = b - X[a];
            X[a] = b;
            bitX.add(a, delta);
        } else if (type == 2) {
            int c;
            cin >> c;
            cout << solve_for_k(c) << '\n';
        } else {
            // unknown query type; consume line if needed
        }
    }

    return 0;
}
0