oj.uz

Submission #893720

# Submission time Handle Problem Language Result Execution time Memory
893720 2023-12-27T10:18:29 Z vjudge1 Birthday gift (IZhO18_treearray) C++17
56 / 100
 4000 ms 36180 KB 
// 以上帝的名义
// 候选硕士
#include <bits/stdc++.h>

#ifdef local
#include "algo/debug.h"
#else
#define dbg(x...) 0
#endif

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define Node int
#define at(i) find_by_order(i)
#define which(x) order_of_key(x)
#define SET tree<Node, null_type,less<Node>, rb_tree_tag,tree_order_statistics_node_update>

using namespace std ;
using ll = long long ;
using ld = long double ;

const int N = 2e5 + 5 ;

int n , m , q, a[N], p[N] ;
vector<int> g[N] ;

int tin[N], tout[N], timer , up[N][20] ;

void dfs(int v, int p) {
    tin[v] = ++timer ;
    up[v][0] = p ;
    for (int i = 1 ; i < 20 ; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1] ;
    }
    for (auto to : g[v]) {
        if (to != p) {
            dfs(to, v) ;
        }
    }
    tout[v] = ++timer ;
}

bool is(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v] ;
}

bool upper(int u, int v) {
    return tin[u] < tin[v] && tout[u] > tout[v] ;
}

int lca(int u, int v) {
    if (!u) return v ;
    if (!v) return u ;
    if (is(u, v)) return u ;
    if (is(v, u)) return v ;
    for (int i = 19 ; ~i ; i--) {
        if (!is(up[u][i], v)) {
            u = up[u][i] ;
        }
    }
    return up[u][0] ;
}

int t[N * 4] ;

void modify(int i, int x, int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = x ;
    } else {
        int tm = (tl + tr) / 2 ;
        if (i <= tm) {
            modify(i, x, v * 2, tl, tm) ;
        } else {
            modify(i, x, v * 2 + 1, tm + 1, tr) ;
        }
        t[v] = lca(t[v * 2], t[v * 2 + 1]) ;
    }
}

int get(int l, int r, int v, int tl, int tr) {
    if (l > tr || r < tl) return 0 ;
    if (l <= tl && tr <= r) return t[v] ;
    int tm = (tl + tr) / 2 ;
    return lca(get(l, r,v * 2, tl, tm), get(l, r,v * 2 + 1 ,tm + 1, tr)) ;
}

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

int32_t main() {
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;
    cin >> n >> m >> q ;
    for (int i = 1 ; i < n ; i++) {
        int u , v ; cin >> u >> v;
        g[u].push_back(v) ;
        g[v].push_back(u) ;
    }
    for (int i = 1 ; i <= m ; i++) {
        cin >> a[i] ;
        p[a[i]] = i ;
    }
    dfs(1, 1) ;
    for (int i = 1 ; i <= m ; i++) {
        modify(i, a[i], 1, 1, m) ;
    }
//    dbg(get(1, 2, 1, 1, m)) ;
    for (int i = 0 ; i < q ; i++) {
        int cmd ; cin >> cmd ;
        if (cmd == 1) {
            int pos, v; cin >> pos >> v ;
            modify(pos, v, 1, 1, m) ;
        } else {
            int l, r, v; cin >> l >> r >> v ;
            int _l = -1, _r = -1 ;
            for (int j = l ; j <= min(r , l + 1000) ; j++) {
                int L = j, R = r ;
                while (L < R) {
                    ll mid = (L + R + 1) / 2 ;
                    ll c = get(j, mid, 1, 1, m) ;
                    if (upper(c, v)) R = mid - 1 ;
                    else L = mid ;
                }
//                dbg(j, L, get(j, L, 1, 1, m)) ;
                if (get(j, L, 1, 1, m) == v) {
                    _l = j , _r = L ;
                    break ;
                }
            }
            for (int j = max(l, r - 1000) ; j <= r ; j++) {
                int L = j, R = r ;
                while (L < R) {
                    ll mid = (L + R + 1) / 2 ;
                    ll c = get(j, mid, 1, 1, m) ;
                    if (upper(c, v)) R = mid - 1 ;
                    else L = mid ;
                }
//                dbg(j, L, get(j, L, 1, 1, m)) ;
                if (get(j, L, 1, 1, m) == v) {
                    _l = j , _r = L ;
                    break ;
                }
            }
            cout << _l << ' ' << _r << "\n" ;
        }
    }
    return 0 ;
}

// 希望白银

Compilation message

treearray.cpp:90: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   90 | #pragma GCC optimization ("O3")
      | 
treearray.cpp:91: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   91 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB n=5
2 Correct 3 ms 8796 KB n=100
3 Correct 3 ms 8796 KB n=100
4 Correct 2 ms 8796 KB n=100
5 Correct 2 ms 8796 KB n=100
6 Correct 10 ms 8796 KB n=100
7 Correct 9 ms 8892 KB n=100
8 Correct 5 ms 8796 KB n=100
9 Correct 4 ms 8796 KB n=100
10 Correct 6 ms 8792 KB n=100
11 Correct 5 ms 8796 KB n=100
12 Correct 2 ms 8796 KB n=100
13 Correct 2 ms 8796 KB n=100
14 Correct 2 ms 8796 KB n=100
15 Correct 2 ms 8792 KB n=100
16 Correct 3 ms 8796 KB n=100
17 Correct 3 ms 8792 KB n=100
18 Correct 2 ms 8796 KB n=100
19 Correct 2 ms 8792 KB n=100
20 Correct 3 ms 8796 KB n=100
21 Correct 2 ms 8792 KB n=100
22 Correct 2 ms 8796 KB n=100
23 Correct 6 ms 8792 KB n=100
24 Correct 5 ms 8792 KB n=100
25 Correct 2 ms 8796 KB n=100
26 Correct 2 ms 8796 KB n=12
27 Correct 6 ms 8920 KB n=100
28 Correct 3 ms 8796 KB n=500
29 Correct 46 ms 8796 KB n=500
30 Correct 37 ms 8796 KB n=500
31 Correct 41 ms 8796 KB n=500
32 Correct 4 ms 8796 KB n=500
33 Correct 38 ms 8792 KB n=500
34 Correct 2 ms 8796 KB n=500
35 Correct 43 ms 8792 KB n=500
36 Correct 294 ms 8928 KB n=500
37 Correct 292 ms 8792 KB n=500
38 Correct 285 ms 8932 KB n=500
39 Correct 98 ms 8932 KB n=500
40 Correct 104 ms 8932 KB n=500
41 Correct 93 ms 8928 KB n=500
42 Correct 150 ms 8792 KB n=500
43 Correct 151 ms 8792 KB n=500
44 Correct 147 ms 8796 KB n=500
45 Correct 3 ms 8792 KB n=500
46 Correct 42 ms 8796 KB n=500
47 Correct 39 ms 8796 KB n=500
48 Correct 2 ms 8792 KB n=500
49 Correct 36 ms 8968 KB n=500
50 Correct 60 ms 8796 KB n=500
51 Correct 64 ms 8796 KB n=500
52 Correct 78 ms 8944 KB n=500
53 Correct 78 ms 8796 KB n=500
54 Correct 50 ms 8948 KB n=500
55 Correct 11 ms 8960 KB n=278
56 Correct 241 ms 8952 KB n=500
57 Correct 253 ms 8796 KB n=500
58 Correct 193 ms 8932 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB n=5
2 Correct 3 ms 8796 KB n=100
3 Correct 3 ms 8796 KB n=100
4 Correct 2 ms 8796 KB n=100
5 Correct 2 ms 8796 KB n=100
6 Correct 10 ms 8796 KB n=100
7 Correct 9 ms 8892 KB n=100
8 Correct 5 ms 8796 KB n=100
9 Correct 4 ms 8796 KB n=100
10 Correct 6 ms 8792 KB n=100
11 Correct 5 ms 8796 KB n=100
12 Correct 2 ms 8796 KB n=100
13 Correct 2 ms 8796 KB n=100
14 Correct 2 ms 8796 KB n=100
15 Correct 2 ms 8792 KB n=100
16 Correct 3 ms 8796 KB n=100
17 Correct 3 ms 8792 KB n=100
18 Correct 2 ms 8796 KB n=100
19 Correct 2 ms 8792 KB n=100
20 Correct 3 ms 8796 KB n=100
21 Correct 2 ms 8792 KB n=100
22 Correct 2 ms 8796 KB n=100
23 Correct 6 ms 8792 KB n=100
24 Correct 5 ms 8792 KB n=100
25 Correct 2 ms 8796 KB n=100
26 Correct 2 ms 8796 KB n=12
27 Correct 6 ms 8920 KB n=100
28 Correct 3 ms 8796 KB n=500
29 Correct 46 ms 8796 KB n=500
30 Correct 37 ms 8796 KB n=500
31 Correct 41 ms 8796 KB n=500
32 Correct 4 ms 8796 KB n=500
33 Correct 38 ms 8792 KB n=500
34 Correct 2 ms 8796 KB n=500
35 Correct 43 ms 8792 KB n=500
36 Correct 294 ms 8928 KB n=500
37 Correct 292 ms 8792 KB n=500
38 Correct 285 ms 8932 KB n=500
39 Correct 98 ms 8932 KB n=500
40 Correct 104 ms 8932 KB n=500
41 Correct 93 ms 8928 KB n=500
42 Correct 150 ms 8792 KB n=500
43 Correct 151 ms 8792 KB n=500
44 Correct 147 ms 8796 KB n=500
45 Correct 3 ms 8792 KB n=500
46 Correct 42 ms 8796 KB n=500
47 Correct 39 ms 8796 KB n=500
48 Correct 2 ms 8792 KB n=500
49 Correct 36 ms 8968 KB n=500
50 Correct 60 ms 8796 KB n=500
51 Correct 64 ms 8796 KB n=500
52 Correct 78 ms 8944 KB n=500
53 Correct 78 ms 8796 KB n=500
54 Correct 50 ms 8948 KB n=500
55 Correct 11 ms 8960 KB n=278
56 Correct 241 ms 8952 KB n=500
57 Correct 253 ms 8796 KB n=500
58 Correct 193 ms 8932 KB n=500
59 Correct 13 ms 8796 KB n=2000
60 Correct 934 ms 9084 KB n=2000
61 Correct 879 ms 9300 KB n=2000
62 Correct 613 ms 8796 KB n=2000
63 Correct 19 ms 9048 KB n=2000
64 Correct 831 ms 9028 KB n=2000
65 Correct 8 ms 9048 KB n=2000
66 Correct 999 ms 9068 KB n=2000
67 Correct 53 ms 8792 KB n=2000
68 Correct 866 ms 9052 KB n=2000
69 Correct 3345 ms 9008 KB n=2000
70 Correct 3344 ms 9248 KB n=2000
71 Correct 3382 ms 9020 KB n=2000
72 Correct 2417 ms 9004 KB n=2000
73 Correct 2378 ms 9256 KB n=2000
74 Correct 7 ms 8796 KB n=1844
75 Correct 2494 ms 9016 KB n=2000
76 Correct 1717 ms 9044 KB n=2000
77 Correct 1705 ms 9180 KB n=2000
78 Correct 1837 ms 9252 KB n=2000
79 Correct 7 ms 8796 KB n=2000
80 Correct 808 ms 9072 KB n=2000
81 Correct 731 ms 9044 KB n=2000
82 Correct 8 ms 8796 KB n=2000
83 Correct 808 ms 9056 KB n=2000
84 Correct 1346 ms 9008 KB n=2000
85 Correct 1362 ms 9028 KB n=2000
86 Correct 1424 ms 9048 KB n=2000
87 Correct 1408 ms 9048 KB n=2000
88 Correct 3347 ms 9088 KB n=2000
89 Correct 3344 ms 9092 KB n=2000
90 Correct 996 ms 9300 KB n=2000
91 Correct 3772 ms 9008 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB n=5
2 Correct 3 ms 8796 KB n=100
3 Correct 3 ms 8796 KB n=100
4 Correct 2 ms 8796 KB n=100
5 Correct 2 ms 8796 KB n=100
6 Correct 10 ms 8796 KB n=100
7 Correct 9 ms 8892 KB n=100
8 Correct 5 ms 8796 KB n=100
9 Correct 4 ms 8796 KB n=100
10 Correct 6 ms 8792 KB n=100
11 Correct 5 ms 8796 KB n=100
12 Correct 2 ms 8796 KB n=100
13 Correct 2 ms 8796 KB n=100
14 Correct 2 ms 8796 KB n=100
15 Correct 2 ms 8792 KB n=100
16 Correct 3 ms 8796 KB n=100
17 Correct 3 ms 8792 KB n=100
18 Correct 2 ms 8796 KB n=100
19 Correct 2 ms 8792 KB n=100
20 Correct 3 ms 8796 KB n=100
21 Correct 2 ms 8792 KB n=100
22 Correct 2 ms 8796 KB n=100
23 Correct 6 ms 8792 KB n=100
24 Correct 5 ms 8792 KB n=100
25 Correct 2 ms 8796 KB n=100
26 Correct 2 ms 8796 KB n=12
27 Correct 6 ms 8920 KB n=100
28 Correct 3 ms 8796 KB n=500
29 Correct 46 ms 8796 KB n=500
30 Correct 37 ms 8796 KB n=500
31 Correct 41 ms 8796 KB n=500
32 Correct 4 ms 8796 KB n=500
33 Correct 38 ms 8792 KB n=500
34 Correct 2 ms 8796 KB n=500
35 Correct 43 ms 8792 KB n=500
36 Correct 294 ms 8928 KB n=500
37 Correct 292 ms 8792 KB n=500
38 Correct 285 ms 8932 KB n=500
39 Correct 98 ms 8932 KB n=500
40 Correct 104 ms 8932 KB n=500
41 Correct 93 ms 8928 KB n=500
42 Correct 150 ms 8792 KB n=500
43 Correct 151 ms 8792 KB n=500
44 Correct 147 ms 8796 KB n=500
45 Correct 3 ms 8792 KB n=500
46 Correct 42 ms 8796 KB n=500
47 Correct 39 ms 8796 KB n=500
48 Correct 2 ms 8792 KB n=500
49 Correct 36 ms 8968 KB n=500
50 Correct 60 ms 8796 KB n=500
51 Correct 64 ms 8796 KB n=500
52 Correct 78 ms 8944 KB n=500
53 Correct 78 ms 8796 KB n=500
54 Correct 50 ms 8948 KB n=500
55 Correct 11 ms 8960 KB n=278
56 Correct 241 ms 8952 KB n=500
57 Correct 253 ms 8796 KB n=500
58 Correct 193 ms 8932 KB n=500
59 Correct 13 ms 8796 KB n=2000
60 Correct 934 ms 9084 KB n=2000
61 Correct 879 ms 9300 KB n=2000
62 Correct 613 ms 8796 KB n=2000
63 Correct 19 ms 9048 KB n=2000
64 Correct 831 ms 9028 KB n=2000
65 Correct 8 ms 9048 KB n=2000
66 Correct 999 ms 9068 KB n=2000
67 Correct 53 ms 8792 KB n=2000
68 Correct 866 ms 9052 KB n=2000
69 Correct 3345 ms 9008 KB n=2000
70 Correct 3344 ms 9248 KB n=2000
71 Correct 3382 ms 9020 KB n=2000
72 Correct 2417 ms 9004 KB n=2000
73 Correct 2378 ms 9256 KB n=2000
74 Correct 7 ms 8796 KB n=1844
75 Correct 2494 ms 9016 KB n=2000
76 Correct 1717 ms 9044 KB n=2000
77 Correct 1705 ms 9180 KB n=2000
78 Correct 1837 ms 9252 KB n=2000
79 Correct 7 ms 8796 KB n=2000
80 Correct 808 ms 9072 KB n=2000
81 Correct 731 ms 9044 KB n=2000
82 Correct 8 ms 8796 KB n=2000
83 Correct 808 ms 9056 KB n=2000
84 Correct 1346 ms 9008 KB n=2000
85 Correct 1362 ms 9028 KB n=2000
86 Correct 1424 ms 9048 KB n=2000
87 Correct 1408 ms 9048 KB n=2000
88 Correct 3347 ms 9088 KB n=2000
89 Correct 3344 ms 9092 KB n=2000
90 Correct 996 ms 9300 KB n=2000
91 Correct 3772 ms 9008 KB n=2000
92 Execution timed out 4101 ms 36180 KB Time limit exceeded
93 Halted 0 ms 0 KB -