oj.uz

Submission #925167

# Submission time Handle Problem Language Result Execution time Memory
925167 2024-02-10T22:38:41 Z alexdd Sprinkler (JOI22_sprinkler) C++17
53 / 100
 4000 ms 200204 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;
                ///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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Correct 4 ms 24924 KB Output is correct
3 Correct 4 ms 24924 KB Output is correct
4 Correct 11 ms 25168 KB Output is correct
5 Correct 10 ms 24920 KB Output is correct
6 Correct 8 ms 25112 KB Output is correct
7 Correct 8 ms 24924 KB Output is correct
8 Correct 5 ms 24920 KB Output is correct
9 Correct 4 ms 24920 KB Output is correct
10 Correct 4 ms 25084 KB Output is correct
11 Correct 4 ms 24924 KB Output is correct
12 Correct 5 ms 24924 KB Output is correct
13 Correct 5 ms 24924 KB Output is correct
14 Correct 4 ms 24924 KB Output is correct
15 Correct 4 ms 24920 KB Output is correct
16 Correct 4 ms 24920 KB Output is correct
17 Correct 4 ms 24920 KB Output is correct
18 Correct 4 ms 25060 KB Output is correct
19 Correct 4 ms 25068 KB Output is correct
20 Correct 4 ms 24924 KB Output is correct
21 Correct 4 ms 24924 KB Output is correct
22 Correct 4 ms 24924 KB Output is correct
23 Correct 3 ms 24924 KB Output is correct
24 Correct 5 ms 24924 KB Output is correct
25 Correct 4 ms 24924 KB Output is correct
26 Correct 4 ms 24924 KB Output is correct
27 Correct 4 ms 24920 KB Output is correct
28 Correct 4 ms 24924 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24920 KB Output is correct
2 Correct 540 ms 181516 KB Output is correct
3 Correct 928 ms 178448 KB Output is correct
4 Correct 712 ms 189080 KB Output is correct
5 Correct 623 ms 180080 KB Output is correct
6 Correct 705 ms 179912 KB Output is correct
7 Correct 713 ms 180348 KB Output is correct
8 Correct 534 ms 180408 KB Output is correct
9 Correct 601 ms 195912 KB Output is correct
10 Correct 1033 ms 191580 KB Output is correct
11 Correct 485 ms 181660 KB Output is correct
12 Correct 903 ms 178512 KB Output is correct
13 Correct 1060 ms 178656 KB Output is correct
14 Correct 1087 ms 178900 KB Output is correct
15 Correct 935 ms 178992 KB Output is correct
16 Correct 888 ms 178800 KB Output is correct
17 Correct 986 ms 179240 KB Output is correct
18 Correct 4 ms 24924 KB Output is correct
19 Correct 4 ms 25060 KB Output is correct
20 Correct 5 ms 24924 KB Output is correct
21 Correct 4 ms 24924 KB Output is correct
22 Correct 4 ms 24924 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24920 KB Output is correct
2 Correct 540 ms 181516 KB Output is correct
3 Correct 928 ms 178448 KB Output is correct
4 Correct 712 ms 189080 KB Output is correct
5 Correct 623 ms 180080 KB Output is correct
6 Correct 705 ms 179912 KB Output is correct
7 Correct 713 ms 180348 KB Output is correct
8 Correct 534 ms 180408 KB Output is correct
9 Correct 601 ms 195912 KB Output is correct
10 Correct 1033 ms 191580 KB Output is correct
11 Correct 485 ms 181660 KB Output is correct
12 Correct 903 ms 178512 KB Output is correct
13 Correct 1060 ms 178656 KB Output is correct
14 Correct 1087 ms 178900 KB Output is correct
15 Correct 935 ms 178992 KB Output is correct
16 Correct 888 ms 178800 KB Output is correct
17 Correct 986 ms 179240 KB Output is correct
18 Correct 4 ms 24924 KB Output is correct
19 Correct 4 ms 25060 KB Output is correct
20 Correct 5 ms 24924 KB Output is correct
21 Correct 4 ms 24924 KB Output is correct
22 Correct 4 ms 24924 KB Output is correct
23 Correct 3 ms 24924 KB Output is correct
24 Correct 501 ms 181660 KB Output is correct
25 Correct 1082 ms 178788 KB Output is correct
26 Correct 824 ms 193472 KB Output is correct
27 Correct 702 ms 180092 KB Output is correct
28 Correct 659 ms 180052 KB Output is correct
29 Correct 664 ms 180204 KB Output is correct
30 Correct 646 ms 180568 KB Output is correct
31 Correct 625 ms 191508 KB Output is correct
32 Correct 1381 ms 191788 KB Output is correct
33 Correct 544 ms 181520 KB Output is correct
34 Correct 1234 ms 178408 KB Output is correct
35 Correct 3 ms 24924 KB Output is correct
36 Correct 4 ms 24924 KB Output is correct
37 Correct 4 ms 24924 KB Output is correct
38 Correct 4 ms 24924 KB Output is correct
39 Correct 4 ms 24924 KB Output is correct
40 Correct 3 ms 24924 KB Output is correct
41 Correct 4 ms 24924 KB Output is correct
42 Correct 4 ms 24924 KB Output is correct
43 Correct 4 ms 25076 KB Output is correct
44 Correct 4 ms 24920 KB Output is correct
45 Correct 4 ms 24924 KB Output is correct
46 Correct 4 ms 24924 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
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Correct 571 ms 192852 KB Output is correct
3 Correct 1809 ms 188768 KB Output is correct
4 Correct 814 ms 198116 KB Output is correct
5 Correct 735 ms 187172 KB Output is correct
6 Correct 543 ms 187216 KB Output is correct
7 Correct 558 ms 187432 KB Output is correct
8 Correct 316 ms 187700 KB Output is correct
9 Correct 591 ms 196440 KB Output is correct
10 Correct 1801 ms 200204 KB Output is correct
11 Correct 516 ms 186696 KB Output is correct
12 Correct 1680 ms 187728 KB Output is correct
13 Correct 1284 ms 188404 KB Output is correct
14 Correct 1209 ms 189344 KB Output is correct
15 Correct 3 ms 24920 KB Output is correct
16 Correct 4 ms 25088 KB Output is correct
17 Correct 4 ms 24924 KB Output is correct
18 Correct 4 ms 24924 KB Output is correct
19 Correct 4 ms 24920 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24924 KB Output is correct
2 Correct 2219 ms 190508 KB Output is correct
3 Execution timed out 4051 ms 185188 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Correct 4 ms 24924 KB Output is correct
3 Correct 4 ms 24924 KB Output is correct
4 Correct 11 ms 25168 KB Output is correct
5 Correct 10 ms 24920 KB Output is correct
6 Correct 8 ms 25112 KB Output is correct
7 Correct 8 ms 24924 KB Output is correct
8 Correct 5 ms 24920 KB Output is correct
9 Correct 4 ms 24920 KB Output is correct
10 Correct 4 ms 25084 KB Output is correct
11 Correct 4 ms 24924 KB Output is correct
12 Correct 5 ms 24924 KB Output is correct
13 Correct 5 ms 24924 KB Output is correct
14 Correct 4 ms 24924 KB Output is correct
15 Correct 4 ms 24920 KB Output is correct
16 Correct 4 ms 24920 KB Output is correct
17 Correct 4 ms 24920 KB Output is correct
18 Correct 4 ms 25060 KB Output is correct
19 Correct 4 ms 25068 KB Output is correct
20 Correct 4 ms 24924 KB Output is correct
21 Correct 4 ms 24924 KB Output is correct
22 Correct 4 ms 24924 KB Output is correct
23 Correct 3 ms 24924 KB Output is correct
24 Correct 5 ms 24924 KB Output is correct
25 Correct 4 ms 24924 KB Output is correct
26 Correct 4 ms 24924 KB Output is correct
27 Correct 4 ms 24920 KB Output is correct
28 Correct 4 ms 24924 KB Output is correct
29 Correct 4 ms 24920 KB Output is correct
30 Correct 540 ms 181516 KB Output is correct
31 Correct 928 ms 178448 KB Output is correct
32 Correct 712 ms 189080 KB Output is correct
33 Correct 623 ms 180080 KB Output is correct
34 Correct 705 ms 179912 KB Output is correct
35 Correct 713 ms 180348 KB Output is correct
36 Correct 534 ms 180408 KB Output is correct
37 Correct 601 ms 195912 KB Output is correct
38 Correct 1033 ms 191580 KB Output is correct
39 Correct 485 ms 181660 KB Output is correct
40 Correct 903 ms 178512 KB Output is correct
41 Correct 1060 ms 178656 KB Output is correct
42 Correct 1087 ms 178900 KB Output is correct
43 Correct 935 ms 178992 KB Output is correct
44 Correct 888 ms 178800 KB Output is correct
45 Correct 986 ms 179240 KB Output is correct
46 Correct 4 ms 24924 KB Output is correct
47 Correct 4 ms 25060 KB Output is correct
48 Correct 5 ms 24924 KB Output is correct
49 Correct 4 ms 24924 KB Output is correct
50 Correct 4 ms 24924 KB Output is correct
51 Correct 3 ms 24924 KB Output is correct
52 Correct 501 ms 181660 KB Output is correct
53 Correct 1082 ms 178788 KB Output is correct
54 Correct 824 ms 193472 KB Output is correct
55 Correct 702 ms 180092 KB Output is correct
56 Correct 659 ms 180052 KB Output is correct
57 Correct 664 ms 180204 KB Output is correct
58 Correct 646 ms 180568 KB Output is correct
59 Correct 625 ms 191508 KB Output is correct
60 Correct 1381 ms 191788 KB Output is correct
61 Correct 544 ms 181520 KB Output is correct
62 Correct 1234 ms 178408 KB Output is correct
63 Correct 3 ms 24924 KB Output is correct
64 Correct 4 ms 24924 KB Output is correct
65 Correct 4 ms 24924 KB Output is correct
66 Correct 4 ms 24924 KB Output is correct
67 Correct 4 ms 24924 KB Output is correct
68 Correct 3 ms 24924 KB Output is correct
69 Correct 4 ms 24924 KB Output is correct
70 Correct 4 ms 24924 KB Output is correct
71 Correct 4 ms 25076 KB Output is correct
72 Correct 4 ms 24920 KB Output is correct
73 Correct 4 ms 24924 KB Output is correct
74 Correct 4 ms 24924 KB Output is correct
75 Correct 4 ms 24924 KB Output is correct
76 Correct 4 ms 24924 KB Output is correct
77 Correct 4 ms 24924 KB Output is correct
78 Correct 4 ms 24924 KB Output is correct
79 Correct 571 ms 192852 KB Output is correct
80 Correct 1809 ms 188768 KB Output is correct
81 Correct 814 ms 198116 KB Output is correct
82 Correct 735 ms 187172 KB Output is correct
83 Correct 543 ms 187216 KB Output is correct
84 Correct 558 ms 187432 KB Output is correct
85 Correct 316 ms 187700 KB Output is correct
86 Correct 591 ms 196440 KB Output is correct
87 Correct 1801 ms 200204 KB Output is correct
88 Correct 516 ms 186696 KB Output is correct
89 Correct 1680 ms 187728 KB Output is correct
90 Correct 1284 ms 188404 KB Output is correct
91 Correct 1209 ms 189344 KB Output is correct
92 Correct 3 ms 24920 KB Output is correct
93 Correct 4 ms 25088 KB Output is correct
94 Correct 4 ms 24924 KB Output is correct
95 Correct 4 ms 24924 KB Output is correct
96 Correct 4 ms 24920 KB Output is correct
97 Correct 3 ms 24924 KB Output is correct
98 Correct 2219 ms 190508 KB Output is correct
99 Execution timed out 4051 ms 185188 KB Time limit exceeded
100 Halted 0 ms 0 KB -