oj.uz

Submission #519790

# Submission time Handle Problem Language Result Execution time Memory
519790 2022-01-27T10:35:20 Z Dasha_Gnedko Birthday gift (IZhO18_treearray) C++17
100 / 100
 968 ms 83236 KB 
#include <bits/stdc++.h>

//#include <ext/pb_ds/detail/standard_policies.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

using namespace std;

//using namespace __gnu_pbds;
//template <typename T> using ordered_set = tree <T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 gen(time(0));

#define ll long long
#define ld long double
#define pb push_back
#define F first
#define S second
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define sz(a) int32_t(a.size())
#define endl '\n'
//#define int long long

const int N = 2e5 + 100;
const int M = 18;
const int mod = 998244353;
const int inf = 1e9 + 7;

vector < int > g[N];
set < int > st1[N], st2[N];
int up[N][M], tin[N], tout[N], timer, a[N];

void DFS(int v, int pr)
{
    up[v][0] = pr;
    for(int j = 1; j < M; j++)
        up[v][j] = up[up[v][j - 1]][j - 1];
    tin[v] = timer++;
    for(auto to: g[v])
    {
        if (to == pr) continue;
        DFS(to, v);
    }
    tout[v] = timer++;
}

bool upper(int a, int b)
{
    return ((tin[a] <= tin[b]) && (tout[a] >= tout[b]));
}

int LCA(int a, int b)
{
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;
    for(int j = M - 1; j >= 0; j--)
        if (!upper(up[a][j], b)) a = up[a][j];
    return up[a][0];
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif // LOCAL

    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 0; i < n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        x--; y--;
        g[x].pb(y);
        g[y].pb(x);
    }
    DFS(0, 0);
    for(int i = 0; i < m; i++)
    {
        cin >> a[i];
        a[i]--;
        st2[a[i]].insert(i);
        if (i) st1[LCA(a[i - 1], a[i])].insert(i - 1);
    }
    while (q--)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int i, x;
            cin >> i >> x;
            i--; x--;
            st2[a[i]].erase(i);
            if (i) st1[LCA(a[i - 1], a[i])].erase(i - 1);
            if (i + 1 < m) st1[LCA(a[i], a[i + 1])].erase(i);
            a[i] = x;
            st2[a[i]].insert(i);
            if (i) st1[LCA(a[i - 1], a[i])].insert(i - 1);
            if (i + 1 < m) st1[LCA(a[i], a[i + 1])].insert(i);
        }
        if (type == 2)
        {
            int l, r, x;
            cin >> l >> r >> x;
            l--; r--; x--;
            auto it = st2[x].lower_bound(l);
            if (it != st2[x].end())
            {
                int p = *(it);
                if (p <= r)
                {
                    cout << p + 1 << " " << p + 1 << endl;
                    continue;
                }
            }
            it = st1[x].lower_bound(l);
            if (it != st1[x].end())
            {
                int p = *(it);
                if (p < r)
                {
                    cout << p + 1 << " " << p + 2 << endl;
                    continue;
                }
            }
            cout << "-1 -1" << endl;
        }
    }

}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23824 KB n=5
2 Correct 13 ms 23784 KB n=100
3 Correct 14 ms 23760 KB n=100
4 Correct 13 ms 23812 KB n=100
5 Correct 12 ms 23828 KB n=100
6 Correct 12 ms 23760 KB n=100
7 Correct 12 ms 23760 KB n=100
8 Correct 13 ms 23824 KB n=100
9 Correct 12 ms 23828 KB n=100
10 Correct 12 ms 23836 KB n=100
11 Correct 12 ms 23832 KB n=100
12 Correct 17 ms 23760 KB n=100
13 Correct 13 ms 23760 KB n=100
14 Correct 12 ms 23828 KB n=100
15 Correct 14 ms 23764 KB n=100
16 Correct 12 ms 23820 KB n=100
17 Correct 13 ms 23760 KB n=100
18 Correct 12 ms 23832 KB n=100
19 Correct 15 ms 23804 KB n=100
20 Correct 13 ms 23888 KB n=100
21 Correct 12 ms 23760 KB n=100
22 Correct 12 ms 23840 KB n=100
23 Correct 13 ms 23828 KB n=100
24 Correct 13 ms 23760 KB n=100
25 Correct 13 ms 23804 KB n=100
26 Correct 13 ms 23828 KB n=12
27 Correct 12 ms 23760 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23824 KB n=5
2 Correct 13 ms 23784 KB n=100
3 Correct 14 ms 23760 KB n=100
4 Correct 13 ms 23812 KB n=100
5 Correct 12 ms 23828 KB n=100
6 Correct 12 ms 23760 KB n=100
7 Correct 12 ms 23760 KB n=100
8 Correct 13 ms 23824 KB n=100
9 Correct 12 ms 23828 KB n=100
10 Correct 12 ms 23836 KB n=100
11 Correct 12 ms 23832 KB n=100
12 Correct 17 ms 23760 KB n=100
13 Correct 13 ms 23760 KB n=100
14 Correct 12 ms 23828 KB n=100
15 Correct 14 ms 23764 KB n=100
16 Correct 12 ms 23820 KB n=100
17 Correct 13 ms 23760 KB n=100
18 Correct 12 ms 23832 KB n=100
19 Correct 15 ms 23804 KB n=100
20 Correct 13 ms 23888 KB n=100
21 Correct 12 ms 23760 KB n=100
22 Correct 12 ms 23840 KB n=100
23 Correct 13 ms 23828 KB n=100
24 Correct 13 ms 23760 KB n=100
25 Correct 13 ms 23804 KB n=100
26 Correct 13 ms 23828 KB n=12
27 Correct 12 ms 23760 KB n=100
28 Correct 13 ms 23888 KB n=500
29 Correct 12 ms 23896 KB n=500
30 Correct 13 ms 23916 KB n=500
31 Correct 13 ms 23976 KB n=500
32 Correct 13 ms 23888 KB n=500
33 Correct 12 ms 23912 KB n=500
34 Correct 13 ms 23884 KB n=500
35 Correct 13 ms 23888 KB n=500
36 Correct 14 ms 23940 KB n=500
37 Correct 13 ms 23888 KB n=500
38 Correct 12 ms 23888 KB n=500
39 Correct 14 ms 23908 KB n=500
40 Correct 15 ms 23888 KB n=500
41 Correct 13 ms 23888 KB n=500
42 Correct 13 ms 23968 KB n=500
43 Correct 14 ms 23968 KB n=500
44 Correct 13 ms 23944 KB n=500
45 Correct 13 ms 23896 KB n=500
46 Correct 13 ms 23968 KB n=500
47 Correct 13 ms 23964 KB n=500
48 Correct 13 ms 23844 KB n=500
49 Correct 12 ms 23888 KB n=500
50 Correct 13 ms 23888 KB n=500
51 Correct 13 ms 23972 KB n=500
52 Correct 14 ms 23964 KB n=500
53 Correct 13 ms 23888 KB n=500
54 Correct 14 ms 23952 KB n=500
55 Correct 13 ms 23888 KB n=278
56 Correct 13 ms 23928 KB n=500
57 Correct 13 ms 23888 KB n=500
58 Correct 13 ms 23888 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23824 KB n=5
2 Correct 13 ms 23784 KB n=100
3 Correct 14 ms 23760 KB n=100
4 Correct 13 ms 23812 KB n=100
5 Correct 12 ms 23828 KB n=100
6 Correct 12 ms 23760 KB n=100
7 Correct 12 ms 23760 KB n=100
8 Correct 13 ms 23824 KB n=100
9 Correct 12 ms 23828 KB n=100
10 Correct 12 ms 23836 KB n=100
11 Correct 12 ms 23832 KB n=100
12 Correct 17 ms 23760 KB n=100
13 Correct 13 ms 23760 KB n=100
14 Correct 12 ms 23828 KB n=100
15 Correct 14 ms 23764 KB n=100
16 Correct 12 ms 23820 KB n=100
17 Correct 13 ms 23760 KB n=100
18 Correct 12 ms 23832 KB n=100
19 Correct 15 ms 23804 KB n=100
20 Correct 13 ms 23888 KB n=100
21 Correct 12 ms 23760 KB n=100
22 Correct 12 ms 23840 KB n=100
23 Correct 13 ms 23828 KB n=100
24 Correct 13 ms 23760 KB n=100
25 Correct 13 ms 23804 KB n=100
26 Correct 13 ms 23828 KB n=12
27 Correct 12 ms 23760 KB n=100
28 Correct 13 ms 23888 KB n=500
29 Correct 12 ms 23896 KB n=500
30 Correct 13 ms 23916 KB n=500
31 Correct 13 ms 23976 KB n=500
32 Correct 13 ms 23888 KB n=500
33 Correct 12 ms 23912 KB n=500
34 Correct 13 ms 23884 KB n=500
35 Correct 13 ms 23888 KB n=500
36 Correct 14 ms 23940 KB n=500
37 Correct 13 ms 23888 KB n=500
38 Correct 12 ms 23888 KB n=500
39 Correct 14 ms 23908 KB n=500
40 Correct 15 ms 23888 KB n=500
41 Correct 13 ms 23888 KB n=500
42 Correct 13 ms 23968 KB n=500
43 Correct 14 ms 23968 KB n=500
44 Correct 13 ms 23944 KB n=500
45 Correct 13 ms 23896 KB n=500
46 Correct 13 ms 23968 KB n=500
47 Correct 13 ms 23964 KB n=500
48 Correct 13 ms 23844 KB n=500
49 Correct 12 ms 23888 KB n=500
50 Correct 13 ms 23888 KB n=500
51 Correct 13 ms 23972 KB n=500
52 Correct 14 ms 23964 KB n=500
53 Correct 13 ms 23888 KB n=500
54 Correct 14 ms 23952 KB n=500
55 Correct 13 ms 23888 KB n=278
56 Correct 13 ms 23928 KB n=500
57 Correct 13 ms 23888 KB n=500
58 Correct 13 ms 23888 KB n=500
59 Correct 15 ms 24220 KB n=2000
60 Correct 16 ms 24408 KB n=2000
61 Correct 15 ms 24272 KB n=2000
62 Correct 16 ms 24252 KB n=2000
63 Correct 16 ms 24272 KB n=2000
64 Correct 16 ms 24272 KB n=2000
65 Correct 15 ms 24284 KB n=2000
66 Correct 15 ms 24320 KB n=2000
67 Correct 17 ms 24220 KB n=2000
68 Correct 15 ms 24352 KB n=2000
69 Correct 17 ms 24228 KB n=2000
70 Correct 15 ms 24272 KB n=2000
71 Correct 14 ms 24220 KB n=2000
72 Correct 15 ms 24252 KB n=2000
73 Correct 15 ms 24272 KB n=2000
74 Correct 17 ms 24304 KB n=1844
75 Correct 15 ms 24272 KB n=2000
76 Correct 16 ms 24216 KB n=2000
77 Correct 15 ms 24220 KB n=2000
78 Correct 15 ms 24208 KB n=2000
79 Correct 15 ms 24296 KB n=2000
80 Correct 15 ms 24400 KB n=2000
81 Correct 15 ms 24272 KB n=2000
82 Correct 17 ms 24272 KB n=2000
83 Correct 14 ms 24352 KB n=2000
84 Correct 17 ms 24272 KB n=2000
85 Correct 15 ms 24352 KB n=2000
86 Correct 16 ms 24348 KB n=2000
87 Correct 15 ms 24272 KB n=2000
88 Correct 15 ms 24400 KB n=2000
89 Correct 15 ms 24400 KB n=2000
90 Correct 16 ms 24400 KB n=2000
91 Correct 14 ms 24272 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23824 KB n=5
2 Correct 13 ms 23784 KB n=100
3 Correct 14 ms 23760 KB n=100
4 Correct 13 ms 23812 KB n=100
5 Correct 12 ms 23828 KB n=100
6 Correct 12 ms 23760 KB n=100
7 Correct 12 ms 23760 KB n=100
8 Correct 13 ms 23824 KB n=100
9 Correct 12 ms 23828 KB n=100
10 Correct 12 ms 23836 KB n=100
11 Correct 12 ms 23832 KB n=100
12 Correct 17 ms 23760 KB n=100
13 Correct 13 ms 23760 KB n=100
14 Correct 12 ms 23828 KB n=100
15 Correct 14 ms 23764 KB n=100
16 Correct 12 ms 23820 KB n=100
17 Correct 13 ms 23760 KB n=100
18 Correct 12 ms 23832 KB n=100
19 Correct 15 ms 23804 KB n=100
20 Correct 13 ms 23888 KB n=100
21 Correct 12 ms 23760 KB n=100
22 Correct 12 ms 23840 KB n=100
23 Correct 13 ms 23828 KB n=100
24 Correct 13 ms 23760 KB n=100
25 Correct 13 ms 23804 KB n=100
26 Correct 13 ms 23828 KB n=12
27 Correct 12 ms 23760 KB n=100
28 Correct 13 ms 23888 KB n=500
29 Correct 12 ms 23896 KB n=500
30 Correct 13 ms 23916 KB n=500
31 Correct 13 ms 23976 KB n=500
32 Correct 13 ms 23888 KB n=500
33 Correct 12 ms 23912 KB n=500
34 Correct 13 ms 23884 KB n=500
35 Correct 13 ms 23888 KB n=500
36 Correct 14 ms 23940 KB n=500
37 Correct 13 ms 23888 KB n=500
38 Correct 12 ms 23888 KB n=500
39 Correct 14 ms 23908 KB n=500
40 Correct 15 ms 23888 KB n=500
41 Correct 13 ms 23888 KB n=500
42 Correct 13 ms 23968 KB n=500
43 Correct 14 ms 23968 KB n=500
44 Correct 13 ms 23944 KB n=500
45 Correct 13 ms 23896 KB n=500
46 Correct 13 ms 23968 KB n=500
47 Correct 13 ms 23964 KB n=500
48 Correct 13 ms 23844 KB n=500
49 Correct 12 ms 23888 KB n=500
50 Correct 13 ms 23888 KB n=500
51 Correct 13 ms 23972 KB n=500
52 Correct 14 ms 23964 KB n=500
53 Correct 13 ms 23888 KB n=500
54 Correct 14 ms 23952 KB n=500
55 Correct 13 ms 23888 KB n=278
56 Correct 13 ms 23928 KB n=500
57 Correct 13 ms 23888 KB n=500
58 Correct 13 ms 23888 KB n=500
59 Correct 15 ms 24220 KB n=2000
60 Correct 16 ms 24408 KB n=2000
61 Correct 15 ms 24272 KB n=2000
62 Correct 16 ms 24252 KB n=2000
63 Correct 16 ms 24272 KB n=2000
64 Correct 16 ms 24272 KB n=2000
65 Correct 15 ms 24284 KB n=2000
66 Correct 15 ms 24320 KB n=2000
67 Correct 17 ms 24220 KB n=2000
68 Correct 15 ms 24352 KB n=2000
69 Correct 17 ms 24228 KB n=2000
70 Correct 15 ms 24272 KB n=2000
71 Correct 14 ms 24220 KB n=2000
72 Correct 15 ms 24252 KB n=2000
73 Correct 15 ms 24272 KB n=2000
74 Correct 17 ms 24304 KB n=1844
75 Correct 15 ms 24272 KB n=2000
76 Correct 16 ms 24216 KB n=2000
77 Correct 15 ms 24220 KB n=2000
78 Correct 15 ms 24208 KB n=2000
79 Correct 15 ms 24296 KB n=2000
80 Correct 15 ms 24400 KB n=2000
81 Correct 15 ms 24272 KB n=2000
82 Correct 17 ms 24272 KB n=2000
83 Correct 14 ms 24352 KB n=2000
84 Correct 17 ms 24272 KB n=2000
85 Correct 15 ms 24352 KB n=2000
86 Correct 16 ms 24348 KB n=2000
87 Correct 15 ms 24272 KB n=2000
88 Correct 15 ms 24400 KB n=2000
89 Correct 15 ms 24400 KB n=2000
90 Correct 16 ms 24400 KB n=2000
91 Correct 14 ms 24272 KB n=2000
92 Correct 668 ms 73812 KB n=200000
93 Correct 719 ms 78632 KB n=200000
94 Correct 531 ms 81992 KB n=200000
95 Correct 655 ms 73544 KB n=200000
96 Correct 622 ms 73532 KB n=200000
97 Correct 772 ms 77824 KB n=200000
98 Correct 647 ms 73604 KB n=200000
99 Correct 753 ms 73832 KB n=200000
100 Correct 665 ms 73720 KB n=200000
101 Correct 480 ms 83236 KB n=200000
102 Correct 393 ms 74752 KB n=200000
103 Correct 395 ms 74936 KB n=200000
104 Correct 397 ms 74704 KB n=200000
105 Correct 418 ms 75160 KB n=200000
106 Correct 397 ms 75320 KB n=200000
107 Correct 400 ms 75332 KB n=200000
108 Correct 687 ms 73692 KB n=200000
109 Correct 676 ms 73660 KB n=200000
110 Correct 706 ms 73604 KB n=200000
111 Correct 649 ms 73004 KB n=200000
112 Correct 509 ms 82400 KB n=200000
113 Correct 770 ms 77676 KB n=200000
114 Correct 651 ms 73096 KB n=200000
115 Correct 968 ms 75592 KB n=200000
116 Correct 636 ms 73748 KB n=200000
117 Correct 488 ms 82568 KB n=200000
118 Correct 843 ms 76636 KB n=200000
119 Correct 619 ms 73660 KB n=200000
120 Correct 436 ms 82260 KB n=200000
121 Correct 437 ms 82152 KB n=200000
122 Correct 448 ms 82564 KB n=200000
123 Correct 410 ms 74920 KB n=200000
124 Correct 156 ms 38552 KB n=25264