Submission #1224851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224851		minhpk	Sprinkler (JOI22_sprinkler)	C++20	0 / 100	418 ms	93868 KiB

sprinkler

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,mod;
vector <int> z[1000005];
int h[1000005];
int sta[1000005];
int fin[100005];
int tour;
vector <int> depth[1000005];
int par[1000005];
int high[1000005];
int base[1000005];
int maxdepth=0;
int cur=1;
bool cmp(int a,int b){
     return sta[a]<sta[b];
}

int sbd(int i){
    int res=base[high[i]];
    int t=high[i];
    int pre=lower_bound(depth[t].begin(),depth[t].end(),sta[i])-depth[t].begin()+1;
    res+=pre;
    return res;
}

void dfs(int i,int j,int k){
    par[i]=j;
    tour++;
    sta[i]=tour;
    maxdepth=max(maxdepth,k);
    depth[k].push_back(sta[i]);

    for (auto p:z[i]){
         if (p==j){
            continue;
         }
         high[p]=high[i]+1;
         dfs(p,i,k+1);
    }

    fin[i]=tour;
}

int f[4000005];
int lazy[4000005];

void push(int id){
    if (lazy[id]!=1){
        lazy[id*2]*=lazy[id];
        lazy[id*2+1]*=lazy[id];

        f[id*2]*=lazy[id];
        f[id*2]*=lazy[id];
        f[id*2]%=mod;
        f[id*2+1]%=mod;

        lazy[id]=1;
    }
}

void update(int id,int l,int r,int x,int y,int val){
     if (x>r || y<l){
         return;
     }
     if (l>=x && y>=r){
         f[id]*=val;
         f[id]%=mod;
         lazy[id]=(lazy[id]*val)%mod;
         return;
     }
     int mid=(l+r)/2;
     push(id);
     update(id*2,l,mid,x,y,val);
     update(id*2+1,mid+1,r,x,y,val);
     f[id]=f[id*2]+f[id*2+1];
}
int get(int id,int l,int r,int pos){
    if (l==r){
        return f[id];
    }
    int mid=(l+r)/2;
    if (pos<=mid){
        return get(id*2,l,mid,pos);
    }else{
        return get(id*2+1,mid+1,r,pos);
    }
}

bool vis[1000005];

void query(int n,int w){
    for (int i=1;i<=min(n,maxdepth);i++){
         vis[i]=true;
         int sta1=base[i]+1;
         int fin1=base[i]+depth[i].size();
         update(1,1,a,sta1,fin1,w);
    }
}

void queryup(int n,int d,int w){
    int cnt=0;
    while (cnt<=d && n!=0){
        if (vis[high[n]]==false){
            vis[high[n]]=true;
            h[n]=(h[n]*w)%mod;
        }
        n=par[n];
        cnt++;
    }
}

void querydown(int n,int d,int w){
    int cnt=0;
    int sta1=high[n];
    while (sta1<=maxdepth && cnt<=d){
         if (!vis[sta1]){
             int pos1=lower_bound(depth[sta1].begin(),depth[sta1].end(),sta[n])-depth[sta1].begin()+1+base[sta1];
             int pos2=upper_bound(depth[sta1].begin(),depth[sta1].end(),fin[n])-depth[sta1].begin()+base[sta1];
//             if (cur==1){
//                cout << sta1<< " " << pos1 << " " << pos2 << "\n";
//             }
             update(1,1,a,pos1,pos2,w);
             vis[sta1]=true;
         }
         sta1++;
         cnt++;
    }
}

void bruh(int id,int l,int r){
     if (l==r){
         cout << f[id] << " ";
         return;
     }
     int mid=(l+r)/2;
     push(id);
     bruh(id*2,l,mid);
     bruh(id*2+1,mid+1,r);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> mod;
    for (int i=1;i<a;i++){
         int x,y;
         cin >> x >> y;
         z[x].push_back(y);
         z[y].push_back(x);
    }
    for (int i=1;i<=a;i++){
         cin >> h[i];
    }
    dfs(1,0,1);

    for (int i=1;i<=maxdepth;i++){
         base[i]=base[i-1]+depth[i-1].size();
         sort(depth[i].begin(),depth[i].end(),cmp);
         vis[i]=false;
    }
    for (int i=1;i<=a;i++){
         high[i]++;
    }
    for (int i=1;i<=4*a+5;i++){
         lazy[i]=1;
         f[i]=1;
    }
//    for (int i=1;i<=maxdepth;i++){
//         cout << base[i] << "\n";
//    }

    int q;
    cin >> q;
//    cout << "\n";
    while (q--){
         int c;
         cin >> c;
         if (c==2){
             int x;
             cin >> x;
             int pos=sbd(x);
             int pre=get(1,1,a,pos);
//             cout << "query" << "\n";
             //cout << pos << " ";
             cout << (h[x]*pre)%mod << "\n";
//             cout << "\n";
         }else{
             int x,d,w;
             cin >> x >> d >> w;
             if (high[x]-1<d){
               // cout << "ok" << '\n';
                int remain=d-(high[x]-1);
                query(remain,w);
             }
             queryup(x,d,w);
             querydown(x,d,w);
             vis[high[x]]=false;
             for (int i=1;i<=d;i++){
                 vis[high[x]+i]=false;
                 vis[min(high[x]-i,1LL)]=false;
             }
         }
//         cout << cur  << "\n";
//         bruh(1,1,a);
//         cout << "\n";
//         for (int i=1;i<=a;i++){
//             cout << h[i] << " ";
//         }
//         cur++;
//         cout << "\n";
//         cout << "\n";
    }

    return 0;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 9
• Subtask 3: 0 / 29
• Subtask 4: 0 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17