Submission #2303564

---

Source Code Expand

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

struct UnionFindTree{
    vector<int>par,sz;
    UnionFindTree(int n){
        par.resize(n);
        sz.resize(n);
        for(int i=0;i<n;i++){
            par[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        if(sz[x]<sz[y])swap(x,y);
        sz[x]+=sz[y];
        par[y]=x;
    }
    bool areSame(int x,int y){
        return find(x)==find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};

int N;
int A[222222];
int X[222222];
int dp[222222];
int ans[1000001];
signed main(){
    cin>>N;
    rep(i,N-1)cin>>A[i];

    int M;cin>>M;
    rep(i,M)cin>>X[i];

    UnionFindTree uf(1000001);
    deque<int>dp(1000001);
    rep(i,1000001)dp[i]=i;
    for(int i=N-2;i>=2;i--){
        vint v;
        rep(j,A[i]){
            v.pb(dp.front());
            dp.pop_front();
            dp.push_back(-1);
        }
        rep(j,A[i]){
            if(v[j]!=-1&&dp[A[i]-j]!=-1)uf.unite(v[j],dp[A[i]-j]);
            if(v[j]!=-1)dp[A[i]-j]=v[j];
        }
    }
    rep(i,1000001)if(dp[i]!=-1)ans[uf.find(dp[i])]=i;
    rep(i,1000001)ans[i]=ans[uf.find(i)];

    int sum=0;
    for(int i=2;i<N-1;i++)sum+=A[i];

    rep(i,M){
        int tmp;
        if(X[i]>1000000)tmp=X[i]-sum;
        else tmp=ans[X[i]];
        cout<<tmp+A[0]-A[1]<<endl;
    }
    return 0;
}

Submission Info

Judge Result