oj.uz

Submission #983703

# Submission time Handle Problem Language Result Execution time Memory
983703 2024-05-16T00:26:29 Z abczz Sprinkler (JOI22_sprinkler) C++14
41 / 100
 4000 ms 204064 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <array>
#define ll long long

using namespace std;

queue <ll> Q;
array <ll, 2> R[200000][41];
ll n, q, t, M, a, b, c, f, cnt, H[200000], P[200000], X[200000], D[200000], dpt[200000];
struct SegTree{
  vector <ll> st, lazy;
  ll stsz = 0;
  void init() {
    st.resize(4*stsz);
    lazy.resize(4*stsz);
    fill(st.begin(), st.end(), 1);
    fill(lazy.begin(), lazy.end(), 1);
  }
  void push(ll id) {
    st[id*2] = st[id*2] * lazy[id] % M;
    st[id*2+1] = st[id*2+1] * lazy[id] % M;
    lazy[id*2] = lazy[id*2] * lazy[id] % M;
    lazy[id*2+1] = lazy[id*2+1] * lazy[id] % M;
    lazy[id] = 1;
  }
  void update(ll id, ll l, ll r, ll ql, ll qr, ll w) {
    if (qr < l || r < ql || ql > qr) return;
    else if (ql <= l && r <= qr) {
      st[id] = st[id] * w % M;
      lazy[id] = lazy[id] * w % M;
      return;
    }
    push(id);
    ll mid = (l+r)/2;
    update(id*2, l, mid, ql, qr, w);
    update(id*2+1, mid+1, r, ql, qr, w);
    st[id] = st[id*2] * st[id*2+1] % M;
  }
  ll query(ll id, ll l, ll r, ll q) {
    if (l == r) return st[id];
    push(id);
    ll mid = (l+r)/2;
    if (q <= mid) return query(id*2, l, mid, q);
    else return query(id*2+1, mid+1, r, q);
  }
}ST[200000];
vector <ll> adj[200000];

void dfs(ll u, ll p) {
  for (auto v : adj[u]) {
    if (v != p) {
      D[v] = D[u] + 1;
      P[v] = u;
      dfs(v, u);
    }
  }
}

void solve(ll u, ll p) {
  R[u][0] = {X[u], X[u]};
  for (int i=1; i<=40; ++i) {
    R[u][i] = {(ll)1e18, (ll)-1e18};
  }
  for (auto v : adj[u]) {
    if (v != p) {
      solve(v, u);
      for (int i=1; i<=40; ++i) {
        R[u][i][0] = min(R[u][i][0], R[v][i-1][0]);
        R[u][i][1] = max(R[u][i][1], R[v][i-1][1]);
      }
    }
  }
}

void bfs() {
  Q.push(0);
  while (!Q.empty()) {
    auto u = Q.front();
    Q.pop();
    X[u] = dpt[D[u]]++;
    for (auto v : adj[u]) {
      if (D[v] > D[u]) Q.push(v);
    }
  }
}

int main() { 
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> M;
  for (int i=0; i<n-1; ++i) {
    cin >> a >> b;
    --a, --b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  for (int i=0; i<n; ++i) {
    cin >> H[i];
  }
  dfs(0, -1);
  P[0] = -1;
  bfs();
  solve(0, -1);
  for (int i=0; i<n; ++i) {
    ST[i].stsz = dpt[i];
    ST[i].init();
  }
  cin >> q;
  while (q--) {
    cin >> t;
    if (t == 1) {
      cin >> a >> b >> c;
      --a;
      ll mnd = 1e18;
      for (int i=0; i<=2*b && a != -1; ++i) {
        mnd = min(mnd, b-(i/2)-(i&1));
        if (D[a]+b-(i/2)-(i&1) < n) ST[D[a]+b-(i/2)-(i&1)].update(1, 0, ST[D[a]+b-(i/2)-(i&1)].stsz-1, R[a][b-(i/2)-(i&1)][0], R[a][b-(i/2)-(i&1)][1], c);
        if (i & 1) a = P[a];
      }
      if (a == -1) a = 0;
      for (int i=mnd-1; i>=0; --i) {
        if (D[a]+i < n) ST[D[a]+i].update(1, 0, ST[D[a]+i].stsz-1, R[a][i][0], R[a][i][1], c);
      }
    }
    else {
      cin >> a;
      --a;
      cout << H[a] * ST[D[a]].query(1, 0, ST[D[a]].stsz-1, X[a]) % M << '\n';
    }
  }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23132 KB Output is correct
2 Correct 5 ms 23132 KB Output is correct
3 Correct 5 ms 23132 KB Output is correct
4 Correct 6 ms 23388 KB Output is correct
5 Correct 7 ms 23132 KB Output is correct
6 Correct 7 ms 23132 KB Output is correct
7 Correct 6 ms 23132 KB Output is correct
8 Correct 5 ms 23132 KB Output is correct
9 Correct 5 ms 23228 KB Output is correct
10 Correct 5 ms 23132 KB Output is correct
11 Correct 5 ms 22988 KB Output is correct
12 Correct 5 ms 23132 KB Output is correct
13 Correct 5 ms 23132 KB Output is correct
14 Correct 6 ms 23132 KB Output is correct
15 Correct 5 ms 23132 KB Output is correct
16 Correct 5 ms 23384 KB Output is correct
17 Correct 5 ms 23132 KB Output is correct
18 Correct 5 ms 23132 KB Output is correct
19 Correct 5 ms 23132 KB Output is correct
20 Correct 5 ms 23220 KB Output is correct
21 Correct 5 ms 23132 KB Output is correct
22 Correct 6 ms 23132 KB Output is correct
23 Correct 5 ms 23132 KB Output is correct
24 Correct 5 ms 23128 KB Output is correct
25 Correct 5 ms 23132 KB Output is correct
26 Correct 5 ms 23200 KB Output is correct
27 Correct 5 ms 23132 KB Output is correct
28 Correct 5 ms 23232 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23132 KB Output is correct
2 Correct 531 ms 183292 KB Output is correct
3 Correct 799 ms 183892 KB Output is correct
4 Correct 542 ms 196436 KB Output is correct
5 Correct 522 ms 183708 KB Output is correct
6 Correct 585 ms 183084 KB Output is correct
7 Correct 595 ms 183836 KB Output is correct
8 Correct 478 ms 185928 KB Output is correct
9 Correct 506 ms 204064 KB Output is correct
10 Correct 578 ms 202588 KB Output is correct
11 Correct 432 ms 183380 KB Output is correct
12 Correct 687 ms 183888 KB Output is correct
13 Correct 336 ms 184716 KB Output is correct
14 Correct 760 ms 184868 KB Output is correct
15 Correct 826 ms 184228 KB Output is correct
16 Correct 820 ms 184656 KB Output is correct
17 Correct 894 ms 184796 KB Output is correct
18 Correct 5 ms 23132 KB Output is correct
19 Correct 5 ms 23132 KB Output is correct
20 Correct 5 ms 23132 KB Output is correct
21 Correct 5 ms 23132 KB Output is correct
22 Correct 5 ms 23236 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23132 KB Output is correct
2 Correct 531 ms 183292 KB Output is correct
3 Correct 799 ms 183892 KB Output is correct
4 Correct 542 ms 196436 KB Output is correct
5 Correct 522 ms 183708 KB Output is correct
6 Correct 585 ms 183084 KB Output is correct
7 Correct 595 ms 183836 KB Output is correct
8 Correct 478 ms 185928 KB Output is correct
9 Correct 506 ms 204064 KB Output is correct
10 Correct 578 ms 202588 KB Output is correct
11 Correct 432 ms 183380 KB Output is correct
12 Correct 687 ms 183888 KB Output is correct
13 Correct 336 ms 184716 KB Output is correct
14 Correct 760 ms 184868 KB Output is correct
15 Correct 826 ms 184228 KB Output is correct
16 Correct 820 ms 184656 KB Output is correct
17 Correct 894 ms 184796 KB Output is correct
18 Correct 5 ms 23132 KB Output is correct
19 Correct 5 ms 23132 KB Output is correct
20 Correct 5 ms 23132 KB Output is correct
21 Correct 5 ms 23132 KB Output is correct
22 Correct 5 ms 23236 KB Output is correct
23 Correct 5 ms 23140 KB Output is correct
24 Correct 500 ms 183356 KB Output is correct
25 Correct 868 ms 183788 KB Output is correct
26 Correct 563 ms 203344 KB Output is correct
27 Correct 575 ms 183376 KB Output is correct
28 Correct 686 ms 183660 KB Output is correct
29 Correct 682 ms 183604 KB Output is correct
30 Correct 523 ms 185836 KB Output is correct
31 Correct 493 ms 196960 KB Output is correct
32 Correct 595 ms 202576 KB Output is correct
33 Correct 493 ms 183372 KB Output is correct
34 Correct 875 ms 183984 KB Output is correct
35 Correct 5 ms 23132 KB Output is correct
36 Correct 5 ms 23132 KB Output is correct
37 Correct 5 ms 23132 KB Output is correct
38 Correct 5 ms 23132 KB Output is correct
39 Correct 5 ms 23132 KB Output is correct
40 Correct 5 ms 23132 KB Output is correct
41 Correct 5 ms 23132 KB Output is correct
42 Correct 5 ms 23132 KB Output is correct
43 Correct 5 ms 23132 KB Output is correct
44 Correct 5 ms 23132 KB Output is correct
45 Correct 5 ms 23132 KB Output is correct
46 Correct 5 ms 23132 KB Output is correct
47 Correct 5 ms 23128 KB Output is correct
48 Correct 5 ms 23128 KB Output is correct
49 Correct 5 ms 23132 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23132 KB Output is correct
2 Correct 761 ms 200828 KB Output is correct
3 Correct 3280 ms 196280 KB Output is correct
4 Correct 1228 ms 196612 KB Output is correct
5 Correct 2663 ms 180884 KB Output is correct
6 Correct 1836 ms 180584 KB Output is correct
7 Correct 951 ms 180908 KB Output is correct
8 Correct 444 ms 182976 KB Output is correct
9 Correct 849 ms 194156 KB Output is correct
10 Correct 3016 ms 199528 KB Output is correct
11 Correct 1366 ms 180424 KB Output is correct
12 Execution timed out 4005 ms 178968 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23132 KB Output is correct
2 Correct 850 ms 196164 KB Output is correct
3 Correct 3601 ms 191332 KB Output is correct
4 Correct 1311 ms 193976 KB Output is correct
5 Correct 2777 ms 182572 KB Output is correct
6 Correct 1963 ms 182312 KB Output is correct
7 Correct 1257 ms 182496 KB Output is correct
8 Correct 397 ms 183740 KB Output is correct
9 Correct 774 ms 202016 KB Output is correct
10 Correct 2961 ms 200700 KB Output is correct
11 Correct 1341 ms 182848 KB Output is correct
12 Execution timed out 4029 ms 178448 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23132 KB Output is correct
2 Correct 5 ms 23132 KB Output is correct
3 Correct 5 ms 23132 KB Output is correct
4 Correct 6 ms 23388 KB Output is correct
5 Correct 7 ms 23132 KB Output is correct
6 Correct 7 ms 23132 KB Output is correct
7 Correct 6 ms 23132 KB Output is correct
8 Correct 5 ms 23132 KB Output is correct
9 Correct 5 ms 23228 KB Output is correct
10 Correct 5 ms 23132 KB Output is correct
11 Correct 5 ms 22988 KB Output is correct
12 Correct 5 ms 23132 KB Output is correct
13 Correct 5 ms 23132 KB Output is correct
14 Correct 6 ms 23132 KB Output is correct
15 Correct 5 ms 23132 KB Output is correct
16 Correct 5 ms 23384 KB Output is correct
17 Correct 5 ms 23132 KB Output is correct
18 Correct 5 ms 23132 KB Output is correct
19 Correct 5 ms 23132 KB Output is correct
20 Correct 5 ms 23220 KB Output is correct
21 Correct 5 ms 23132 KB Output is correct
22 Correct 6 ms 23132 KB Output is correct
23 Correct 5 ms 23132 KB Output is correct
24 Correct 5 ms 23128 KB Output is correct
25 Correct 5 ms 23132 KB Output is correct
26 Correct 5 ms 23200 KB Output is correct
27 Correct 5 ms 23132 KB Output is correct
28 Correct 5 ms 23232 KB Output is correct
29 Correct 5 ms 23132 KB Output is correct
30 Correct 531 ms 183292 KB Output is correct
31 Correct 799 ms 183892 KB Output is correct
32 Correct 542 ms 196436 KB Output is correct
33 Correct 522 ms 183708 KB Output is correct
34 Correct 585 ms 183084 KB Output is correct
35 Correct 595 ms 183836 KB Output is correct
36 Correct 478 ms 185928 KB Output is correct
37 Correct 506 ms 204064 KB Output is correct
38 Correct 578 ms 202588 KB Output is correct
39 Correct 432 ms 183380 KB Output is correct
40 Correct 687 ms 183888 KB Output is correct
41 Correct 336 ms 184716 KB Output is correct
42 Correct 760 ms 184868 KB Output is correct
43 Correct 826 ms 184228 KB Output is correct
44 Correct 820 ms 184656 KB Output is correct
45 Correct 894 ms 184796 KB Output is correct
46 Correct 5 ms 23132 KB Output is correct
47 Correct 5 ms 23132 KB Output is correct
48 Correct 5 ms 23132 KB Output is correct
49 Correct 5 ms 23132 KB Output is correct
50 Correct 5 ms 23236 KB Output is correct
51 Correct 5 ms 23140 KB Output is correct
52 Correct 500 ms 183356 KB Output is correct
53 Correct 868 ms 183788 KB Output is correct
54 Correct 563 ms 203344 KB Output is correct
55 Correct 575 ms 183376 KB Output is correct
56 Correct 686 ms 183660 KB Output is correct
57 Correct 682 ms 183604 KB Output is correct
58 Correct 523 ms 185836 KB Output is correct
59 Correct 493 ms 196960 KB Output is correct
60 Correct 595 ms 202576 KB Output is correct
61 Correct 493 ms 183372 KB Output is correct
62 Correct 875 ms 183984 KB Output is correct
63 Correct 5 ms 23132 KB Output is correct
64 Correct 5 ms 23132 KB Output is correct
65 Correct 5 ms 23132 KB Output is correct
66 Correct 5 ms 23132 KB Output is correct
67 Correct 5 ms 23132 KB Output is correct
68 Correct 5 ms 23132 KB Output is correct
69 Correct 5 ms 23132 KB Output is correct
70 Correct 5 ms 23132 KB Output is correct
71 Correct 5 ms 23132 KB Output is correct
72 Correct 5 ms 23132 KB Output is correct
73 Correct 5 ms 23132 KB Output is correct
74 Correct 5 ms 23132 KB Output is correct
75 Correct 5 ms 23128 KB Output is correct
76 Correct 5 ms 23128 KB Output is correct
77 Correct 5 ms 23132 KB Output is correct
78 Correct 5 ms 23132 KB Output is correct
79 Correct 761 ms 200828 KB Output is correct
80 Correct 3280 ms 196280 KB Output is correct
81 Correct 1228 ms 196612 KB Output is correct
82 Correct 2663 ms 180884 KB Output is correct
83 Correct 1836 ms 180584 KB Output is correct
84 Correct 951 ms 180908 KB Output is correct
85 Correct 444 ms 182976 KB Output is correct
86 Correct 849 ms 194156 KB Output is correct
87 Correct 3016 ms 199528 KB Output is correct
88 Correct 1366 ms 180424 KB Output is correct
89 Execution timed out 4005 ms 178968 KB Time limit exceeded
90 Halted 0 ms 0 KB -