oj.uz

Submission #1092037

# Submission time Handle Problem Language Result Execution time Memory
1092037 2024-09-23T02:26:23 Z juicy Birthday gift (IZhO18_treearray) C++17
100 / 100
 536 ms 120308 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5, LG = 19;

int n, m, q;
int a[N], tin[N], tout[N], lg[2 * N], spt[LG][2 * N];
set<int> x[N], y[N];
vector<int> g[N];

int cmb(int u, int v) {
  return tin[u] < tin[v] ? u : v;
}

int lca(int u, int v) {
  int l = min(tin[u], tin[v]), r = max(tin[u], tin[v]);
  int k = lg[r - l + 1];
  return cmb(spt[k][l], spt[k][r - (1 << k) + 1]);
}

int timer;

void dfs(int u) {
  spt[0][tin[u] = ++timer] = u;
  for (int v : g[u]) {
    if (!tin[v]) {
      dfs(v);
      spt[0][++timer] = u;
    }
  }
  tout[u] = timer;
}

int 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);
  }
  dfs(1);
  for (int i = 2; i <= timer; ++i) {
    lg[i] = lg[i / 2] + 1;
  }
  for (int j = 1; j < LG; ++j) {
    for (int i = 1; i + (1 << j) - 1 <= timer; ++i) {
      spt[j][i] = cmb(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
    }
  }
  for (int i = 1; i <= n; ++i) {
    x[i].insert(m + 1);
    y[i].insert(m + 1);
  }
  for (int i = 1; i <= m; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i <= m; ++i) {
    x[a[i]].insert(i);
    if (i < m) {
      y[lca(a[i], a[i + 1])].insert(i);
    }
  }
  while (q--) {
    int t; cin >> t;
    if (t == 1) {
      int i, v; cin >> i >> v;
      x[a[i]].erase(i);
      if (i > 1) {
        y[lca(a[i - 1], a[i])].erase(i - 1);
      }
      if (i < m) {
        y[lca(a[i], a[i + 1])].erase(i);
      }
      a[i] = v;
      x[a[i]].insert(i);
      if (i > 1) {
        y[lca(a[i - 1], a[i])].insert(i - 1);
      }
      if (i < m) {
        y[lca(a[i], a[i + 1])].insert(i);
      }
    } else {
      int l, r, v; cin >> l >> r >> v;
      int a = *x[v].lower_bound(l), b = *y[v].lower_bound(l);
      if (a <= r) {
        cout << a << " " << a << "\n";
      } else if (b < r) {
        cout << b << " " << b + 1 << "\n";
      } else {
        cout << "-1 -1\n";
      }
    }
  }
  return 0;
}

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:56:61: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   56 |       spt[j][i] = cmb(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
      |                                                           ~~^~~

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB n=5
2 Correct 10 ms 23900 KB n=100
3 Correct 10 ms 23900 KB n=100
4 Correct 10 ms 23900 KB n=100
5 Correct 10 ms 23928 KB n=100
6 Correct 9 ms 23900 KB n=100
7 Correct 11 ms 23900 KB n=100
8 Correct 10 ms 23896 KB n=100
9 Correct 10 ms 23900 KB n=100
10 Correct 10 ms 23900 KB n=100
11 Correct 10 ms 23896 KB n=100
12 Correct 10 ms 23900 KB n=100
13 Correct 11 ms 23836 KB n=100
14 Correct 10 ms 23896 KB n=100
15 Correct 10 ms 23900 KB n=100
16 Correct 11 ms 23896 KB n=100
17 Correct 10 ms 23900 KB n=100
18 Correct 10 ms 23900 KB n=100
19 Correct 10 ms 23896 KB n=100
20 Correct 10 ms 23896 KB n=100
21 Correct 12 ms 23940 KB n=100
22 Correct 11 ms 23896 KB n=100
23 Correct 10 ms 23900 KB n=100
24 Correct 9 ms 23900 KB n=100
25 Correct 10 ms 23896 KB n=100
26 Correct 10 ms 23924 KB n=12
27 Correct 10 ms 23900 KB n=100
28 Correct 11 ms 24152 KB n=500
29 Correct 11 ms 24208 KB n=500
30 Correct 10 ms 24156 KB n=500
31 Correct 10 ms 24156 KB n=500
32 Correct 10 ms 24156 KB n=500
33 Correct 10 ms 24220 KB n=500
34 Correct 12 ms 24156 KB n=500
35 Correct 10 ms 24152 KB n=500
36 Correct 10 ms 24208 KB n=500
37 Correct 11 ms 24152 KB n=500
38 Correct 12 ms 24108 KB n=500
39 Correct 11 ms 24156 KB n=500
40 Correct 10 ms 24152 KB n=500
41 Correct 9 ms 24152 KB n=500
42 Correct 10 ms 24156 KB n=500
43 Correct 10 ms 24156 KB n=500
44 Correct 14 ms 24412 KB n=500
45 Correct 10 ms 24156 KB n=500
46 Correct 10 ms 24156 KB n=500
47 Correct 11 ms 24156 KB n=500
48 Correct 10 ms 24076 KB n=500
49 Correct 10 ms 24156 KB n=500
50 Correct 10 ms 24156 KB n=500
51 Correct 11 ms 24156 KB n=500
52 Correct 10 ms 24152 KB n=500
53 Correct 10 ms 24156 KB n=500
54 Correct 12 ms 24012 KB n=500
55 Correct 11 ms 24156 KB n=278
56 Correct 10 ms 24152 KB n=500
57 Correct 10 ms 24156 KB n=500
58 Correct 11 ms 24156 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB n=5
2 Correct 10 ms 23900 KB n=100
3 Correct 10 ms 23900 KB n=100
4 Correct 10 ms 23900 KB n=100
5 Correct 10 ms 23928 KB n=100
6 Correct 9 ms 23900 KB n=100
7 Correct 11 ms 23900 KB n=100
8 Correct 10 ms 23896 KB n=100
9 Correct 10 ms 23900 KB n=100
10 Correct 10 ms 23900 KB n=100
11 Correct 10 ms 23896 KB n=100
12 Correct 10 ms 23900 KB n=100
13 Correct 11 ms 23836 KB n=100
14 Correct 10 ms 23896 KB n=100
15 Correct 10 ms 23900 KB n=100
16 Correct 11 ms 23896 KB n=100
17 Correct 10 ms 23900 KB n=100
18 Correct 10 ms 23900 KB n=100
19 Correct 10 ms 23896 KB n=100
20 Correct 10 ms 23896 KB n=100
21 Correct 12 ms 23940 KB n=100
22 Correct 11 ms 23896 KB n=100
23 Correct 10 ms 23900 KB n=100
24 Correct 9 ms 23900 KB n=100
25 Correct 10 ms 23896 KB n=100
26 Correct 10 ms 23924 KB n=12
27 Correct 10 ms 23900 KB n=100
28 Correct 11 ms 24152 KB n=500
29 Correct 11 ms 24208 KB n=500
30 Correct 10 ms 24156 KB n=500
31 Correct 10 ms 24156 KB n=500
32 Correct 10 ms 24156 KB n=500
33 Correct 10 ms 24220 KB n=500
34 Correct 12 ms 24156 KB n=500
35 Correct 10 ms 24152 KB n=500
36 Correct 10 ms 24208 KB n=500
37 Correct 11 ms 24152 KB n=500
38 Correct 12 ms 24108 KB n=500
39 Correct 11 ms 24156 KB n=500
40 Correct 10 ms 24152 KB n=500
41 Correct 9 ms 24152 KB n=500
42 Correct 10 ms 24156 KB n=500
43 Correct 10 ms 24156 KB n=500
44 Correct 14 ms 24412 KB n=500
45 Correct 10 ms 24156 KB n=500
46 Correct 10 ms 24156 KB n=500
47 Correct 11 ms 24156 KB n=500
48 Correct 10 ms 24076 KB n=500
49 Correct 10 ms 24156 KB n=500
50 Correct 10 ms 24156 KB n=500
51 Correct 11 ms 24156 KB n=500
52 Correct 10 ms 24152 KB n=500
53 Correct 10 ms 24156 KB n=500
54 Correct 12 ms 24012 KB n=500
55 Correct 11 ms 24156 KB n=278
56 Correct 10 ms 24152 KB n=500
57 Correct 10 ms 24156 KB n=500
58 Correct 11 ms 24156 KB n=500
59 Correct 12 ms 24668 KB n=2000
60 Correct 12 ms 24664 KB n=2000
61 Correct 13 ms 24668 KB n=2000
62 Correct 12 ms 24664 KB n=2000
63 Correct 11 ms 24664 KB n=2000
64 Correct 11 ms 24668 KB n=2000
65 Correct 12 ms 24668 KB n=2000
66 Correct 12 ms 24668 KB n=2000
67 Correct 13 ms 24668 KB n=2000
68 Correct 13 ms 24656 KB n=2000
69 Correct 12 ms 24664 KB n=2000
70 Correct 12 ms 24668 KB n=2000
71 Correct 13 ms 24668 KB n=2000
72 Correct 11 ms 24664 KB n=2000
73 Correct 11 ms 24668 KB n=2000
74 Correct 15 ms 24724 KB n=1844
75 Correct 12 ms 24668 KB n=2000
76 Correct 12 ms 24664 KB n=2000
77 Correct 11 ms 24668 KB n=2000
78 Correct 13 ms 24668 KB n=2000
79 Correct 12 ms 24668 KB n=2000
80 Correct 12 ms 24668 KB n=2000
81 Correct 12 ms 24664 KB n=2000
82 Correct 14 ms 24640 KB n=2000
83 Correct 13 ms 24664 KB n=2000
84 Correct 12 ms 24668 KB n=2000
85 Correct 12 ms 24668 KB n=2000
86 Correct 12 ms 24752 KB n=2000
87 Correct 11 ms 24668 KB n=2000
88 Correct 12 ms 24668 KB n=2000
89 Correct 14 ms 24664 KB n=2000
90 Correct 12 ms 24668 KB n=2000
91 Correct 11 ms 24668 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB n=5
2 Correct 10 ms 23900 KB n=100
3 Correct 10 ms 23900 KB n=100
4 Correct 10 ms 23900 KB n=100
5 Correct 10 ms 23928 KB n=100
6 Correct 9 ms 23900 KB n=100
7 Correct 11 ms 23900 KB n=100
8 Correct 10 ms 23896 KB n=100
9 Correct 10 ms 23900 KB n=100
10 Correct 10 ms 23900 KB n=100
11 Correct 10 ms 23896 KB n=100
12 Correct 10 ms 23900 KB n=100
13 Correct 11 ms 23836 KB n=100
14 Correct 10 ms 23896 KB n=100
15 Correct 10 ms 23900 KB n=100
16 Correct 11 ms 23896 KB n=100
17 Correct 10 ms 23900 KB n=100
18 Correct 10 ms 23900 KB n=100
19 Correct 10 ms 23896 KB n=100
20 Correct 10 ms 23896 KB n=100
21 Correct 12 ms 23940 KB n=100
22 Correct 11 ms 23896 KB n=100
23 Correct 10 ms 23900 KB n=100
24 Correct 9 ms 23900 KB n=100
25 Correct 10 ms 23896 KB n=100
26 Correct 10 ms 23924 KB n=12
27 Correct 10 ms 23900 KB n=100
28 Correct 11 ms 24152 KB n=500
29 Correct 11 ms 24208 KB n=500
30 Correct 10 ms 24156 KB n=500
31 Correct 10 ms 24156 KB n=500
32 Correct 10 ms 24156 KB n=500
33 Correct 10 ms 24220 KB n=500
34 Correct 12 ms 24156 KB n=500
35 Correct 10 ms 24152 KB n=500
36 Correct 10 ms 24208 KB n=500
37 Correct 11 ms 24152 KB n=500
38 Correct 12 ms 24108 KB n=500
39 Correct 11 ms 24156 KB n=500
40 Correct 10 ms 24152 KB n=500
41 Correct 9 ms 24152 KB n=500
42 Correct 10 ms 24156 KB n=500
43 Correct 10 ms 24156 KB n=500
44 Correct 14 ms 24412 KB n=500
45 Correct 10 ms 24156 KB n=500
46 Correct 10 ms 24156 KB n=500
47 Correct 11 ms 24156 KB n=500
48 Correct 10 ms 24076 KB n=500
49 Correct 10 ms 24156 KB n=500
50 Correct 10 ms 24156 KB n=500
51 Correct 11 ms 24156 KB n=500
52 Correct 10 ms 24152 KB n=500
53 Correct 10 ms 24156 KB n=500
54 Correct 12 ms 24012 KB n=500
55 Correct 11 ms 24156 KB n=278
56 Correct 10 ms 24152 KB n=500
57 Correct 10 ms 24156 KB n=500
58 Correct 11 ms 24156 KB n=500
59 Correct 12 ms 24668 KB n=2000
60 Correct 12 ms 24664 KB n=2000
61 Correct 13 ms 24668 KB n=2000
62 Correct 12 ms 24664 KB n=2000
63 Correct 11 ms 24664 KB n=2000
64 Correct 11 ms 24668 KB n=2000
65 Correct 12 ms 24668 KB n=2000
66 Correct 12 ms 24668 KB n=2000
67 Correct 13 ms 24668 KB n=2000
68 Correct 13 ms 24656 KB n=2000
69 Correct 12 ms 24664 KB n=2000
70 Correct 12 ms 24668 KB n=2000
71 Correct 13 ms 24668 KB n=2000
72 Correct 11 ms 24664 KB n=2000
73 Correct 11 ms 24668 KB n=2000
74 Correct 15 ms 24724 KB n=1844
75 Correct 12 ms 24668 KB n=2000
76 Correct 12 ms 24664 KB n=2000
77 Correct 11 ms 24668 KB n=2000
78 Correct 13 ms 24668 KB n=2000
79 Correct 12 ms 24668 KB n=2000
80 Correct 12 ms 24668 KB n=2000
81 Correct 12 ms 24664 KB n=2000
82 Correct 14 ms 24640 KB n=2000
83 Correct 13 ms 24664 KB n=2000
84 Correct 12 ms 24668 KB n=2000
85 Correct 12 ms 24668 KB n=2000
86 Correct 12 ms 24752 KB n=2000
87 Correct 11 ms 24668 KB n=2000
88 Correct 12 ms 24668 KB n=2000
89 Correct 14 ms 24664 KB n=2000
90 Correct 12 ms 24668 KB n=2000
91 Correct 11 ms 24668 KB n=2000
92 Correct 492 ms 107732 KB n=200000
93 Correct 492 ms 114252 KB n=200000
94 Correct 458 ms 118612 KB n=200000
95 Correct 499 ms 107472 KB n=200000
96 Correct 462 ms 107656 KB n=200000
97 Correct 492 ms 113148 KB n=200000
98 Correct 449 ms 107688 KB n=200000
99 Correct 531 ms 107860 KB n=200000
100 Correct 473 ms 107776 KB n=200000
101 Correct 462 ms 120308 KB n=200000
102 Correct 275 ms 108856 KB n=200000
103 Correct 286 ms 108880 KB n=200000
104 Correct 290 ms 108880 KB n=200000
105 Correct 279 ms 109136 KB n=200000
106 Correct 287 ms 109140 KB n=200000
107 Correct 272 ms 109136 KB n=200000
108 Correct 491 ms 107600 KB n=200000
109 Correct 486 ms 107684 KB n=200000
110 Correct 470 ms 107588 KB n=200000
111 Correct 517 ms 107340 KB n=200000
112 Correct 488 ms 119124 KB n=200000
113 Correct 497 ms 112976 KB n=200000
114 Correct 474 ms 107204 KB n=200000
115 Correct 504 ms 110164 KB n=200000
116 Correct 468 ms 107932 KB n=200000
117 Correct 472 ms 119632 KB n=200000
118 Correct 517 ms 111440 KB n=200000
119 Correct 536 ms 107792 KB n=200000
120 Correct 399 ms 119380 KB n=200000
121 Correct 423 ms 119504 KB n=200000
122 Correct 457 ms 119632 KB n=200000
123 Correct 314 ms 109136 KB n=200000
124 Correct 104 ms 42836 KB n=25264