結果

問題 No.3164 [Chery 7th Tune B] La vie en rose
コンテスト
ユーザー Today03
提出日時 2025-05-30 21:26:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 793 ms / 2,000 ms
コード長 3,651 bytes
コンパイル時間 3,540 ms
コンパイル使用メモリ 282,628 KB
実行使用メモリ 10,240 KB
最終ジャッジ日時 2025-05-30 21:27:19
合計ジャッジ時間 25,268 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

#define ALL(x) (x).begin(),(x).end()
#define IO ios::sync_with_stdio(false),cin.tie(nullptr);
#define REP(i, n) for(ll i=0; i<(ll)(n); i++)
#define FOR(i, a, b) for(ll i=(ll)(a); i<(b); i++)
#define ROF(i, a, b) for(ll i=(ll)(b)-1; i>=(a); i--)

template<typename T> int LB(const vector<T>& v, T x) { return lower_bound(ALL(v),x)-(v).begin(); }
template<typename T> int UQ(T& v) { sort(ALL(v)); v.erase(unique(ALL(v)),v.end()); return v.size(); }
template<typename T> bool chmax(T &a, T b) { return a<b ? a=b, true : false; }
template<typename T> bool chmin(T &a, T b) { return a>b ? a=b, true : false; }
template<typename T> using rpriority_queue=priority_queue<T,vector<T>,greater<T>>;
using ll=long long; const int INF=1e9+10; const ll INFL=4e18; using ld=long double;
using ull=unsigned long long; using lll=__int128_t; using VST=vector<string>;
using VI=vector<int>; using VVI=vector<VI>; using VL=vector<ll>; using VVL=vector<VL>;
using PL=pair<ll,ll>; using VP=vector<PL>; using WG=vector<vector<pair<int,ll>>>;

#ifdef LOCAL
#include "./debug.hpp"
#else
#define debug(...)
#define print_line
#endif



struct DsuBaseSemigroup {
    using Type=ll;
    static Type op(Type a, Type b) { return a+b; }
};

/// @brief 値をマージする DSU
/// @tparam Semigroup 半群
template<typename Semigroup=DsuBaseSemigroup>
struct DsuMerging {
    using Type=typename Semigroup::Type;
    DsuMerging()=default;

    /// @brief コンストラクタ
    DsuMerging(int n, const vector<Type>& v) {
        par=VI(n); iota(ALL(par),0);
        sz=VI(n,1);
        dat=v;
        forest_count=n;
    }

    /// @brief 頂点 x を含む連結成分の代表元を返す
    /// @note O(α(N))
    int find(int x) {
        if(par[x]==x) return x;
        return par[x]=find(par[x]);
    }

    /// @brief 頂点 x と y を連結し、true を返す
    /// @brief 既に連結されている場合は false を返す
    /// @note O(α(N))
    bool merge(int x, int y) {
        x=find(x); y=find(y);
        if(x==y) return false;
        if(sz[x]>=sz[y]) {
            par[y]=x; sz[x]+=sz[y];
            dat[x]=Semigroup::op(dat[x],dat[y]);
        } else {
            par[x]=y; sz[y]+=sz[x];
            dat[y]=Semigroup::op(dat[x],dat[y]);
        }
        forest_count--;
        return true;
    }

    /// @brief 頂点 x を含む連結成分の半群積を返す
    const Type& get(int x) { return dat[find(x)]; }

    /// @brief 頂点 x を含む連結成分のサイズを返す
    int size(int x) const { return sz[find(x)]; }

    /// @brief 頂点 x と y が同じ連結成分に属するか否かを返す
    bool same(int x, int y) const {return find(x)==find(y);}

    /// @brief 連結成分の個数を返す
    int count() const { return forest_count; }

    /// @brief 各頂点を連結成分に分解する
    VVI groups() const {
        int n=par.size();
        VVI ret(n);
        REP(i,n) ret[find(i)].push_back(i);
        ret.erase(remove_if(ALL(ret),[&](const VI& v) { return v.empty(); }),ret.end());
        return ret;
    }

private:
    VI par,sz;
    vector<Type> dat;
    int forest_count;
};

//----------------------------------------------------------

int main() {
    ll N; cin>>N;
    VL A(N); REP(i,N) cin>>A[i];

    DsuMerging<> dsu(N,A);

    REP(i,N-1) {
        if(A[i]>0&&A[i+1]>0) dsu.merge(i,i+1);
    }

    int Q; cin>>Q;
    while(Q--) {
        ll x,b; cin>>x>>b; x--;

        ll ans=dsu.get(x);

        if(A[x]==0&&x>0) ans+=dsu.get(x-1);
        if(A[x]==0&&x+1<N) ans+=dsu.get(x+1);
        ans+=b-A[x];

        cout<<ans<<'\n';
    }
}
0