結果

問題 No.2861 Slime Party
コンテスト
ユーザー Thomas Yang
提出日時 2025-10-05 23:32:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 372 ms / 4,000 ms
コード長 5,343 bytes
コンパイル時間 2,707 ms
コンパイル使用メモリ 205,228 KB
実行使用メモリ 37,664 KB
最終ジャッジ日時 2025-10-05 23:33:17
合計ジャッジ時間 31,713 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 76
権限があれば一括ダウンロードができます

ソースコード

diff # 

// ai benchmark 

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

using int64 = long long;
using i128 = __int128_t;

struct Fenwick {
    int n;
    vector<long long> bit;
    Fenwick() {}
    Fenwick(int n): n(n), bit(n+1,0) {}
    void add(int idx, long long v){
        for(; idx<=n; idx+=idx&-idx) bit[idx]+=v;
    }
    long long sumPrefix(int idx) const{
        long long r=0;
        for(; idx>0; idx-=idx&-idx) r+=bit[idx];
        return r;
    }
    long long sumRange(int l, int r) const{
        if(r<l) return 0;
        return sumPrefix(r)-sumPrefix(l-1);
    }
};

struct SegTree {
    int n;
    vector<long long> mx, lz;
    SegTree() {}
    SegTree(int n): n(n), mx(4*n+4, LLONG_MIN/4), lz(4*n+4, 0) {}
    void build(const vector<long long>& a){ build(1,1,n,a); }
    void build(int p, int l, int r, const vector<long long>& a){
        if(l==r){ mx[p]=a[l]; return; }
        int m=(l+r)>>1;
        build(p<<1,l,m,a);
        build(p<<1|1,m+1,r,a);
        mx[p]=max(mx[p<<1],mx[p<<1|1]);
    }
    void push(int p){
        if(lz[p]!=0){
            long long v=lz[p];
            lz[p<<1]+=v; mx[p<<1]+=v;
            lz[p<<1|1]+=v; mx[p<<1|1]+=v;
            lz[p]=0;
        }
    }
    void rangeAdd(int L, int R, long long v){ if(L>R) return; rangeAdd(1,1,n,L,R,v); }
    void rangeAdd(int p, int l, int r, int L, int R, long long v){
        if(R<l || r<L) return;
        if(L<=l && r<=R){ mx[p]+=v; lz[p]+=v; return; }
        push(p);
        int m=(l+r)>>1;
        rangeAdd(p<<1,l,m,L,R,v);
        rangeAdd(p<<1|1,m+1,r,L,R,v);
        mx[p]=max(mx[p<<1],mx[p<<1|1]);
    }
    // find the greatest index <= pos with value >= thr; return 0 if none
    int find_last_ge(int pos, long long thr){ return find_last_ge(1,1,n,pos,thr); }
    int find_last_ge(int p, int l, int r, int pos, long long thr){
        if(l>pos) return 0;
        if(mx[p] < thr) return 0;
        if(l==r) return l;
        push(p);
        int m=(l+r)>>1;
        int res = 0;
        if(m<pos){
            res = find_last_ge(p<<1|1,m+1,r,pos,thr);
            if(res) return res;
            return find_last_ge(p<<1,l,m,pos,thr);
        }else{
            // entire right child is beyond pos
            return find_last_ge(p<<1,l,m,pos,thr);
        }
    }
    // find the smallest index >= pos with value >= thr; return n+1 if none
    int find_first_ge(int pos, long long thr){ return find_first_ge(1,1,n,pos,thr); }
    int find_first_ge(int p, int l, int r, int pos, long long thr){
        if(r<pos) return n+1;
        if(mx[p] < thr) return n+1;
        if(l==r) return l;
        push(p);
        int m=(l+r)>>1;
        int res = find_first_ge(p<<1,l,m,pos,thr);
        if(res!=n+1) return res;
        return find_first_ge(p<<1|1,m+1,r,pos,thr);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    long long L;
    if(!(cin>>N>>Q>>L)) return 0;
    vector<long long> 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];

    // prefix sums of X
    Fenwick fw(N);
    for(int i=1;i<=N;i++) fw.add(i, X[i]);

    // Build base arrays for segtrees:
    // V_L[i] = A[i] + P[i]
    // V_R[i] = A[i] - P[i-1]
    vector<long long> pref(N+1,0);
    for(int i=1;i<=N;i++) pref[i]=pref[i-1]+X[i];
    vector<long long> VL(N+1), VR(N+1);
    for(int i=1;i<=N;i++){
        VL[i] = A[i] + pref[i];
        VR[i] = A[i] - pref[i-1];
    }

    SegTree segL(N), segR(N);
    segL.build(VL);
    segR.build(VR);

    auto solve_gap = [&](int k)->long long{
        // l = k (last uncleared on left), r = k+1 (first uncleared on right)
        int l = k, r = k+1;
        long long Pk = fw.sumPrefix(k);
        long long TR0 = L + Pk;      // L + P[r-1] (initially r-1=k)
        long long TL0 = L - Pk;      // L - P[l]
        // Expand alternately until stable. Each expansion jumps to the current maximal run.
        int prev_l = -1, prev_r = -1;
        long long SL = 0, SR = 0;
        for(;;){
            // stop if no movement
            if(prev_l==l && prev_r==r) break;
            prev_l = l; prev_r = r;

            // Expand left with fixed TR = TR0 + SR
            long long TR = TR0 + SR;
            int blockLeft = segL.find_last_ge(l, TR); // last index <= l with V_L >= TR
            // if none, 0
            l = (blockLeft<0?0:blockLeft);
            SL = fw.sumRange(l+1, k);

            // Expand right with fixed TL = TL0 + SL
            long long TL = TL0 + SL;
            int blockRight = segR.find_first_ge(r, TL); // first index >= r with V_R >= TL
            if(blockRight == N+1) r = N+1;
            else r = blockRight;
            SR = fw.sumRange(k+1, r-1);
        }
        return L + SL + SR;
    };

    for(int qi=0; qi<Q; ++qi){
        int t; cin>>t;
        if(t==1){
            int a; long long b; cin>>a>>b;
            long long delta = b - X[a];
            if(delta!=0){
                X[a]=b;
                fw.add(a, delta);
                // Update V_L[i] += delta for i>=a
                segL.rangeAdd(a, N, delta);
                // Update V_R[i] -= delta for i>=a+1
                if(a+1<=N) segR.rangeAdd(a+1, N, -delta);
            }
        }else{
            int c; cin>>c; // start between c and c+1
            cout << solve_gap(c) << '\n';
        }
    }
    return 0;
}
0