Submission #925165

#TimeUsernameProblemLanguageResultExecution timeMemory
925165alexddSprinkler (JOI22_sprinkler)C++17
9 / 100
1512 ms195920 KiB
#include<bits/stdc++.h> using namespace std; #define int long long int n,MOD,phi; int put(int a, int exp) { if(exp==0) return 1; if(exp%2==0) return put((a*a)%MOD,exp/2); else return (put((a*a)%MOD,exp/2)*a)%MOD; } int aint[800005]; int lazy[800005]; void build(int nod, int st, int dr) { aint[nod]=1; lazy[nod]=1; if(st==dr) return; int mij=(st+dr)/2; build(nod*2,st,mij); build(nod*2+1,mij+1,dr); } void propagate(int nod) { lazy[nod*2]=lazy[nod*2]*lazy[nod]%MOD; lazy[nod*2+1]=lazy[nod*2+1]*lazy[nod]%MOD; aint[nod*2]=aint[nod*2]*lazy[nod]%MOD; aint[nod*2+1]=aint[nod*2+1]*lazy[nod]%MOD; lazy[nod]=1; } void upd(int nod, int st, int dr, int le, int ri, int newv) { if(le>ri) return; if(le==st && dr==ri) { aint[nod]=aint[nod]*newv%MOD; lazy[nod]=lazy[nod]*newv%MOD; return; } propagate(nod); int mij=(st+dr)/2; upd(nod*2,st,mij,le,min(mij,ri),newv); upd(nod*2+1,mij+1,dr,max(le,mij+1),ri,newv); aint[nod]=aint[nod*2]*aint[nod*2+1]%MOD; } int qry(int nod, int st, int dr, int poz) { if(st==dr) return aint[nod]; propagate(nod); int mij=(st+dr)/2; if(poz<=mij) return qry(nod*2,st,mij,poz); else return qry(nod*2+1,mij+1,dr,poz); } int aib0[200005]; int qry0(int poz) { int aux=0; for(int i=poz;i>0;i-=(i&(-i))) aux+=aib0[i]; return aux; } void upd0(int poz, int newv) { for(int i=poz;i<=n;i+=(i&(-i))) aib0[i]+=newv; } int h[200005]; vector<int> con[200005]; int parent[200005]; int tole[200005][45]; int tori[200005][45]; int cntd[200005]; int cntd2[200005]; int depth[200005]; int pos[200005]; void dfs(int nod) { cntd[depth[nod]]++; for(auto adj:con[nod]) { if(adj!=parent[nod]) { depth[adj]=depth[nod]+1; parent[adj]=nod; dfs(adj); } } } void dfs2(int nod) { cntd2[depth[nod]]++; pos[nod] = cntd[depth[nod]-1] + cntd2[depth[nod]]; //cout<<nod<<" "<<pos[nod]<<" pos\n"; for(int d=0;d<=42;d++) { tole[nod][d] = n+5; tori[nod][d] = -1; } tole[nod][0] = tori[nod][0] = pos[nod]; for(auto adj:con[nod]) { if(adj!=parent[nod]) { dfs2(adj); for(int d=1;d<=42;d++) { tole[nod][d] = min(tole[nod][d], tole[adj][d-1]); tori[nod][d] = max(tori[nod][d], tori[adj][d-1]); } } } } void faupd(int le, int ri, int newv) { if(le>ri) return; if(newv!=0) { upd(1,1,n,le,ri,newv); } else { upd0(le,1); upd0(ri+1,-1); } } int calc_phi(int x) { int d=2,prod=x; while(d*d<=x) { if(x%d==0) { while(x%d==0) x/=d; prod = prod / d * (d-1); } if(d==2) d--; d+=2; } if(x>1) prod = prod / x * (x-1); return prod; } int getrez(int poz) { if(qry0(poz)>0) return 0; else return qry(1,1,n,poz); } int le[200005],ri[200005]; signed main() { ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>MOD; phi = calc_phi(MOD); int a,b; for(int i=1;i<n;i++) { cin>>a>>b; con[a].push_back(b); con[b].push_back(a); } depth[1]=1; dfs(1); for(int i=2;i<=n;i++) cntd[i]+=cntd[i-1]; dfs2(1); for(int i=1;i<=n;i++) { cin>>h[i]; } build(1,1,n); int cntq,tip,d; cin>>cntq; for(int pas=1;pas<=cntq;pas++) { cin>>tip; if(tip==1) { cin>>a>>d>>b; for(int i=max((int)1,depth[a]-d);i<=min(n,depth[a]+d);i++) { le[i]=n+5; ri[i]=-1; } int cur=a; for(int i=0;i<=d;i++) { if(cur==0) break; for(int j=max(0LL,d-i-1);j<=d-i;j++) { if(depth[cur]+j>n) break; le[depth[cur]+j] = min(le[depth[cur]+j], tole[cur][j]); ri[depth[cur]+j] = max(ri[depth[cur]+j], tori[cur][j]); } cur = parent[cur]; } for(int i=max((int)1,depth[a]-d);i<=min(n,depth[a]+d);i++) { faupd(le[i],ri[i],b); } } else { cin>>a; cout<<(h[a]*getrez(pos[a]))%MOD<<"\n"; //cout<<h[a]<<" "<<qry_brut(pos[a])<<" zzz\n"; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...