oj.uz

답안 #875791

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
875791 2023-11-20T13:50:29 Z danikoynov Sprinkler (JOI22_sprinkler) C++14
41 / 100
 4000 ms 97980 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)
    {
        if (lazy[root] == 1)
            return;
        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)
    {
        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)
    {
        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);
                }
            }
/**for (int i = 1; i <= n; i ++)
            cout << h[i] << " ";
        cout << endl;*/
        }

    }

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

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

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 47736 KB Output is correct
2 Correct 27 ms 47964 KB Output is correct
3 Correct 37 ms 47964 KB Output is correct
4 Correct 37 ms 47964 KB Output is correct
5 Correct 42 ms 47916 KB Output is correct
6 Correct 27 ms 47964 KB Output is correct
7 Correct 28 ms 47960 KB Output is correct
8 Correct 30 ms 47956 KB Output is correct
9 Correct 31 ms 47964 KB Output is correct
10 Correct 26 ms 47952 KB Output is correct
11 Correct 25 ms 47956 KB Output is correct
12 Correct 25 ms 47952 KB Output is correct
13 Correct 27 ms 47952 KB Output is correct
14 Correct 26 ms 48172 KB Output is correct
15 Correct 25 ms 47964 KB Output is correct
16 Correct 27 ms 47964 KB Output is correct
17 Correct 25 ms 47964 KB Output is correct
18 Correct 30 ms 47964 KB Output is correct
19 Correct 25 ms 47964 KB Output is correct
20 Correct 25 ms 47964 KB Output is correct
21 Correct 25 ms 47960 KB Output is correct
22 Correct 28 ms 47964 KB Output is correct
23 Correct 26 ms 47940 KB Output is correct
24 Correct 26 ms 47964 KB Output is correct
25 Correct 37 ms 47960 KB Output is correct
26 Correct 26 ms 47952 KB Output is correct
27 Correct 25 ms 47724 KB Output is correct
28 Correct 26 ms 47956 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 47964 KB Output is correct
2 Correct 313 ms 81372 KB Output is correct
3 Correct 766 ms 78080 KB Output is correct
4 Correct 423 ms 90212 KB Output is correct
5 Correct 578 ms 79560 KB Output is correct
6 Correct 606 ms 79504 KB Output is correct
7 Correct 674 ms 79632 KB Output is correct
8 Correct 476 ms 79824 KB Output is correct
9 Correct 433 ms 97980 KB Output is correct
10 Correct 518 ms 93460 KB Output is correct
11 Correct 355 ms 81020 KB Output is correct
12 Correct 672 ms 78060 KB Output is correct
13 Correct 329 ms 78404 KB Output is correct
14 Correct 596 ms 78232 KB Output is correct
15 Correct 678 ms 78372 KB Output is correct
16 Correct 636 ms 78364 KB Output is correct
17 Correct 800 ms 78800 KB Output is correct
18 Correct 25 ms 47764 KB Output is correct
19 Correct 26 ms 47960 KB Output is correct
20 Correct 29 ms 47860 KB Output is correct
21 Correct 31 ms 47964 KB Output is correct
22 Correct 29 ms 47980 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 47964 KB Output is correct
2 Correct 313 ms 81372 KB Output is correct
3 Correct 766 ms 78080 KB Output is correct
4 Correct 423 ms 90212 KB Output is correct
5 Correct 578 ms 79560 KB Output is correct
6 Correct 606 ms 79504 KB Output is correct
7 Correct 674 ms 79632 KB Output is correct
8 Correct 476 ms 79824 KB Output is correct
9 Correct 433 ms 97980 KB Output is correct
10 Correct 518 ms 93460 KB Output is correct
11 Correct 355 ms 81020 KB Output is correct
12 Correct 672 ms 78060 KB Output is correct
13 Correct 329 ms 78404 KB Output is correct
14 Correct 596 ms 78232 KB Output is correct
15 Correct 678 ms 78372 KB Output is correct
16 Correct 636 ms 78364 KB Output is correct
17 Correct 800 ms 78800 KB Output is correct
18 Correct 25 ms 47764 KB Output is correct
19 Correct 26 ms 47960 KB Output is correct
20 Correct 29 ms 47860 KB Output is correct
21 Correct 31 ms 47964 KB Output is correct
22 Correct 29 ms 47980 KB Output is correct
23 Correct 29 ms 47964 KB Output is correct
24 Correct 387 ms 81160 KB Output is correct
25 Correct 1079 ms 77832 KB Output is correct
26 Correct 501 ms 95824 KB Output is correct
27 Correct 523 ms 79544 KB Output is correct
28 Correct 801 ms 79352 KB Output is correct
29 Correct 768 ms 79360 KB Output is correct
30 Correct 427 ms 80200 KB Output is correct
31 Correct 416 ms 92636 KB Output is correct
32 Correct 476 ms 93500 KB Output is correct
33 Correct 480 ms 81148 KB Output is correct
34 Correct 1075 ms 78012 KB Output is correct
35 Correct 26 ms 47744 KB Output is correct
36 Correct 25 ms 47952 KB Output is correct
37 Correct 26 ms 47960 KB Output is correct
38 Correct 30 ms 48216 KB Output is correct
39 Correct 25 ms 47884 KB Output is correct
40 Correct 31 ms 47956 KB Output is correct
41 Correct 26 ms 47956 KB Output is correct
42 Correct 27 ms 48040 KB Output is correct
43 Correct 25 ms 47960 KB Output is correct
44 Correct 25 ms 47964 KB Output is correct
45 Correct 26 ms 47964 KB Output is correct
46 Correct 26 ms 47956 KB Output is correct
47 Correct 26 ms 47800 KB Output is correct
48 Correct 25 ms 47960 KB Output is correct
49 Correct 25 ms 47964 KB Output is correct

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 47952 KB Output is correct
2 Correct 536 ms 95132 KB Output is correct
3 Correct 1974 ms 90052 KB Output is correct
4 Correct 935 ms 91248 KB Output is correct
5 Correct 3605 ms 78392 KB Output is correct
6 Correct 2712 ms 78080 KB Output is correct
7 Correct 1400 ms 78188 KB Output is correct
8 Correct 283 ms 78660 KB Output is correct
9 Correct 585 ms 89892 KB Output is correct
10 Correct 1967 ms 93136 KB Output is correct
11 Correct 1637 ms 78504 KB Output is correct
12 Execution timed out 4094 ms 77696 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 47972 KB Output is correct
2 Correct 625 ms 91784 KB Output is correct
3 Correct 2433 ms 86184 KB Output is correct
4 Correct 1024 ms 89248 KB Output is correct
5 Execution timed out 4049 ms 79524 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 47736 KB Output is correct
2 Correct 27 ms 47964 KB Output is correct
3 Correct 37 ms 47964 KB Output is correct
4 Correct 37 ms 47964 KB Output is correct
5 Correct 42 ms 47916 KB Output is correct
6 Correct 27 ms 47964 KB Output is correct
7 Correct 28 ms 47960 KB Output is correct
8 Correct 30 ms 47956 KB Output is correct
9 Correct 31 ms 47964 KB Output is correct
10 Correct 26 ms 47952 KB Output is correct
11 Correct 25 ms 47956 KB Output is correct
12 Correct 25 ms 47952 KB Output is correct
13 Correct 27 ms 47952 KB Output is correct
14 Correct 26 ms 48172 KB Output is correct
15 Correct 25 ms 47964 KB Output is correct
16 Correct 27 ms 47964 KB Output is correct
17 Correct 25 ms 47964 KB Output is correct
18 Correct 30 ms 47964 KB Output is correct
19 Correct 25 ms 47964 KB Output is correct
20 Correct 25 ms 47964 KB Output is correct
21 Correct 25 ms 47960 KB Output is correct
22 Correct 28 ms 47964 KB Output is correct
23 Correct 26 ms 47940 KB Output is correct
24 Correct 26 ms 47964 KB Output is correct
25 Correct 37 ms 47960 KB Output is correct
26 Correct 26 ms 47952 KB Output is correct
27 Correct 25 ms 47724 KB Output is correct
28 Correct 26 ms 47956 KB Output is correct
29 Correct 25 ms 47964 KB Output is correct
30 Correct 313 ms 81372 KB Output is correct
31 Correct 766 ms 78080 KB Output is correct
32 Correct 423 ms 90212 KB Output is correct
33 Correct 578 ms 79560 KB Output is correct
34 Correct 606 ms 79504 KB Output is correct
35 Correct 674 ms 79632 KB Output is correct
36 Correct 476 ms 79824 KB Output is correct
37 Correct 433 ms 97980 KB Output is correct
38 Correct 518 ms 93460 KB Output is correct
39 Correct 355 ms 81020 KB Output is correct
40 Correct 672 ms 78060 KB Output is correct
41 Correct 329 ms 78404 KB Output is correct
42 Correct 596 ms 78232 KB Output is correct
43 Correct 678 ms 78372 KB Output is correct
44 Correct 636 ms 78364 KB Output is correct
45 Correct 800 ms 78800 KB Output is correct
46 Correct 25 ms 47764 KB Output is correct
47 Correct 26 ms 47960 KB Output is correct
48 Correct 29 ms 47860 KB Output is correct
49 Correct 31 ms 47964 KB Output is correct
50 Correct 29 ms 47980 KB Output is correct
51 Correct 29 ms 47964 KB Output is correct
52 Correct 387 ms 81160 KB Output is correct
53 Correct 1079 ms 77832 KB Output is correct
54 Correct 501 ms 95824 KB Output is correct
55 Correct 523 ms 79544 KB Output is correct
56 Correct 801 ms 79352 KB Output is correct
57 Correct 768 ms 79360 KB Output is correct
58 Correct 427 ms 80200 KB Output is correct
59 Correct 416 ms 92636 KB Output is correct
60 Correct 476 ms 93500 KB Output is correct
61 Correct 480 ms 81148 KB Output is correct
62 Correct 1075 ms 78012 KB Output is correct
63 Correct 26 ms 47744 KB Output is correct
64 Correct 25 ms 47952 KB Output is correct
65 Correct 26 ms 47960 KB Output is correct
66 Correct 30 ms 48216 KB Output is correct
67 Correct 25 ms 47884 KB Output is correct
68 Correct 31 ms 47956 KB Output is correct
69 Correct 26 ms 47956 KB Output is correct
70 Correct 27 ms 48040 KB Output is correct
71 Correct 25 ms 47960 KB Output is correct
72 Correct 25 ms 47964 KB Output is correct
73 Correct 26 ms 47964 KB Output is correct
74 Correct 26 ms 47956 KB Output is correct
75 Correct 26 ms 47800 KB Output is correct
76 Correct 25 ms 47960 KB Output is correct
77 Correct 25 ms 47964 KB Output is correct
78 Correct 28 ms 47952 KB Output is correct
79 Correct 536 ms 95132 KB Output is correct
80 Correct 1974 ms 90052 KB Output is correct
81 Correct 935 ms 91248 KB Output is correct
82 Correct 3605 ms 78392 KB Output is correct
83 Correct 2712 ms 78080 KB Output is correct
84 Correct 1400 ms 78188 KB Output is correct
85 Correct 283 ms 78660 KB Output is correct
86 Correct 585 ms 89892 KB Output is correct
87 Correct 1967 ms 93136 KB Output is correct
88 Correct 1637 ms 78504 KB Output is correct
89 Execution timed out 4094 ms 77696 KB Time limit exceeded
90 Halted 0 ms 0 KB -