제출 #588766

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
588766		balbit	Sprinkler (JOI22_sprinkler)	C++14	9 / 100	4067 ms	99628 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define int ll
#define pii pair<ll, ll>
#define f first
#define s second

#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)

#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<"- "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do( T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT

const int maxn = 2e5+5;
signed L;
vector<int> rawt[maxn], g[maxn];
int par[maxn];
ll H[maxn];
int ordpos[maxn], dep[maxn];;
vector<int> depv[maxn];

ll seg[maxn*4], tg[maxn*4];

inline void push(int o, int l, int r) {
    if (tg[o] != 1) {
        seg[o] *= tg[o]; seg[o] %= L;
        if (l!=r) {
            tg[o*2] = tg[o*2] * tg[o] % L;
            tg[o*2+1] = tg[o*2+1] * tg[o] % L;
        }
        tg[o] = 1;
    }
}

void MO(int L, int R, int v, int o=1, int l=0, int r=maxn-1) {
    push(o,l,r);
    if (l > R || r < L) return;
    if (l >= L && r <= R) {
        tg[o] = tg[o] * v % ::L;
        push(o,l,r); return;
    }
    int mid = (l+r)/2;
    MO(L,R,v,o*2,l,mid); MO(L,R,v,o*2+1,mid+1,r);
    seg[o] = seg[o*2] * seg[o*2+1] % ::L;
}

ll get(int p, int o=1, int l=0, int r=maxn-1) {
    if (l > p || r < p) assert(0);
    push(o,l,r);
    if (l == r) return seg[o];
    int mid = (l+r)/2;
    if (p <= mid) return get(p,o*2,l,mid);
    else return get(p,o*2+1,mid+1,r);
}

void build(){
    fill(seg, seg+maxn*4, 1);
    fill(tg, tg+maxn*4, 1);
}

void dfs1(int v, int p) {
    par[v] = p;
    depv[dep[v]].pb(v);
    for (int u : rawt[v]) {
        if (u == p) continue;
        g[v].pb(u);
        dep[u] = dep[v] + 1;
        dfs1(u,v);
    }
}

pii findrng(int v, int tdp) {
    int l,r;
    {
        int at = v;
        while (dep[at] < tdp) {
            if (SZ(g[at]) == 0) {
                return {-1, -1};
            }
            at = g[at][0];
        }
        l = ordpos[at];
    }
    {
        int at = v;
        while (dep[at] < tdp) at = g[at].back();
        r = ordpos[at];
    }
    return {l,r};
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    bug(1,2);

    int n; cin>>n>>L;
    REP(i,n-1) {
        int a,b; cin>>a>>b; --a; --b;
        rawt[a].pb(b);
        rawt[b].pb(a);
    }

    dfs1(0,-1);
    int IT = 0;
    REP(i, maxn) {
        for (int e : depv[i]) {
            bug(e, IT);
            ordpos[e] = IT++;
        }
    }
    build();
    REP(i,n) cin>>H[i], MO(ordpos[i],ordpos[i],H[i]);

    int q; cin>>q;

    while (q--) {
        int tp; cin>>tp;
        if (tp == 1) {
            int v, d, w; cin>>v>>d>>w; --v;
            int at = v;
            for (int dp = dep[v] + d; dp >= dep[v] - d; dp--) {
                if (dp < 0 || dp >= maxn || SZ(depv[dp]) == 0) continue;
                while (at != 0 && dep[v] - dep[par[at]] + dp - dep[par[at]] <= d) {
                    at = par[at];
                }
                pii ha = findrng(at, dp);
                if (ha.f == -1) continue;
                bug(ha.f, ha.s, w);
                MO(ha.f, ha.s, w);
            }
        }else{
            int v; cin>>v; --v;
            bug(ordpos[v]);
            cout<<get(ordpos[v])<<endl;
        }

    }

}

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