Submission #1125274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125274		nguyenkhangninh99	Sprinkler (JOI22_sprinkler)	C++20	41 / 100	4094 ms	82376 KiB

sprinkler

#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O2", "unroll-loops", "Ofast")
#pragma GCC target("popcnt")
#pragma GCC target("avx,avx2,fma")
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
const int maxn = 2e5 + 69;

vector<array<int, 4>> query;

vector<int> g[maxn], c[maxn];

int mod;

int h[maxn];
int tin[maxn], out[maxn], depth[maxn], par[maxn], timeDfs = 0;
struct SegmentTree{
	vector<long long> st, lazy;

	void init(long long sz){
		st.assign(4 * sz + 1, 1LL);
		lazy.assign(4 * sz + 1, 1LL);
	}

	void down(int id){
		long long &x = lazy[id];
		st[id << 1] = st[id << 1] * x % mod;
		st[id << 1 | 1] = st[id << 1 | 1] * x % mod;
		lazy[id << 1] = lazy[id << 1] * x % mod;
		lazy[id << 1 | 1] = lazy[id << 1 | 1] * x % mod;
		x = 1;
	}

	void update(int id, int l, int r, int u, int v, long long val){
		if(l > v || u > r) return;
		if(u <= l && r <= v){
			st[id] = st[id] * val % mod;
			lazy[id] = lazy[id] * val % mod;
			return;
		}
		int mid = (l + r) >> 1;
		down(id);
		update(id << 1, l, mid, u, v, val);
		update(id << 1 | 1, mid + 1, r, u, v, val);
		st[id] = st[id << 1] * st[id << 1 | 1] % mod;
	}

	long long get(int id, int l, int r, int pos){
    	if(l == r) return st[id];
		int mid = (l + r) >> 1;
		down(id);
		if(pos <= mid) return get(id << 1, l, mid, pos);
		else return get(id << 1 | 1, mid + 1, r, pos);
	}
} tree[maxn];

void dfs(int u, int pre){
	tin[u] = ++timeDfs;
	depth[u] = depth[pre] + 1;
	c[depth[u]].push_back(tin[u]);
	par[u] = pre;
	for(int v: g[u]){
		if(v == pre) continue;
		dfs(v, u);
	}

	out[u] = timeDfs;
}
void solve(){
	int n; cin >> n >> mod;

	for(int i = 1; i <= n - 1; i++){
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	for(int i = 1; i <= n; i++) cin >> h[i];

	dfs(1, 0);

	for(int i = 1; i <= n + 65; i++) tree[i].init(sz(c[i]) + 1);
	for(int i = 1; i <= n; i++){
		int ll = lower_bound(all(c[depth[i]]), tin[i]) - c[depth[i]].begin() + 1;
		tree[depth[i]].update(1, 1, sz(c[depth[i]]), ll, ll, h[i]);
	}

	int qry; cin >> qry;
	while(qry--){
		int t, x, d = -1; 
		long long w = -1; cin >> t >> x;
		if(t == 1){
			cin >> d >> w;

			if(d == 0){
				//update chính nó
				int ll = lower_bound(all(c[depth[x]]), tin[x]) - c[depth[x]].begin() + 1;
				tree[depth[x]].update(1, 1, sz(c[depth[x]]), ll, ll, w);
			}
			else{
				int u = x, dd = d;
				for(int i = 0; i + 2 <= dd; i++){
					int ll = lower_bound(all(c[depth[u] + d]), tin[u]) - c[depth[u] + d].begin() + 1;
					int rr = upper_bound(all(c[depth[u] + d]), out[u]) - c[depth[u] + d].begin();
					tree[depth[u] + d].update(1, 1, sz(c[depth[u] + d]), ll, rr, w);

					ll = lower_bound(all(c[depth[u] + d - 1]), tin[u]) - c[depth[u] + d - 1].begin() + 1;
					rr = upper_bound(all(c[depth[u] + d - 1]), out[u]) - c[depth[u] + d - 1].begin();
					tree[depth[u] + d - 1].update(1, 1, sz(c[depth[u] + d - 1]), ll, rr, w);
					d -= 1;
					u = par[u];
					if(!u){
						for(int j = 1; j <= d; j++){
							ll = lower_bound(all(c[depth[1] + d - j]), tin[1]) - c[depth[1] + d - j].begin() + 1;
							rr = upper_bound(all(c[depth[1] + d - j]), out[1]) - c[depth[1] + d - j].begin();
							tree[depth[1] + d - j].update(1, 1, sz(c[depth[1] + d - j]), ll, rr, w);
						}
						break;
					}
				}

				if(u){
					//update những thằng con
					int l = lower_bound(all(c[depth[u] + 1]), tin[u]) - c[depth[u] + 1].begin() + 1;
					int r = upper_bound(all(c[depth[u] + 1]), out[u]) - c[depth[u] + 1].begin();
					tree[depth[u] + 1].update(1, 1, sz(c[depth[u] + 1]), l, r, w);

					int ll = lower_bound(all(c[depth[u]]), tin[u]) - c[depth[u]].begin() + 1;
					tree[depth[u]].update(1, 1, sz(c[depth[u]]), ll, ll, w);
				}

				u = par[u];
				if(u){
					int ll = lower_bound(all(c[depth[u]]), tin[u]) - c[depth[u]].begin() + 1;
					tree[depth[u]].update(1, 1, sz(c[depth[u]]), ll, ll, w);
				}
			}
		}
		else{
			int k = lower_bound(all(c[depth[x]]), tin[x]) - c[depth[x]].begin() + 1;
			cout << tree[depth[x]].get(1, 1, c[depth[x]].size(), k) << "\n";
		}	

	}
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	solve();
}

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