oj.uz

Submission #651206

# Submission time Handle Problem Language Result Execution time Memory
651206 2022-10-18T02:43:39 Z becaido Birthday gift (IZhO18_treearray) C++17
56 / 100
 387 ms 1224 KB 
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=I;x++)
#define pb emplace_back
#define F first
#define S second

#define lpos pos*2
#define rpos pos*2+1

const int SIZE = 4005;
const int H = __lg (SIZE) + 2;

int n, m, q, cnt;
int h[SIZE], in[SIZE], out[SIZE], dfsp[SIZE];
int L[SIZE][H + 1], R[SIZE][H + 1], lc[4 * SIZE];
vector<int> adj[SIZE];
int a[SIZE];

int chmin (int i, int j) {
    return h[i] < h[j] ? i : j;
}

int lca (int i, int j) {
    int l = in[i], r = in[j];
    if (l > r) swap (l, r);
    int t = __lg (r - l + 1);
    return chmin (L[l][t], R[r][t]);
}

void dfs (int pos, int fa) {
    dfsp[++cnt] = pos;
    in[pos] = out[pos] = cnt;
    for (int np : adj[pos]) if (np != fa) {
        h[np] = h[pos] + 1;
        dfs (np, pos);
        dfsp[++cnt] = pos;
        out[pos] = cnt;
    }
}

void Pull (int pos, int l, int r) {
    lc[pos] = lca (lc[lpos], lc[rpos]);
}

void build (int pos, int l, int r) {
    if (l == r) {
        lc[pos] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build (lpos, l, mid);
    build (rpos, mid + 1, r);
    Pull (pos, l, r);
}

void upd (int pos, int l, int r, int p, int x) {
    if (l == r) {
        lc[pos] = x;
        return;
    }
    int mid = (l + r) / 2;
    if (p <= mid) upd (lpos, l, mid, p, x);
    else upd (rpos, mid + 1, r, p, x);
    Pull (pos, l, r);
}

int que (int pos, int l, int r, int L, int R) {
    if (l > r) return 0;
    if (l == L && r == R) return lc[pos];
    int mid = (L + R) / 2;
    if (r <= mid) return que (lpos, l, r, L, mid);
    else if (l > mid) return que (rpos, l, r, mid + 1, R);
    return lca (que (lpos, l, mid, L, mid), que (rpos, mid + 1, r, mid + 1, R));
}

pair<int, int> cal (int l, int r, int v) {
    for (int i = l, j = l - 1; i <= r; i++) {
        j = max (j, i - 1);
        while (j < r) {
            j++;
            int p = que (1, i, j, 1, m);
            //cout << "i = " << i << ", j = " << j << ", p = " << p << '\n';
            if (p == v) return {i, j};
            if (h[p] <= h[v]) {j--; break;}
            if (in[p] < in[v] || in[p] > out[v]) {j--; break;}
        }
    }
    return {-1, -1};
}

void solve() {
    cin >> n >> m >> q;
    FOR (i, 2, n) {
        int a, b;
        cin >> a >> b;
        adj[a].pb (b);
        adj[b].pb (a);
    }
    h[1] = 1;
    dfs (1, 1);
    FOR (i, 1, cnt) L[i][0] = R[i][0] = dfsp[i];
    for (int t = 1; (1 << t) < cnt; t++) {
        int len = 1 << t, half = len >> 1;
        FOR (i, 1, cnt - len + 1) L[i][t] = chmin (L[i][t - 1], L[i + half][t - 1]);
        for (int i = cnt; i >= len; i--) R[i][t] = chmin (R[i][t - 1], R[i - half][t - 1]);
    }
    FOR (i, 1, m) cin >> a[i];
    build (1, 1, m);
    while (q--) {
        int ty, l, r, p, v;
        cin >> ty;
        if (ty == 1) {
            cin >> p >> v;
            upd (1, 1, m, p, v);
            a[p] = v;
        } else {
            cin >> l >> r >> v;
            auto [x, y] = cal (l, r, v);
            cout << x << ' ' << y << '\n';
        }
    }
}

int main() {
    Waimai;
    solve();
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n=5
2 Correct 1 ms 468 KB n=100
3 Correct 1 ms 468 KB n=100
4 Correct 1 ms 468 KB n=100
5 Correct 1 ms 468 KB n=100
6 Correct 1 ms 424 KB n=100
7 Correct 1 ms 468 KB n=100
8 Correct 1 ms 468 KB n=100
9 Correct 1 ms 468 KB n=100
10 Correct 1 ms 424 KB n=100
11 Correct 1 ms 424 KB n=100
12 Correct 1 ms 596 KB n=100
13 Correct 1 ms 468 KB n=100
14 Correct 1 ms 468 KB n=100
15 Correct 1 ms 468 KB n=100
16 Correct 1 ms 468 KB n=100
17 Correct 1 ms 468 KB n=100
18 Correct 1 ms 468 KB n=100
19 Correct 1 ms 420 KB n=100
20 Correct 1 ms 424 KB n=100
21 Correct 1 ms 424 KB n=100
22 Correct 1 ms 420 KB n=100
23 Correct 1 ms 432 KB n=100
24 Correct 1 ms 468 KB n=100
25 Correct 1 ms 468 KB n=100
26 Correct 1 ms 424 KB n=12
27 Correct 1 ms 468 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n=5
2 Correct 1 ms 468 KB n=100
3 Correct 1 ms 468 KB n=100
4 Correct 1 ms 468 KB n=100
5 Correct 1 ms 468 KB n=100
6 Correct 1 ms 424 KB n=100
7 Correct 1 ms 468 KB n=100
8 Correct 1 ms 468 KB n=100
9 Correct 1 ms 468 KB n=100
10 Correct 1 ms 424 KB n=100
11 Correct 1 ms 424 KB n=100
12 Correct 1 ms 596 KB n=100
13 Correct 1 ms 468 KB n=100
14 Correct 1 ms 468 KB n=100
15 Correct 1 ms 468 KB n=100
16 Correct 1 ms 468 KB n=100
17 Correct 1 ms 468 KB n=100
18 Correct 1 ms 468 KB n=100
19 Correct 1 ms 420 KB n=100
20 Correct 1 ms 424 KB n=100
21 Correct 1 ms 424 KB n=100
22 Correct 1 ms 420 KB n=100
23 Correct 1 ms 432 KB n=100
24 Correct 1 ms 468 KB n=100
25 Correct 1 ms 468 KB n=100
26 Correct 1 ms 424 KB n=12
27 Correct 1 ms 468 KB n=100
28 Correct 2 ms 556 KB n=500
29 Correct 3 ms 596 KB n=500
30 Correct 4 ms 596 KB n=500
31 Correct 3 ms 596 KB n=500
32 Correct 1 ms 596 KB n=500
33 Correct 3 ms 596 KB n=500
34 Correct 1 ms 596 KB n=500
35 Correct 3 ms 596 KB n=500
36 Correct 9 ms 596 KB n=500
37 Correct 7 ms 596 KB n=500
38 Correct 6 ms 604 KB n=500
39 Correct 4 ms 596 KB n=500
40 Correct 4 ms 596 KB n=500
41 Correct 4 ms 596 KB n=500
42 Correct 4 ms 596 KB n=500
43 Correct 5 ms 724 KB n=500
44 Correct 4 ms 596 KB n=500
45 Correct 1 ms 596 KB n=500
46 Correct 4 ms 596 KB n=500
47 Correct 3 ms 564 KB n=500
48 Correct 1 ms 596 KB n=500
49 Correct 3 ms 596 KB n=500
50 Correct 2 ms 596 KB n=500
51 Correct 6 ms 608 KB n=500
52 Correct 4 ms 596 KB n=500
53 Correct 3 ms 596 KB n=500
54 Correct 5 ms 596 KB n=500
55 Correct 1 ms 468 KB n=278
56 Correct 15 ms 596 KB n=500
57 Correct 15 ms 596 KB n=500
58 Correct 3 ms 596 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n=5
2 Correct 1 ms 468 KB n=100
3 Correct 1 ms 468 KB n=100
4 Correct 1 ms 468 KB n=100
5 Correct 1 ms 468 KB n=100
6 Correct 1 ms 424 KB n=100
7 Correct 1 ms 468 KB n=100
8 Correct 1 ms 468 KB n=100
9 Correct 1 ms 468 KB n=100
10 Correct 1 ms 424 KB n=100
11 Correct 1 ms 424 KB n=100
12 Correct 1 ms 596 KB n=100
13 Correct 1 ms 468 KB n=100
14 Correct 1 ms 468 KB n=100
15 Correct 1 ms 468 KB n=100
16 Correct 1 ms 468 KB n=100
17 Correct 1 ms 468 KB n=100
18 Correct 1 ms 468 KB n=100
19 Correct 1 ms 420 KB n=100
20 Correct 1 ms 424 KB n=100
21 Correct 1 ms 424 KB n=100
22 Correct 1 ms 420 KB n=100
23 Correct 1 ms 432 KB n=100
24 Correct 1 ms 468 KB n=100
25 Correct 1 ms 468 KB n=100
26 Correct 1 ms 424 KB n=12
27 Correct 1 ms 468 KB n=100
28 Correct 2 ms 556 KB n=500
29 Correct 3 ms 596 KB n=500
30 Correct 4 ms 596 KB n=500
31 Correct 3 ms 596 KB n=500
32 Correct 1 ms 596 KB n=500
33 Correct 3 ms 596 KB n=500
34 Correct 1 ms 596 KB n=500
35 Correct 3 ms 596 KB n=500
36 Correct 9 ms 596 KB n=500
37 Correct 7 ms 596 KB n=500
38 Correct 6 ms 604 KB n=500
39 Correct 4 ms 596 KB n=500
40 Correct 4 ms 596 KB n=500
41 Correct 4 ms 596 KB n=500
42 Correct 4 ms 596 KB n=500
43 Correct 5 ms 724 KB n=500
44 Correct 4 ms 596 KB n=500
45 Correct 1 ms 596 KB n=500
46 Correct 4 ms 596 KB n=500
47 Correct 3 ms 564 KB n=500
48 Correct 1 ms 596 KB n=500
49 Correct 3 ms 596 KB n=500
50 Correct 2 ms 596 KB n=500
51 Correct 6 ms 608 KB n=500
52 Correct 4 ms 596 KB n=500
53 Correct 3 ms 596 KB n=500
54 Correct 5 ms 596 KB n=500
55 Correct 1 ms 468 KB n=278
56 Correct 15 ms 596 KB n=500
57 Correct 15 ms 596 KB n=500
58 Correct 3 ms 596 KB n=500
59 Correct 3 ms 1028 KB n=2000
60 Correct 46 ms 1028 KB n=2000
61 Correct 40 ms 980 KB n=2000
62 Correct 28 ms 980 KB n=2000
63 Correct 3 ms 980 KB n=2000
64 Correct 35 ms 1072 KB n=2000
65 Correct 3 ms 980 KB n=2000
66 Correct 59 ms 1100 KB n=2000
67 Correct 4 ms 980 KB n=2000
68 Correct 38 ms 1088 KB n=2000
69 Correct 134 ms 1048 KB n=2000
70 Correct 156 ms 1056 KB n=2000
71 Correct 137 ms 1048 KB n=2000
72 Correct 75 ms 1040 KB n=2000
73 Correct 77 ms 1052 KB n=2000
74 Correct 3 ms 980 KB n=1844
75 Correct 79 ms 1052 KB n=2000
76 Correct 74 ms 1056 KB n=2000
77 Correct 73 ms 980 KB n=2000
78 Correct 81 ms 948 KB n=2000
79 Correct 4 ms 948 KB n=2000
80 Correct 47 ms 980 KB n=2000
81 Correct 34 ms 1064 KB n=2000
82 Correct 3 ms 948 KB n=2000
83 Correct 35 ms 1096 KB n=2000
84 Correct 29 ms 980 KB n=2000
85 Correct 54 ms 1072 KB n=2000
86 Correct 53 ms 1076 KB n=2000
87 Correct 30 ms 1064 KB n=2000
88 Correct 367 ms 1224 KB n=2000
89 Correct 387 ms 1104 KB n=2000
90 Correct 86 ms 1048 KB n=2000
91 Correct 83 ms 992 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB n=5
2 Correct 1 ms 468 KB n=100
3 Correct 1 ms 468 KB n=100
4 Correct 1 ms 468 KB n=100
5 Correct 1 ms 468 KB n=100
6 Correct 1 ms 424 KB n=100
7 Correct 1 ms 468 KB n=100
8 Correct 1 ms 468 KB n=100
9 Correct 1 ms 468 KB n=100
10 Correct 1 ms 424 KB n=100
11 Correct 1 ms 424 KB n=100
12 Correct 1 ms 596 KB n=100
13 Correct 1 ms 468 KB n=100
14 Correct 1 ms 468 KB n=100
15 Correct 1 ms 468 KB n=100
16 Correct 1 ms 468 KB n=100
17 Correct 1 ms 468 KB n=100
18 Correct 1 ms 468 KB n=100
19 Correct 1 ms 420 KB n=100
20 Correct 1 ms 424 KB n=100
21 Correct 1 ms 424 KB n=100
22 Correct 1 ms 420 KB n=100
23 Correct 1 ms 432 KB n=100
24 Correct 1 ms 468 KB n=100
25 Correct 1 ms 468 KB n=100
26 Correct 1 ms 424 KB n=12
27 Correct 1 ms 468 KB n=100
28 Correct 2 ms 556 KB n=500
29 Correct 3 ms 596 KB n=500
30 Correct 4 ms 596 KB n=500
31 Correct 3 ms 596 KB n=500
32 Correct 1 ms 596 KB n=500
33 Correct 3 ms 596 KB n=500
34 Correct 1 ms 596 KB n=500
35 Correct 3 ms 596 KB n=500
36 Correct 9 ms 596 KB n=500
37 Correct 7 ms 596 KB n=500
38 Correct 6 ms 604 KB n=500
39 Correct 4 ms 596 KB n=500
40 Correct 4 ms 596 KB n=500
41 Correct 4 ms 596 KB n=500
42 Correct 4 ms 596 KB n=500
43 Correct 5 ms 724 KB n=500
44 Correct 4 ms 596 KB n=500
45 Correct 1 ms 596 KB n=500
46 Correct 4 ms 596 KB n=500
47 Correct 3 ms 564 KB n=500
48 Correct 1 ms 596 KB n=500
49 Correct 3 ms 596 KB n=500
50 Correct 2 ms 596 KB n=500
51 Correct 6 ms 608 KB n=500
52 Correct 4 ms 596 KB n=500
53 Correct 3 ms 596 KB n=500
54 Correct 5 ms 596 KB n=500
55 Correct 1 ms 468 KB n=278
56 Correct 15 ms 596 KB n=500
57 Correct 15 ms 596 KB n=500
58 Correct 3 ms 596 KB n=500
59 Correct 3 ms 1028 KB n=2000
60 Correct 46 ms 1028 KB n=2000
61 Correct 40 ms 980 KB n=2000
62 Correct 28 ms 980 KB n=2000
63 Correct 3 ms 980 KB n=2000
64 Correct 35 ms 1072 KB n=2000
65 Correct 3 ms 980 KB n=2000
66 Correct 59 ms 1100 KB n=2000
67 Correct 4 ms 980 KB n=2000
68 Correct 38 ms 1088 KB n=2000
69 Correct 134 ms 1048 KB n=2000
70 Correct 156 ms 1056 KB n=2000
71 Correct 137 ms 1048 KB n=2000
72 Correct 75 ms 1040 KB n=2000
73 Correct 77 ms 1052 KB n=2000
74 Correct 3 ms 980 KB n=1844
75 Correct 79 ms 1052 KB n=2000
76 Correct 74 ms 1056 KB n=2000
77 Correct 73 ms 980 KB n=2000
78 Correct 81 ms 948 KB n=2000
79 Correct 4 ms 948 KB n=2000
80 Correct 47 ms 980 KB n=2000
81 Correct 34 ms 1064 KB n=2000
82 Correct 3 ms 948 KB n=2000
83 Correct 35 ms 1096 KB n=2000
84 Correct 29 ms 980 KB n=2000
85 Correct 54 ms 1072 KB n=2000
86 Correct 53 ms 1076 KB n=2000
87 Correct 30 ms 1064 KB n=2000
88 Correct 367 ms 1224 KB n=2000
89 Correct 387 ms 1104 KB n=2000
90 Correct 86 ms 1048 KB n=2000
91 Correct 83 ms 992 KB n=2000
92 Runtime error 1 ms 688 KB Execution killed with signal 11
93 Halted 0 ms 0 KB -