oj.uz

Submission #942866

# Submission time Handle Problem Language Result Execution time Memory
942866 2024-03-11T05:43:05 Z vjudge1 Arboras (RMI20_arboras) C++17
100 / 100
 291 ms 21232 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 4 ms 12892 KB Output is correct
2 Correct 4 ms 12892 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 291 ms 19284 KB Output is correct
2 Correct 151 ms 17868 KB Output is correct
3 Correct 180 ms 18288 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 20472 KB Output is correct
2 Correct 133 ms 21232 KB Output is correct
3 Correct 251 ms 19236 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12892 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 291 ms 19284 KB Output is correct
5 Correct 151 ms 17868 KB Output is correct
6 Correct 180 ms 18288 KB Output is correct
7 Correct 238 ms 20472 KB Output is correct
8 Correct 133 ms 21232 KB Output is correct
9 Correct 251 ms 19236 KB Output is correct
10 Correct 254 ms 20404 KB Output is correct
11 Correct 130 ms 21200 KB Output is correct
12 Correct 205 ms 19284 KB Output is correct
13 Correct 162 ms 20064 KB Output is correct
14 Correct 131 ms 20136 KB Output is correct