Submission #925287

#	Time	Username	Problem	Language	Result	Execution time	Memory
925287		alexdd	Sprinkler (JOI22_sprinkler)	C++17	53 / 100	4034 ms	206300 KiB

sprinkler

#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];
int care[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]];
    care[pos[nod]]=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)
    {
        if(ri-le+1 <= 15)
        {
            for(int i=le;i<=ri;i++)
                h[care[i]] = (h[care[i]]*newv)%MOD;
        }
        else
            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;
                ///j > -1 + d - (i+1)


                int lim=0;
                if(parent[cur]!=0)
                    lim=max(lim, d - i - 1);
                for(int j=lim;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;
}

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