oj.uz

Submission #925287

# Submission time Handle Problem Language Result Execution time Memory
925287 2024-02-11T10:54:26 Z alexdd Sprinkler (JOI22_sprinkler) C++17
53 / 100
 4000 ms 206300 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];
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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22872 KB Output is correct
2 Correct 4 ms 22876 KB Output is correct
3 Correct 4 ms 25008 KB Output is correct
4 Correct 4 ms 23132 KB Output is correct
5 Correct 5 ms 23016 KB Output is correct
6 Correct 7 ms 23132 KB Output is correct
7 Correct 6 ms 23132 KB Output is correct
8 Correct 4 ms 23132 KB Output is correct
9 Correct 3 ms 22872 KB Output is correct
10 Correct 3 ms 22876 KB Output is correct
11 Correct 4 ms 22876 KB Output is correct
12 Correct 4 ms 22872 KB Output is correct
13 Correct 3 ms 22876 KB Output is correct
14 Correct 3 ms 22876 KB Output is correct
15 Correct 4 ms 22876 KB Output is correct
16 Correct 4 ms 22876 KB Output is correct
17 Correct 3 ms 22876 KB Output is correct
18 Correct 4 ms 22968 KB Output is correct
19 Correct 3 ms 22876 KB Output is correct
20 Correct 4 ms 22968 KB Output is correct
21 Correct 3 ms 22876 KB Output is correct
22 Correct 4 ms 24924 KB Output is correct
23 Correct 4 ms 24924 KB Output is correct
24 Correct 4 ms 22876 KB Output is correct
25 Correct 3 ms 22876 KB Output is correct
26 Correct 3 ms 22876 KB Output is correct
27 Correct 3 ms 22876 KB Output is correct
28 Correct 3 ms 22876 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22876 KB Output is correct
2 Correct 497 ms 191816 KB Output is correct
3 Correct 413 ms 192592 KB Output is correct
4 Correct 548 ms 201044 KB Output is correct
5 Correct 493 ms 192064 KB Output is correct
6 Correct 483 ms 191796 KB Output is correct
7 Correct 494 ms 192340 KB Output is correct
8 Correct 373 ms 192700 KB Output is correct
9 Correct 511 ms 206300 KB Output is correct
10 Correct 499 ms 205136 KB Output is correct
11 Correct 452 ms 191796 KB Output is correct
12 Correct 460 ms 192288 KB Output is correct
13 Correct 690 ms 192592 KB Output is correct
14 Correct 681 ms 192940 KB Output is correct
15 Correct 598 ms 192116 KB Output is correct
16 Correct 606 ms 192784 KB Output is correct
17 Correct 615 ms 193212 KB Output is correct
18 Correct 4 ms 22872 KB Output is correct
19 Correct 4 ms 22876 KB Output is correct
20 Correct 4 ms 22888 KB Output is correct
21 Correct 4 ms 22872 KB Output is correct
22 Correct 4 ms 22876 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22876 KB Output is correct
2 Correct 497 ms 191816 KB Output is correct
3 Correct 413 ms 192592 KB Output is correct
4 Correct 548 ms 201044 KB Output is correct
5 Correct 493 ms 192064 KB Output is correct
6 Correct 483 ms 191796 KB Output is correct
7 Correct 494 ms 192340 KB Output is correct
8 Correct 373 ms 192700 KB Output is correct
9 Correct 511 ms 206300 KB Output is correct
10 Correct 499 ms 205136 KB Output is correct
11 Correct 452 ms 191796 KB Output is correct
12 Correct 460 ms 192288 KB Output is correct
13 Correct 690 ms 192592 KB Output is correct
14 Correct 681 ms 192940 KB Output is correct
15 Correct 598 ms 192116 KB Output is correct
16 Correct 606 ms 192784 KB Output is correct
17 Correct 615 ms 193212 KB Output is correct
18 Correct 4 ms 22872 KB Output is correct
19 Correct 4 ms 22876 KB Output is correct
20 Correct 4 ms 22888 KB Output is correct
21 Correct 4 ms 22872 KB Output is correct
22 Correct 4 ms 22876 KB Output is correct
23 Correct 4 ms 25056 KB Output is correct
24 Correct 498 ms 191876 KB Output is correct
25 Correct 468 ms 192412 KB Output is correct
26 Correct 566 ms 205724 KB Output is correct
27 Correct 513 ms 192080 KB Output is correct
28 Correct 462 ms 192508 KB Output is correct
29 Correct 470 ms 191972 KB Output is correct
30 Correct 472 ms 192700 KB Output is correct
31 Correct 503 ms 201640 KB Output is correct
32 Correct 569 ms 205616 KB Output is correct
33 Correct 463 ms 191828 KB Output is correct
34 Correct 473 ms 192596 KB Output is correct
35 Correct 4 ms 22872 KB Output is correct
36 Correct 4 ms 22876 KB Output is correct
37 Correct 3 ms 22876 KB Output is correct
38 Correct 3 ms 23076 KB Output is correct
39 Correct 3 ms 22876 KB Output is correct
40 Correct 4 ms 22872 KB Output is correct
41 Correct 3 ms 22872 KB Output is correct
42 Correct 4 ms 22876 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 22876 KB Output is correct
46 Correct 3 ms 22876 KB Output is correct
47 Correct 4 ms 22876 KB Output is correct
48 Correct 3 ms 22876 KB Output is correct
49 Correct 4 ms 22872 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 544 ms 203008 KB Output is correct
3 Correct 1994 ms 200348 KB Output is correct
4 Correct 884 ms 200180 KB Output is correct
5 Correct 820 ms 189136 KB Output is correct
6 Correct 583 ms 189360 KB Output is correct
7 Correct 534 ms 189668 KB Output is correct
8 Correct 332 ms 189572 KB Output is correct
9 Correct 541 ms 198644 KB Output is correct
10 Correct 1853 ms 202236 KB Output is correct
11 Correct 515 ms 189008 KB Output is correct
12 Correct 1691 ms 189680 KB Output is correct
13 Correct 1219 ms 190708 KB Output is correct
14 Correct 1209 ms 191664 KB Output is correct
15 Correct 4 ms 22872 KB Output is correct
16 Correct 4 ms 22972 KB Output is correct
17 Correct 3 ms 22876 KB Output is correct
18 Correct 4 ms 24924 KB Output is correct
19 Correct 4 ms 24924 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23008 KB Output is correct
2 Correct 696 ms 200628 KB Output is correct
3 Correct 1702 ms 196928 KB Output is correct
4 Correct 835 ms 198892 KB Output is correct
5 Correct 1718 ms 190868 KB Output is correct
6 Correct 3532 ms 191140 KB Output is correct
7 Correct 3059 ms 191000 KB Output is correct
8 Correct 565 ms 190940 KB Output is correct
9 Correct 687 ms 204628 KB Output is correct
10 Correct 1663 ms 203452 KB Output is correct
11 Correct 1161 ms 191448 KB Output is correct
12 Execution timed out 4034 ms 188012 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22872 KB Output is correct
2 Correct 4 ms 22876 KB Output is correct
3 Correct 4 ms 25008 KB Output is correct
4 Correct 4 ms 23132 KB Output is correct
5 Correct 5 ms 23016 KB Output is correct
6 Correct 7 ms 23132 KB Output is correct
7 Correct 6 ms 23132 KB Output is correct
8 Correct 4 ms 23132 KB Output is correct
9 Correct 3 ms 22872 KB Output is correct
10 Correct 3 ms 22876 KB Output is correct
11 Correct 4 ms 22876 KB Output is correct
12 Correct 4 ms 22872 KB Output is correct
13 Correct 3 ms 22876 KB Output is correct
14 Correct 3 ms 22876 KB Output is correct
15 Correct 4 ms 22876 KB Output is correct
16 Correct 4 ms 22876 KB Output is correct
17 Correct 3 ms 22876 KB Output is correct
18 Correct 4 ms 22968 KB Output is correct
19 Correct 3 ms 22876 KB Output is correct
20 Correct 4 ms 22968 KB Output is correct
21 Correct 3 ms 22876 KB Output is correct
22 Correct 4 ms 24924 KB Output is correct
23 Correct 4 ms 24924 KB Output is correct
24 Correct 4 ms 22876 KB Output is correct
25 Correct 3 ms 22876 KB Output is correct
26 Correct 3 ms 22876 KB Output is correct
27 Correct 3 ms 22876 KB Output is correct
28 Correct 3 ms 22876 KB Output is correct
29 Correct 3 ms 22876 KB Output is correct
30 Correct 497 ms 191816 KB Output is correct
31 Correct 413 ms 192592 KB Output is correct
32 Correct 548 ms 201044 KB Output is correct
33 Correct 493 ms 192064 KB Output is correct
34 Correct 483 ms 191796 KB Output is correct
35 Correct 494 ms 192340 KB Output is correct
36 Correct 373 ms 192700 KB Output is correct
37 Correct 511 ms 206300 KB Output is correct
38 Correct 499 ms 205136 KB Output is correct
39 Correct 452 ms 191796 KB Output is correct
40 Correct 460 ms 192288 KB Output is correct
41 Correct 690 ms 192592 KB Output is correct
42 Correct 681 ms 192940 KB Output is correct
43 Correct 598 ms 192116 KB Output is correct
44 Correct 606 ms 192784 KB Output is correct
45 Correct 615 ms 193212 KB Output is correct
46 Correct 4 ms 22872 KB Output is correct
47 Correct 4 ms 22876 KB Output is correct
48 Correct 4 ms 22888 KB Output is correct
49 Correct 4 ms 22872 KB Output is correct
50 Correct 4 ms 22876 KB Output is correct
51 Correct 4 ms 25056 KB Output is correct
52 Correct 498 ms 191876 KB Output is correct
53 Correct 468 ms 192412 KB Output is correct
54 Correct 566 ms 205724 KB Output is correct
55 Correct 513 ms 192080 KB Output is correct
56 Correct 462 ms 192508 KB Output is correct
57 Correct 470 ms 191972 KB Output is correct
58 Correct 472 ms 192700 KB Output is correct
59 Correct 503 ms 201640 KB Output is correct
60 Correct 569 ms 205616 KB Output is correct
61 Correct 463 ms 191828 KB Output is correct
62 Correct 473 ms 192596 KB Output is correct
63 Correct 4 ms 22872 KB Output is correct
64 Correct 4 ms 22876 KB Output is correct
65 Correct 3 ms 22876 KB Output is correct
66 Correct 3 ms 23076 KB Output is correct
67 Correct 3 ms 22876 KB Output is correct
68 Correct 4 ms 22872 KB Output is correct
69 Correct 3 ms 22872 KB Output is correct
70 Correct 4 ms 22876 KB Output is correct
71 Correct 4 ms 24924 KB Output is correct
72 Correct 4 ms 24924 KB Output is correct
73 Correct 4 ms 22876 KB Output is correct
74 Correct 3 ms 22876 KB Output is correct
75 Correct 4 ms 22876 KB Output is correct
76 Correct 3 ms 22876 KB Output is correct
77 Correct 4 ms 22872 KB Output is correct
78 Correct 4 ms 24924 KB Output is correct
79 Correct 544 ms 203008 KB Output is correct
80 Correct 1994 ms 200348 KB Output is correct
81 Correct 884 ms 200180 KB Output is correct
82 Correct 820 ms 189136 KB Output is correct
83 Correct 583 ms 189360 KB Output is correct
84 Correct 534 ms 189668 KB Output is correct
85 Correct 332 ms 189572 KB Output is correct
86 Correct 541 ms 198644 KB Output is correct
87 Correct 1853 ms 202236 KB Output is correct
88 Correct 515 ms 189008 KB Output is correct
89 Correct 1691 ms 189680 KB Output is correct
90 Correct 1219 ms 190708 KB Output is correct
91 Correct 1209 ms 191664 KB Output is correct
92 Correct 4 ms 22872 KB Output is correct
93 Correct 4 ms 22972 KB Output is correct
94 Correct 3 ms 22876 KB Output is correct
95 Correct 4 ms 24924 KB Output is correct
96 Correct 4 ms 24924 KB Output is correct
97 Correct 3 ms 23008 KB Output is correct
98 Correct 696 ms 200628 KB Output is correct
99 Correct 1702 ms 196928 KB Output is correct
100 Correct 835 ms 198892 KB Output is correct
101 Correct 1718 ms 190868 KB Output is correct
102 Correct 3532 ms 191140 KB Output is correct
103 Correct 3059 ms 191000 KB Output is correct
104 Correct 565 ms 190940 KB Output is correct
105 Correct 687 ms 204628 KB Output is correct
106 Correct 1663 ms 203452 KB Output is correct
107 Correct 1161 ms 191448 KB Output is correct
108 Execution timed out 4034 ms 188012 KB Time limit exceeded
109 Halted 0 ms 0 KB -