oj.uz

Submission #875802

# Submission time Handle Problem Language Result Execution time Memory
875802 2023-11-20T13:58:23 Z danikoynov Sprinkler (JOI22_sprinkler) C++14
41 / 100
 4000 ms 97996 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxq = 4e5 + 10;

struct query
{
    int type, ver, d, t;
    ll w;
}ask[maxq];

const int maxn = 2e5 + 10;

int n, q;
ll l, h[maxn];
vector < query > task[maxn];
vector < int > adj[maxn];

bool cmp(query a1, query a2)
{
    return a1.d < a2.d;
}

void input()
{
    cin >> n >> l;
    for (int i = 1; i < n; i ++)
    {
        int v, u;
        cin >> v >> u;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }
    for (int i = 1; i <= n; i ++)
        cin >> h[i];
    cin >> q;
    for (int i = 1; i <= q; i ++)
    {
        cin >> ask[i].type;
        if (ask[i].type == 1)
            cin >> ask[i].ver >> ask[i].d >> ask[i].w;
        else
            cin >> ask[i].ver;
        ask[i].t = i;
    }
}

struct segment_tree
{
    vector < ll > tree, lazy;

    segment_tree(int len = 0)
    {
        tree.resize(4 * (len + 1));
        lazy.resize(4 * (len + 1));
        fill(tree.begin(), tree.end(), 1);
        fill(lazy.begin(), lazy.end(), 1);
    }

    void push_lazy(int &root, int &left, int &right)
    {

        tree[root] *= lazy[root];
        tree[root] %= l;
        if (left != right)
        {
            lazy[root * 2] *= (lazy[root]);
            lazy[root * 2 + 1] *= (lazy[root]);
            lazy[root * 2] %= l;
            lazy[root * 2 + 1] %= l;
        }

        lazy[root] = 1;
    }

    void update_range(int root, int left, int right, int qleft, int qright, ll val)
    {
        if (lazy[root] != 1)
        push_lazy(root, left, right);
        if (left > qright || right < qleft)
            return;

        if (left >= qleft && right <= qright)
        {
            lazy[root] = val;
            push_lazy(root, left, right);
            return;
        }

        int mid = (left + right) / 2;
        update_range(root * 2, left, mid, qleft, qright, val);
        update_range(root * 2 + 1, mid + 1, right, qleft, qright, val);
    }

    ll get_point(int root, int left, int right, int pos)
    {
        if (lazy[root] != 1)
        push_lazy(root, left, right);
        if (left == right)
            return tree[root];

        int mid = (left + right) / 2;
        if (pos <= mid)
            return get_point(root * 2, left, mid, pos);
        return get_point(root * 2 + 1, mid + 1, right, pos);
    }
};

segment_tree st[maxn];
int par[maxn], depth[maxn];
vector < int > by_depth[maxn];
int tin[maxn], tout[maxn], timer, rev[maxn];
void dfs(int v)
{
    tin[v] = ++ timer;
    ///cout << "dfs " << v << " "  << depth[v] << endl;
    rev[v] = by_depth[depth[v]].size();
    by_depth[depth[v]].push_back(v);
    for (int u : adj[v])
    {
        if (u == par[v])
            continue;
        par[u] = v;
        depth[u] = depth[v] + 1;
        dfs(u);
    }
    tout[v] = timer;
}

const int maxd = 40;

void update_row(int row, int left, int right, ll val)
{

    int lf = 0, rf = (int)(by_depth[row].size()) - 1;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (tin[by_depth[row][mf]] < left)
            lf = mf + 1;
        else
            rf = mf - 1;
    }

    int lb = lf;

    lf = 0;
    rf = (int)(by_depth[row].size()) - 1;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (tin[by_depth[row][mf]] <= right)
            lf = mf + 1;
        else
            rf = mf - 1;
    }
    int rb = rf;

    st[row].update_range(1, 0, (int)(by_depth[row].size()) - 1, lb, rb, val);

}

void make_query(int v)
{
    ll ans = h[v];
    ans = ans * st[depth[v]].get_point(1, 0, (int)(by_depth[depth[v]].size()) - 1, rev[v]);
    ans %= l;
    cout << ans << endl;
}
void simulate()
{
    for (int i = 1; i <= n; i ++)
        st[i] = segment_tree(by_depth[i].size());
    for (int i = 1; i <= q; i ++)
    {
        if (ask[i].type == 2)
            make_query(ask[i].ver);
        else
        {
            int cnt = 0, ver = ask[i].ver;
            while(ver != 1 && cnt <= ask[i].d)
            {
                int lf = ask[i].d - cnt;
                update_row(depth[ver] + lf, tin[ver], tout[ver], ask[i].w);
                ///cout << "update " << ver << " " << depth[ver] + lf << endl;
                //if (lf != 0)
                update_row(depth[ver] + lf - 1, tin[ver], tout[ver], ask[i].w);
                cnt ++;
                ver = par[ver];
            }
            if (ver == 1 && cnt <= ask[i].d)
            {
                int lf = ask[i].d - cnt;
                for (int j = 0; j <= lf; j ++)
                {
                    ///cout << "update " << ver << " " << depth[ver] + j << endl;
                    update_row(depth[ver] + j, tin[ver], tout[ver], ask[i].w);
                }
            }

        }

    }

}
void solve()
{
    input();
    ///offline_queries();
    depth[1] = 1;
    dfs(1);
    simulate();
}

int main()
{
    speed();
    solve();
    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 48208 KB Output is correct
2 Correct 27 ms 47952 KB Output is correct
3 Correct 28 ms 47736 KB Output is correct
4 Correct 29 ms 47960 KB Output is correct
5 Correct 30 ms 47956 KB Output is correct
6 Correct 36 ms 47964 KB Output is correct
7 Correct 29 ms 47964 KB Output is correct
8 Correct 32 ms 48084 KB Output is correct
9 Correct 28 ms 47964 KB Output is correct
10 Correct 35 ms 47956 KB Output is correct
11 Correct 28 ms 48084 KB Output is correct
12 Correct 29 ms 47820 KB Output is correct
13 Correct 28 ms 47964 KB Output is correct
14 Correct 28 ms 47852 KB Output is correct
15 Correct 28 ms 47948 KB Output is correct
16 Correct 28 ms 47952 KB Output is correct
17 Correct 28 ms 47964 KB Output is correct
18 Correct 28 ms 48148 KB Output is correct
19 Correct 28 ms 47964 KB Output is correct
20 Correct 29 ms 47964 KB Output is correct
21 Correct 28 ms 47952 KB Output is correct
22 Correct 29 ms 47964 KB Output is correct
23 Correct 28 ms 47960 KB Output is correct
24 Correct 28 ms 47956 KB Output is correct
25 Correct 28 ms 47956 KB Output is correct
26 Correct 28 ms 47992 KB Output is correct
27 Correct 28 ms 47964 KB Output is correct
28 Correct 28 ms 47964 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47964 KB Output is correct
2 Correct 302 ms 81232 KB Output is correct
3 Correct 631 ms 77904 KB Output is correct
4 Correct 371 ms 90464 KB Output is correct
5 Correct 421 ms 79480 KB Output is correct
6 Correct 551 ms 79476 KB Output is correct
7 Correct 552 ms 79568 KB Output is correct
8 Correct 349 ms 80200 KB Output is correct
9 Correct 334 ms 97996 KB Output is correct
10 Correct 410 ms 93404 KB Output is correct
11 Correct 303 ms 80972 KB Output is correct
12 Correct 589 ms 77904 KB Output is correct
13 Correct 289 ms 78276 KB Output is correct
14 Correct 514 ms 78308 KB Output is correct
15 Correct 589 ms 78680 KB Output is correct
16 Correct 596 ms 78536 KB Output is correct
17 Correct 747 ms 78672 KB Output is correct
18 Correct 34 ms 47956 KB Output is correct
19 Correct 28 ms 47980 KB Output is correct
20 Correct 28 ms 47896 KB Output is correct
21 Correct 28 ms 47796 KB Output is correct
22 Correct 28 ms 47964 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47964 KB Output is correct
2 Correct 302 ms 81232 KB Output is correct
3 Correct 631 ms 77904 KB Output is correct
4 Correct 371 ms 90464 KB Output is correct
5 Correct 421 ms 79480 KB Output is correct
6 Correct 551 ms 79476 KB Output is correct
7 Correct 552 ms 79568 KB Output is correct
8 Correct 349 ms 80200 KB Output is correct
9 Correct 334 ms 97996 KB Output is correct
10 Correct 410 ms 93404 KB Output is correct
11 Correct 303 ms 80972 KB Output is correct
12 Correct 589 ms 77904 KB Output is correct
13 Correct 289 ms 78276 KB Output is correct
14 Correct 514 ms 78308 KB Output is correct
15 Correct 589 ms 78680 KB Output is correct
16 Correct 596 ms 78536 KB Output is correct
17 Correct 747 ms 78672 KB Output is correct
18 Correct 34 ms 47956 KB Output is correct
19 Correct 28 ms 47980 KB Output is correct
20 Correct 28 ms 47896 KB Output is correct
21 Correct 28 ms 47796 KB Output is correct
22 Correct 28 ms 47964 KB Output is correct
23 Correct 36 ms 47836 KB Output is correct
24 Correct 353 ms 81376 KB Output is correct
25 Correct 774 ms 78160 KB Output is correct
26 Correct 391 ms 95828 KB Output is correct
27 Correct 463 ms 79600 KB Output is correct
28 Correct 642 ms 79392 KB Output is correct
29 Correct 632 ms 79432 KB Output is correct
30 Correct 411 ms 79840 KB Output is correct
31 Correct 350 ms 92748 KB Output is correct
32 Correct 422 ms 93524 KB Output is correct
33 Correct 331 ms 81412 KB Output is correct
34 Correct 811 ms 78204 KB Output is correct
35 Correct 28 ms 47964 KB Output is correct
36 Correct 28 ms 47812 KB Output is correct
37 Correct 28 ms 47884 KB Output is correct
38 Correct 28 ms 47964 KB Output is correct
39 Correct 28 ms 47952 KB Output is correct
40 Correct 28 ms 47972 KB Output is correct
41 Correct 28 ms 47956 KB Output is correct
42 Correct 28 ms 47968 KB Output is correct
43 Correct 28 ms 47796 KB Output is correct
44 Correct 29 ms 47880 KB Output is correct
45 Correct 28 ms 47964 KB Output is correct
46 Correct 29 ms 47964 KB Output is correct
47 Correct 28 ms 47964 KB Output is correct
48 Correct 29 ms 48156 KB Output is correct
49 Correct 28 ms 47956 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47800 KB Output is correct
2 Correct 463 ms 95284 KB Output is correct
3 Correct 1606 ms 90192 KB Output is correct
4 Correct 708 ms 91220 KB Output is correct
5 Correct 2711 ms 78080 KB Output is correct
6 Correct 2414 ms 77972 KB Output is correct
7 Correct 1185 ms 78264 KB Output is correct
8 Correct 321 ms 78500 KB Output is correct
9 Correct 490 ms 89988 KB Output is correct
10 Correct 1564 ms 93048 KB Output is correct
11 Correct 1175 ms 78372 KB Output is correct
12 Execution timed out 4067 ms 77932 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47824 KB Output is correct
2 Correct 481 ms 91916 KB Output is correct
3 Correct 1857 ms 86008 KB Output is correct
4 Correct 738 ms 89428 KB Output is correct
5 Correct 2751 ms 79616 KB Output is correct
6 Correct 2480 ms 79888 KB Output is correct
7 Correct 1497 ms 79440 KB Output is correct
8 Correct 352 ms 79684 KB Output is correct
9 Correct 486 ms 96856 KB Output is correct
10 Correct 1511 ms 94304 KB Output is correct
11 Correct 1346 ms 80964 KB Output is correct
12 Execution timed out 4035 ms 77692 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 48208 KB Output is correct
2 Correct 27 ms 47952 KB Output is correct
3 Correct 28 ms 47736 KB Output is correct
4 Correct 29 ms 47960 KB Output is correct
5 Correct 30 ms 47956 KB Output is correct
6 Correct 36 ms 47964 KB Output is correct
7 Correct 29 ms 47964 KB Output is correct
8 Correct 32 ms 48084 KB Output is correct
9 Correct 28 ms 47964 KB Output is correct
10 Correct 35 ms 47956 KB Output is correct
11 Correct 28 ms 48084 KB Output is correct
12 Correct 29 ms 47820 KB Output is correct
13 Correct 28 ms 47964 KB Output is correct
14 Correct 28 ms 47852 KB Output is correct
15 Correct 28 ms 47948 KB Output is correct
16 Correct 28 ms 47952 KB Output is correct
17 Correct 28 ms 47964 KB Output is correct
18 Correct 28 ms 48148 KB Output is correct
19 Correct 28 ms 47964 KB Output is correct
20 Correct 29 ms 47964 KB Output is correct
21 Correct 28 ms 47952 KB Output is correct
22 Correct 29 ms 47964 KB Output is correct
23 Correct 28 ms 47960 KB Output is correct
24 Correct 28 ms 47956 KB Output is correct
25 Correct 28 ms 47956 KB Output is correct
26 Correct 28 ms 47992 KB Output is correct
27 Correct 28 ms 47964 KB Output is correct
28 Correct 28 ms 47964 KB Output is correct
29 Correct 27 ms 47964 KB Output is correct
30 Correct 302 ms 81232 KB Output is correct
31 Correct 631 ms 77904 KB Output is correct
32 Correct 371 ms 90464 KB Output is correct
33 Correct 421 ms 79480 KB Output is correct
34 Correct 551 ms 79476 KB Output is correct
35 Correct 552 ms 79568 KB Output is correct
36 Correct 349 ms 80200 KB Output is correct
37 Correct 334 ms 97996 KB Output is correct
38 Correct 410 ms 93404 KB Output is correct
39 Correct 303 ms 80972 KB Output is correct
40 Correct 589 ms 77904 KB Output is correct
41 Correct 289 ms 78276 KB Output is correct
42 Correct 514 ms 78308 KB Output is correct
43 Correct 589 ms 78680 KB Output is correct
44 Correct 596 ms 78536 KB Output is correct
45 Correct 747 ms 78672 KB Output is correct
46 Correct 34 ms 47956 KB Output is correct
47 Correct 28 ms 47980 KB Output is correct
48 Correct 28 ms 47896 KB Output is correct
49 Correct 28 ms 47796 KB Output is correct
50 Correct 28 ms 47964 KB Output is correct
51 Correct 36 ms 47836 KB Output is correct
52 Correct 353 ms 81376 KB Output is correct
53 Correct 774 ms 78160 KB Output is correct
54 Correct 391 ms 95828 KB Output is correct
55 Correct 463 ms 79600 KB Output is correct
56 Correct 642 ms 79392 KB Output is correct
57 Correct 632 ms 79432 KB Output is correct
58 Correct 411 ms 79840 KB Output is correct
59 Correct 350 ms 92748 KB Output is correct
60 Correct 422 ms 93524 KB Output is correct
61 Correct 331 ms 81412 KB Output is correct
62 Correct 811 ms 78204 KB Output is correct
63 Correct 28 ms 47964 KB Output is correct
64 Correct 28 ms 47812 KB Output is correct
65 Correct 28 ms 47884 KB Output is correct
66 Correct 28 ms 47964 KB Output is correct
67 Correct 28 ms 47952 KB Output is correct
68 Correct 28 ms 47972 KB Output is correct
69 Correct 28 ms 47956 KB Output is correct
70 Correct 28 ms 47968 KB Output is correct
71 Correct 28 ms 47796 KB Output is correct
72 Correct 29 ms 47880 KB Output is correct
73 Correct 28 ms 47964 KB Output is correct
74 Correct 29 ms 47964 KB Output is correct
75 Correct 28 ms 47964 KB Output is correct
76 Correct 29 ms 48156 KB Output is correct
77 Correct 28 ms 47956 KB Output is correct
78 Correct 28 ms 47800 KB Output is correct
79 Correct 463 ms 95284 KB Output is correct
80 Correct 1606 ms 90192 KB Output is correct
81 Correct 708 ms 91220 KB Output is correct
82 Correct 2711 ms 78080 KB Output is correct
83 Correct 2414 ms 77972 KB Output is correct
84 Correct 1185 ms 78264 KB Output is correct
85 Correct 321 ms 78500 KB Output is correct
86 Correct 490 ms 89988 KB Output is correct
87 Correct 1564 ms 93048 KB Output is correct
88 Correct 1175 ms 78372 KB Output is correct
89 Execution timed out 4067 ms 77932 KB Time limit exceeded
90 Halted 0 ms 0 KB -