oj.uz

Submission #925166

# Submission time Handle Problem Language Result Execution time Memory
925166 2024-02-10T22:38:19 Z alexdd Sprinkler (JOI22_sprinkler) C++17
38 / 100
 1487 ms 195776 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-2);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 3 ms 24920 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 24924 KB Output is correct
2 Correct 519 ms 181724 KB Output is correct
3 Correct 949 ms 178620 KB Output is correct
4 Correct 768 ms 189004 KB Output is correct
5 Correct 637 ms 180284 KB Output is correct
6 Correct 657 ms 180220 KB Output is correct
7 Correct 590 ms 180304 KB Output is correct
8 Correct 580 ms 180452 KB Output is correct
9 Correct 586 ms 195776 KB Output is correct
10 Correct 1008 ms 191512 KB Output is correct
11 Correct 518 ms 181852 KB Output is correct
12 Correct 905 ms 178772 KB Output is correct
13 Correct 1069 ms 178880 KB Output is correct
14 Correct 1072 ms 179060 KB Output is correct
15 Correct 968 ms 178952 KB Output is correct
16 Correct 882 ms 178772 KB Output is correct
17 Correct 964 ms 179536 KB Output is correct
18 Correct 4 ms 24920 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 5 ms 24924 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24924 KB Output is correct
2 Correct 519 ms 181724 KB Output is correct
3 Correct 949 ms 178620 KB Output is correct
4 Correct 768 ms 189004 KB Output is correct
5 Correct 637 ms 180284 KB Output is correct
6 Correct 657 ms 180220 KB Output is correct
7 Correct 590 ms 180304 KB Output is correct
8 Correct 580 ms 180452 KB Output is correct
9 Correct 586 ms 195776 KB Output is correct
10 Correct 1008 ms 191512 KB Output is correct
11 Correct 518 ms 181852 KB Output is correct
12 Correct 905 ms 178772 KB Output is correct
13 Correct 1069 ms 178880 KB Output is correct
14 Correct 1072 ms 179060 KB Output is correct
15 Correct 968 ms 178952 KB Output is correct
16 Correct 882 ms 178772 KB Output is correct
17 Correct 964 ms 179536 KB Output is correct
18 Correct 4 ms 24920 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 5 ms 24924 KB Output is correct
23 Correct 4 ms 24924 KB Output is correct
24 Correct 535 ms 181936 KB Output is correct
25 Correct 1144 ms 178308 KB Output is correct
26 Correct 821 ms 193900 KB Output is correct
27 Correct 715 ms 180332 KB Output is correct
28 Correct 704 ms 180012 KB Output is correct
29 Correct 710 ms 180148 KB Output is correct
30 Correct 684 ms 180512 KB Output is correct
31 Correct 700 ms 191096 KB Output is correct
32 Correct 1487 ms 191820 KB Output is correct
33 Correct 616 ms 181844 KB Output is correct
34 Correct 1380 ms 178716 KB Output is correct
35 Correct 4 ms 24924 KB Output is correct
36 Correct 5 ms 24924 KB Output is correct
37 Correct 4 ms 25068 KB Output is correct
38 Correct 4 ms 24924 KB Output is correct
39 Correct 4 ms 24924 KB Output is correct
40 Correct 4 ms 24924 KB Output is correct
41 Correct 4 ms 24924 KB Output is correct
42 Correct 4 ms 24920 KB Output is correct
43 Correct 4 ms 24924 KB Output is correct
44 Correct 4 ms 24924 KB Output is correct
45 Correct 4 ms 24924 KB Output is correct
46 Correct 4 ms 24920 KB Output is correct
47 Correct 4 ms 24924 KB Output is correct
48 Correct 4 ms 24924 KB Output is correct
49 Correct 4 ms 24924 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Incorrect 714 ms 192848 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 3 ms 24920 KB Output isn't correct
2 Halted 0 ms 0 KB -