oj.uz

Submission #850845

# Submission time Handle Problem Language Result Execution time Memory
850845 2023-09-17T14:24:14 Z EJIC_B_KEDAX Sprinkler (JOI22_sprinkler) C++14
100 / 100
 2132 ms 203864 KB 
#include <bits/stdc++.h>
#include <random>

#ifndef LOCAL
    #pragma GCC optimize("O3")
    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
typedef long long ll;
typedef double dd;
typedef long double ld;
typedef unsigned int uii;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()



void solve();

mt19937_64 mt(1);

int32_t main() {
#ifdef LOCAL
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#else
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    //freopen("amusing.in", "r", stdin);
    //freopen("amusing.out", "w", stdout);
#endif
    cout << fixed << setprecision(30);
    int tests = 1;
    //cin >> tests;
    while (tests--) {
        solve();
    }
}

ll mod;

struct st_down {
    vector<long long> tree;
    int n;

    void build(const vector<int>& arr) {
        n = arr.size();
        tree.assign(2 * n, 1);
        for (int i = 0; i < n; i++) {
            tree[n + i] = arr[i];
        }
    }

    long long find_value(int pos) {
        pos += n;
        long long ans = 1;
        while (pos > 0) {
            ans = (ans * tree[pos]) % mod;
            pos >>= 1;
        }
        return ans;
    }

    void segment_update(int l, int r, int addval) {
        l += n;
        r += n;
        while (l < r) {
            if (l & 1) {
                tree[l++] *= addval;
                tree[l - 1] %= mod;
            }
            if (r & 1) {
                tree[--r] *= addval;
                tree[r] %= mod;
            }
            l >>= 1;
            r >>= 1;
        }
    }
};

pair<int, int> seg[200200][41];

void dfs(int s, int p, vector<vector<int>>& g, int dist[], vector<vector<int>>& d, int pr[]) {
    if (p != -1) {
        dist[s] = dist[p] + 1;
    } else {
        dist[s] = 0;
    }
    pr[s] = p;
    d[dist[s]].push_back(s);
    seg[s][0] = {d[dist[s]].size() - 1, d[dist[s]].size() - 1};
    for (int i = 1; i < 41; i++) {
        seg[s][i] = {INT32_MAX, INT32_MIN};
    }
    for (int i : g[s]) {
        if (i != p) {
            dfs(i, s, g, dist, d, pr);
            for (int j = 1; j < 41; j++) {
                seg[s][j].x = min(seg[s][j].x, seg[i][j - 1].x);
            }
            for (int j = 1; j < 41; j++) {
                seg[s][j].y = max(seg[s][j].y, seg[i][j - 1].y);
            }
        }
    }
}

void solve() {
    int n;
    cin >> n >> mod;
    vector<vector<int>> g(n), d(n);
    int deg[200200], dist[200200], h[200200], p[200200];
    for (int i = 0; i < n; i++) {
        deg[i] = 0;
    }
    int pr[200200][41], lev[200200][41];
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v; u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }
    int root = 0;
    for (int i = 0; i < n; i++) {
        if (deg[i] == 1) {
            root = i;
            break;
        }
    }
    dfs(root, -1, g, dist, d, p);
    for (int i = 0; i < n; i++) {
        int nw = i, lv = 0, nlev = 0;
        for (int c = 0; c < 41; c++) {
            while (c > nlev) {
                nlev++;
                if (p[nw] != -1) {
                    lv++;
                    nw = p[nw];
                }
            }
            pr[i][c] = nw;
            lev[i][c] = lv;
        }
    }
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < d[i].size(); j++) {
            d[i][j] = h[d[i][j]];
        }
    }
    st_down dec[200200];
    for (int i = 0; i < n; i++) {
        dec[i].build(d[i]);
    }
    int q;
    cin >> q;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int x, dk, wk;
            cin >> x >> dk >> wk; x--;
            for (int l = max(-dk, dist[x] - n + 1); l <= dk && l <= dist[x]; l++) {
                int c = (dk + l) / 2;
                if (c - l >= 0 && c - l <= dk) {
                    int l1, r1;
                    l1 = seg[pr[x][c]][lev[x][c] - l].x;
                    r1 = seg[pr[x][c]][lev[x][c] - l].y;
                    dec[dist[x] - l].segment_update(l1, r1 + 1, wk);
                }
            }
        } else {
            int x;
            cin >> x; x--;
            cout << (dec[dist[x]].find_value(seg[x][0].x) % mod + mod) % mod << '\n';
        }
    }
}

Compilation message

sprinkler.cpp: In function 'void solve()':
sprinkler.cpp:156:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |         for (int j = 0; j < d[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 74076 KB Output is correct
2 Correct 37 ms 74064 KB Output is correct
3 Correct 37 ms 73912 KB Output is correct
4 Correct 38 ms 76368 KB Output is correct
5 Correct 38 ms 76368 KB Output is correct
6 Correct 39 ms 76224 KB Output is correct
7 Correct 38 ms 76368 KB Output is correct
8 Correct 39 ms 76368 KB Output is correct
9 Correct 37 ms 74324 KB Output is correct
10 Correct 37 ms 74068 KB Output is correct
11 Correct 37 ms 74064 KB Output is correct
12 Correct 37 ms 74320 KB Output is correct
13 Correct 38 ms 74072 KB Output is correct
14 Correct 38 ms 74068 KB Output is correct
15 Correct 37 ms 74064 KB Output is correct
16 Correct 37 ms 73924 KB Output is correct
17 Correct 39 ms 74084 KB Output is correct
18 Correct 38 ms 74088 KB Output is correct
19 Correct 37 ms 74072 KB Output is correct
20 Correct 39 ms 74064 KB Output is correct
21 Correct 37 ms 74064 KB Output is correct
22 Correct 39 ms 74064 KB Output is correct
23 Correct 38 ms 74064 KB Output is correct
24 Correct 37 ms 74064 KB Output is correct
25 Correct 37 ms 74064 KB Output is correct
26 Correct 37 ms 74064 KB Output is correct
27 Correct 38 ms 74064 KB Output is correct
28 Correct 37 ms 74064 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 74068 KB Output is correct
2 Correct 406 ms 162224 KB Output is correct
3 Correct 437 ms 158812 KB Output is correct
4 Correct 486 ms 193360 KB Output is correct
5 Correct 415 ms 160248 KB Output is correct
6 Correct 392 ms 159848 KB Output is correct
7 Correct 405 ms 160212 KB Output is correct
8 Correct 360 ms 160788 KB Output is correct
9 Correct 437 ms 194900 KB Output is correct
10 Correct 528 ms 191824 KB Output is correct
11 Correct 386 ms 162032 KB Output is correct
12 Correct 475 ms 158800 KB Output is correct
13 Correct 309 ms 159452 KB Output is correct
14 Correct 322 ms 159268 KB Output is correct
15 Correct 324 ms 158924 KB Output is correct
16 Correct 320 ms 159108 KB Output is correct
17 Correct 339 ms 159504 KB Output is correct
18 Correct 37 ms 74064 KB Output is correct
19 Correct 38 ms 73984 KB Output is correct
20 Correct 39 ms 74060 KB Output is correct
21 Correct 39 ms 74072 KB Output is correct
22 Correct 39 ms 74072 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 74068 KB Output is correct
2 Correct 406 ms 162224 KB Output is correct
3 Correct 437 ms 158812 KB Output is correct
4 Correct 486 ms 193360 KB Output is correct
5 Correct 415 ms 160248 KB Output is correct
6 Correct 392 ms 159848 KB Output is correct
7 Correct 405 ms 160212 KB Output is correct
8 Correct 360 ms 160788 KB Output is correct
9 Correct 437 ms 194900 KB Output is correct
10 Correct 528 ms 191824 KB Output is correct
11 Correct 386 ms 162032 KB Output is correct
12 Correct 475 ms 158800 KB Output is correct
13 Correct 309 ms 159452 KB Output is correct
14 Correct 322 ms 159268 KB Output is correct
15 Correct 324 ms 158924 KB Output is correct
16 Correct 320 ms 159108 KB Output is correct
17 Correct 339 ms 159504 KB Output is correct
18 Correct 37 ms 74064 KB Output is correct
19 Correct 38 ms 73984 KB Output is correct
20 Correct 39 ms 74060 KB Output is correct
21 Correct 39 ms 74072 KB Output is correct
22 Correct 39 ms 74072 KB Output is correct
23 Correct 37 ms 74064 KB Output is correct
24 Correct 378 ms 161872 KB Output is correct
25 Correct 501 ms 158912 KB Output is correct
26 Correct 515 ms 193452 KB Output is correct
27 Correct 422 ms 160332 KB Output is correct
28 Correct 396 ms 160308 KB Output is correct
29 Correct 458 ms 160072 KB Output is correct
30 Correct 345 ms 160576 KB Output is correct
31 Correct 516 ms 194900 KB Output is correct
32 Correct 574 ms 191920 KB Output is correct
33 Correct 371 ms 161960 KB Output is correct
34 Correct 487 ms 158800 KB Output is correct
35 Correct 37 ms 74000 KB Output is correct
36 Correct 37 ms 74064 KB Output is correct
37 Correct 39 ms 74064 KB Output is correct
38 Correct 37 ms 74108 KB Output is correct
39 Correct 38 ms 74064 KB Output is correct
40 Correct 36 ms 73860 KB Output is correct
41 Correct 37 ms 74064 KB Output is correct
42 Correct 38 ms 74064 KB Output is correct
43 Correct 38 ms 74068 KB Output is correct
44 Correct 37 ms 74072 KB Output is correct
45 Correct 38 ms 74076 KB Output is correct
46 Correct 37 ms 74064 KB Output is correct
47 Correct 37 ms 74032 KB Output is correct
48 Correct 37 ms 74068 KB Output is correct
49 Correct 37 ms 74064 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 74064 KB Output is correct
2 Correct 575 ms 192224 KB Output is correct
3 Correct 1728 ms 191604 KB Output is correct
4 Correct 887 ms 191852 KB Output is correct
5 Correct 832 ms 158868 KB Output is correct
6 Correct 645 ms 158540 KB Output is correct
7 Correct 588 ms 158768 KB Output is correct
8 Correct 370 ms 159140 KB Output is correct
9 Correct 579 ms 192372 KB Output is correct
10 Correct 1711 ms 191804 KB Output is correct
11 Correct 508 ms 159008 KB Output is correct
12 Correct 1663 ms 158824 KB Output is correct
13 Correct 1547 ms 159316 KB Output is correct
14 Correct 1477 ms 160416 KB Output is correct
15 Correct 37 ms 74064 KB Output is correct
16 Correct 37 ms 74064 KB Output is correct
17 Correct 38 ms 74064 KB Output is correct
18 Correct 37 ms 74064 KB Output is correct
19 Correct 38 ms 74064 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 74064 KB Output is correct
2 Correct 564 ms 194908 KB Output is correct
3 Correct 1687 ms 192084 KB Output is correct
4 Correct 819 ms 193476 KB Output is correct
5 Correct 760 ms 160644 KB Output is correct
6 Correct 693 ms 160532 KB Output is correct
7 Correct 584 ms 160156 KB Output is correct
8 Correct 388 ms 160508 KB Output is correct
9 Correct 627 ms 195244 KB Output is correct
10 Correct 1716 ms 191896 KB Output is correct
11 Correct 530 ms 161712 KB Output is correct
12 Correct 1701 ms 158840 KB Output is correct
13 Correct 1613 ms 168716 KB Output is correct
14 Correct 1554 ms 170080 KB Output is correct
15 Correct 42 ms 74008 KB Output is correct
16 Correct 38 ms 73920 KB Output is correct
17 Correct 39 ms 73988 KB Output is correct
18 Correct 38 ms 74064 KB Output is correct
19 Correct 37 ms 74076 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 74076 KB Output is correct
2 Correct 37 ms 74064 KB Output is correct
3 Correct 37 ms 73912 KB Output is correct
4 Correct 38 ms 76368 KB Output is correct
5 Correct 38 ms 76368 KB Output is correct
6 Correct 39 ms 76224 KB Output is correct
7 Correct 38 ms 76368 KB Output is correct
8 Correct 39 ms 76368 KB Output is correct
9 Correct 37 ms 74324 KB Output is correct
10 Correct 37 ms 74068 KB Output is correct
11 Correct 37 ms 74064 KB Output is correct
12 Correct 37 ms 74320 KB Output is correct
13 Correct 38 ms 74072 KB Output is correct
14 Correct 38 ms 74068 KB Output is correct
15 Correct 37 ms 74064 KB Output is correct
16 Correct 37 ms 73924 KB Output is correct
17 Correct 39 ms 74084 KB Output is correct
18 Correct 38 ms 74088 KB Output is correct
19 Correct 37 ms 74072 KB Output is correct
20 Correct 39 ms 74064 KB Output is correct
21 Correct 37 ms 74064 KB Output is correct
22 Correct 39 ms 74064 KB Output is correct
23 Correct 38 ms 74064 KB Output is correct
24 Correct 37 ms 74064 KB Output is correct
25 Correct 37 ms 74064 KB Output is correct
26 Correct 37 ms 74064 KB Output is correct
27 Correct 38 ms 74064 KB Output is correct
28 Correct 37 ms 74064 KB Output is correct
29 Correct 45 ms 74068 KB Output is correct
30 Correct 406 ms 162224 KB Output is correct
31 Correct 437 ms 158812 KB Output is correct
32 Correct 486 ms 193360 KB Output is correct
33 Correct 415 ms 160248 KB Output is correct
34 Correct 392 ms 159848 KB Output is correct
35 Correct 405 ms 160212 KB Output is correct
36 Correct 360 ms 160788 KB Output is correct
37 Correct 437 ms 194900 KB Output is correct
38 Correct 528 ms 191824 KB Output is correct
39 Correct 386 ms 162032 KB Output is correct
40 Correct 475 ms 158800 KB Output is correct
41 Correct 309 ms 159452 KB Output is correct
42 Correct 322 ms 159268 KB Output is correct
43 Correct 324 ms 158924 KB Output is correct
44 Correct 320 ms 159108 KB Output is correct
45 Correct 339 ms 159504 KB Output is correct
46 Correct 37 ms 74064 KB Output is correct
47 Correct 38 ms 73984 KB Output is correct
48 Correct 39 ms 74060 KB Output is correct
49 Correct 39 ms 74072 KB Output is correct
50 Correct 39 ms 74072 KB Output is correct
51 Correct 37 ms 74064 KB Output is correct
52 Correct 378 ms 161872 KB Output is correct
53 Correct 501 ms 158912 KB Output is correct
54 Correct 515 ms 193452 KB Output is correct
55 Correct 422 ms 160332 KB Output is correct
56 Correct 396 ms 160308 KB Output is correct
57 Correct 458 ms 160072 KB Output is correct
58 Correct 345 ms 160576 KB Output is correct
59 Correct 516 ms 194900 KB Output is correct
60 Correct 574 ms 191920 KB Output is correct
61 Correct 371 ms 161960 KB Output is correct
62 Correct 487 ms 158800 KB Output is correct
63 Correct 37 ms 74000 KB Output is correct
64 Correct 37 ms 74064 KB Output is correct
65 Correct 39 ms 74064 KB Output is correct
66 Correct 37 ms 74108 KB Output is correct
67 Correct 38 ms 74064 KB Output is correct
68 Correct 36 ms 73860 KB Output is correct
69 Correct 37 ms 74064 KB Output is correct
70 Correct 38 ms 74064 KB Output is correct
71 Correct 38 ms 74068 KB Output is correct
72 Correct 37 ms 74072 KB Output is correct
73 Correct 38 ms 74076 KB Output is correct
74 Correct 37 ms 74064 KB Output is correct
75 Correct 37 ms 74032 KB Output is correct
76 Correct 37 ms 74068 KB Output is correct
77 Correct 37 ms 74064 KB Output is correct
78 Correct 40 ms 74064 KB Output is correct
79 Correct 575 ms 192224 KB Output is correct
80 Correct 1728 ms 191604 KB Output is correct
81 Correct 887 ms 191852 KB Output is correct
82 Correct 832 ms 158868 KB Output is correct
83 Correct 645 ms 158540 KB Output is correct
84 Correct 588 ms 158768 KB Output is correct
85 Correct 370 ms 159140 KB Output is correct
86 Correct 579 ms 192372 KB Output is correct
87 Correct 1711 ms 191804 KB Output is correct
88 Correct 508 ms 159008 KB Output is correct
89 Correct 1663 ms 158824 KB Output is correct
90 Correct 1547 ms 159316 KB Output is correct
91 Correct 1477 ms 160416 KB Output is correct
92 Correct 37 ms 74064 KB Output is correct
93 Correct 37 ms 74064 KB Output is correct
94 Correct 38 ms 74064 KB Output is correct
95 Correct 37 ms 74064 KB Output is correct
96 Correct 38 ms 74064 KB Output is correct
97 Correct 44 ms 74064 KB Output is correct
98 Correct 564 ms 194908 KB Output is correct
99 Correct 1687 ms 192084 KB Output is correct
100 Correct 819 ms 193476 KB Output is correct
101 Correct 760 ms 160644 KB Output is correct
102 Correct 693 ms 160532 KB Output is correct
103 Correct 584 ms 160156 KB Output is correct
104 Correct 388 ms 160508 KB Output is correct
105 Correct 627 ms 195244 KB Output is correct
106 Correct 1716 ms 191896 KB Output is correct
107 Correct 530 ms 161712 KB Output is correct
108 Correct 1701 ms 158840 KB Output is correct
109 Correct 1613 ms 168716 KB Output is correct
110 Correct 1554 ms 170080 KB Output is correct
111 Correct 42 ms 74008 KB Output is correct
112 Correct 38 ms 73920 KB Output is correct
113 Correct 39 ms 73988 KB Output is correct
114 Correct 38 ms 74064 KB Output is correct
115 Correct 37 ms 74076 KB Output is correct
116 Correct 578 ms 168272 KB Output is correct
117 Correct 1641 ms 170864 KB Output is correct
118 Correct 831 ms 203864 KB Output is correct
119 Correct 777 ms 170340 KB Output is correct
120 Correct 730 ms 169900 KB Output is correct
121 Correct 709 ms 170448 KB Output is correct
122 Correct 383 ms 170772 KB Output is correct
123 Correct 607 ms 203288 KB Output is correct
124 Correct 1756 ms 203504 KB Output is correct
125 Correct 563 ms 169284 KB Output is correct
126 Correct 1708 ms 170812 KB Output is correct
127 Correct 1774 ms 171096 KB Output is correct
128 Correct 2103 ms 171816 KB Output is correct
129 Correct 2132 ms 172584 KB Output is correct