oj.uz

Submission #942865

# Submission time Handle Problem Language Result Execution time Memory
942865 2024-03-11T05:42:40 Z bachhoangxuan Arboras (RMI20_arboras) C++17
100 / 100
 295 ms 23520 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=1e9+7;
const int maxn=100005;
const int B=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=25;
const int maxa=1000000;
const int root=3;
const int base=101;

int n,q,par[maxn],d[maxn],dep[maxn];
vector<int> edge[maxn];
int L[maxn],R[maxn],cn[maxn],T;
int nxt[maxn],total=0;

struct node{
    int mx=0,u=-1;
    node(int mx=-1,int u=-1):mx(mx),u(u){}
    bool operator<(const node &a)const{
        if(mx!=a.mx) return mx<a.mx;
        else return u<a.u;
    }
};

int lazy[4*maxn];
node tree[4*maxn];
void update(int l,int r,int id,int tl,int tr,int val){
    if(tr<l || r<tl) return;
    if(tl<=l && r<=tr){
        lazy[id]+=val;
        tree[id].mx+=val;
        return;
    }
    int mid=(l+r)>>1;
    update(l,mid,id<<1,tl,tr,val);update(mid+1,r,id<<1|1,tl,tr,val);
    tree[id]=max(tree[id<<1],tree[id<<1|1]);
    tree[id].mx+=lazy[id];
}
node query(int l,int r,int id,int tl,int tr){
    if(tr<l || r<tl || tl>tr) return node();
    if(tl<=l && r<=tr) return tree[id];
    int mid=(l+r)>>1;
    node res=max(query(l,mid,id<<1,tl,tr),query(mid+1,r,id<<1|1,tl,tr));
    res.mx+=lazy[id];
    return res;
}
void build(int l,int r,int id){
    if(l==r){
        tree[id]=node(d[cn[l]],cn[l]);
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,id<<1);build(mid+1,r,id<<1|1);
    tree[id]=max(tree[id<<1],tree[id<<1|1]);
}

node dfs(int u){
    L[u]=++T;cn[T]=u;
    d[u]+=d[par[u]];
    dep[u]=dep[par[u]]+1;
    node cc=node(d[u],u);
    for(int v:edge[u]) cc=max(cc,dfs(v));
    nxt[cc.u]=u;R[u]=T;
    return cc;
}
int getChild(int u,int x){
    int l=0,r=(int)edge[u].size()-1;
    while(l<r){
        int mid=(l+r+1)>>1;
        int v=edge[u][mid];
        if(L[v]<=L[x]) l=mid;
        else r=mid-1;
    }
    return edge[u][l];
}
node getMax(int u){
    return query(1,n,1,L[u],R[u]);
}
node getSec(int u){
    if(edge[u].empty()) return query(1,n,1,L[u],L[u]);
    node Max=getMax(u);
    int v=getChild(u,Max.u);
    return max(query(1,n,1,L[u],L[v]-1),query(1,n,1,R[v]+1,R[u]));
}

void solve(){
    cin >> n;
    for(int i=2;i<=n;i++){
        cin >> par[i];par[i]++;
        edge[par[i]].push_back(i);
    }
    for(int i=2;i<=n;i++) cin >> d[i];
    dfs(1);
    build(1,n,1);
    for(int i=1;i<=n;i++){
        //cout << i << endl;
        total+=(getMax(i).mx+getSec(i).mx-2*d[i])%mod;
        total=(total%mod+mod)%mod;
    }
    cout << total << '\n';
    cin >> q;
    for(int i=1;i<=q;i++){
        int u,val;cin >> u >> val;u++;
        node cc=getMax(u);
        //cout << '*' << cc.u << ' ' << cc.mx << '\n';
        total=(total+(dep[u]-dep[nxt[cc.u]])*val)%mod;
        cc.mx+=val;
        int v=nxt[cc.u];
        while(v>1){
            int p=par[v];
            node cur=getMax(p);
            if(cc<cur){
                node c2=getSec(p);
                if(c2<cc) total=(total+cc.mx-c2.mx)%mod;
                break;
            }
            else{
                total=(total+cur.mx-getSec(p).mx)%mod;
                int x=nxt[cur.u];
                total=(total+(cc.mx-cur.mx)%mod*(dep[v]-dep[x]))%mod;
                nxt[cur.u]=getChild(p,cur.u);
                nxt[cc.u]=x;v=x;
            }
        }
        cout << (total%mod+mod)%mod << '\n';
        update(1,n,1,L[u],R[u],val);
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12888 KB Output is correct
2 Correct 4 ms 13148 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 21312 KB Output is correct
2 Correct 180 ms 19492 KB Output is correct
3 Correct 190 ms 20468 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 22716 KB Output is correct
2 Correct 130 ms 23520 KB Output is correct
3 Correct 228 ms 21372 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12888 KB Output is correct
2 Correct 4 ms 13148 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 256 ms 21312 KB Output is correct
5 Correct 180 ms 19492 KB Output is correct
6 Correct 190 ms 20468 KB Output is correct
7 Correct 273 ms 22716 KB Output is correct
8 Correct 130 ms 23520 KB Output is correct
9 Correct 228 ms 21372 KB Output is correct
10 Correct 295 ms 22536 KB Output is correct
11 Correct 132 ms 23504 KB Output is correct
12 Correct 200 ms 21328 KB Output is correct
13 Correct 166 ms 21200 KB Output is correct
14 Correct 133 ms 21660 KB Output is correct