oj.uz

Submission #925165

# Submission time Handle Problem Language Result Execution time Memory
925165 2024-02-10T22:37:57 Z alexdd Sprinkler (JOI22_sprinkler) C++17
9 / 100
 1512 ms 195920 KB 
#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;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 25180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24920 KB Output is correct
2 Correct 514 ms 181568 KB Output is correct
3 Correct 888 ms 178512 KB Output is correct
4 Correct 703 ms 189024 KB Output is correct
5 Correct 622 ms 179904 KB Output is correct
6 Correct 606 ms 179972 KB Output is correct
7 Correct 585 ms 180600 KB Output is correct
8 Correct 518 ms 180416 KB Output is correct
9 Correct 580 ms 195920 KB Output is correct
10 Correct 1010 ms 191516 KB Output is correct
11 Correct 562 ms 181568 KB Output is correct
12 Correct 889 ms 178512 KB Output is correct
13 Correct 1073 ms 178728 KB Output is correct
14 Correct 1055 ms 179136 KB Output is correct
15 Correct 946 ms 179388 KB Output is correct
16 Correct 890 ms 178768 KB Output is correct
17 Correct 960 ms 179348 KB Output is correct
18 Correct 4 ms 24924 KB Output is correct
19 Correct 4 ms 24924 KB Output is correct
20 Correct 4 ms 24924 KB Output is correct
21 Correct 4 ms 24924 KB Output is correct
22 Correct 3 ms 24924 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24920 KB Output is correct
2 Correct 514 ms 181568 KB Output is correct
3 Correct 888 ms 178512 KB Output is correct
4 Correct 703 ms 189024 KB Output is correct
5 Correct 622 ms 179904 KB Output is correct
6 Correct 606 ms 179972 KB Output is correct
7 Correct 585 ms 180600 KB Output is correct
8 Correct 518 ms 180416 KB Output is correct
9 Correct 580 ms 195920 KB Output is correct
10 Correct 1010 ms 191516 KB Output is correct
11 Correct 562 ms 181568 KB Output is correct
12 Correct 889 ms 178512 KB Output is correct
13 Correct 1073 ms 178728 KB Output is correct
14 Correct 1055 ms 179136 KB Output is correct
15 Correct 946 ms 179388 KB Output is correct
16 Correct 890 ms 178768 KB Output is correct
17 Correct 960 ms 179348 KB Output is correct
18 Correct 4 ms 24924 KB Output is correct
19 Correct 4 ms 24924 KB Output is correct
20 Correct 4 ms 24924 KB Output is correct
21 Correct 4 ms 24924 KB Output is correct
22 Correct 3 ms 24924 KB Output is correct
23 Correct 4 ms 24924 KB Output is correct
24 Correct 540 ms 181892 KB Output is correct
25 Correct 1196 ms 178428 KB Output is correct
26 Correct 804 ms 193616 KB Output is correct
27 Correct 716 ms 180048 KB Output is correct
28 Correct 721 ms 180104 KB Output is correct
29 Correct 702 ms 180052 KB Output is correct
30 Correct 721 ms 180420 KB Output is correct
31 Correct 638 ms 191132 KB Output is correct
32 Correct 1512 ms 191968 KB Output is correct
33 Correct 607 ms 181660 KB Output is correct
34 Correct 1278 ms 178616 KB Output is correct
35 Incorrect 4 ms 24924 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Incorrect 561 ms 192948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 24924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 25180 KB Output isn't correct
2 Halted 0 ms 0 KB -