Submission #1058754

#TimeUsernameProblemLanguageResultExecution timeMemory
1058754Beerus13Birthday gift (IZhO18_treearray)C++14
100 / 100
496 ms122452 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define MIN_HIGH(x, t) (H[x] < H[t] ? (x) : (t)) #define Mask(i) (1 << i) const int N = 2e5 + 5; int n, m, q, cnt, a[N]; int H[N], P[N << 1][19], nodes[N << 1], pos[N]; vector<int> g[N]; set<int> sett[N], Pos[N]; void dfs(int u, int p = 0) { nodes[++cnt] = u; pos[u] = cnt; for (int v : g[u]) if(v != p) { H[v] = H[u] + 1; dfs(v, u); nodes[++cnt] = u; } } int lca(int u, int v) { int l = pos[u], r = pos[v]; if (l > r) swap(l, r); int k = 31 - __builtin_clz(r - l + 1); return MIN_HIGH(P[l][k], P[r - Mask(k) + 1][k]); } void solve() { cin >> n >> m >> q; for(int i = 1, u, v; i < n; ++i) { cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } dfs(1); for(int i = 1; i <= cnt; ++i) P[i][0] = nodes[i]; for(int j = 1; j < 19; ++j) for(int i = 1; i <= cnt - Mask(j) + 1; ++i) P[i][j] = MIN_HIGH(P[i][j - 1], P[i + Mask(j - 1)][j - 1]); for(int i = 1; i <= m; ++i) { cin >> a[i]; Pos[a[i]].insert(i); if(i > 1) sett[lca(a[i], a[i - 1])].insert(i); } for(int i = 1; i <= n; ++i) { Pos[i].insert(m + 1); sett[i].insert(m + 1); } while(q--) { int type, l, r, u; cin >> type >> l >> r; if(type == 1) { Pos[a[l]].erase(l); Pos[r].insert(l); if(l > 1) { sett[lca(a[l], a[l - 1])].erase(l); sett[lca(r, a[l - 1])].insert(l); } if(l < m) { sett[lca(a[l], a[l + 1])].erase(l + 1); sett[lca(r, a[l + 1])].insert(l + 1); } a[l] = r; } else { cin >> u; int res = *Pos[u].lower_bound(l); if(res <= r) cout << res << ' ' << res << '\n'; else { res = *sett[u].upper_bound(l); if(res <= r) cout << res - 1 << ' ' << res << '\n'; else cout << -1 << ' ' << -1 << '\n'; } } } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int test = 1; // cin >> test; while(test--) solve(); return 0; }

Compilation message (stderr)

treearray.cpp: In function 'void solve()':
treearray.cpp:40:58: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   40 |             P[i][j] = MIN_HIGH(P[i][j - 1], P[i + Mask(j - 1)][j - 1]);
      |                                                        ~~^~~
treearray.cpp:4:34: note: in definition of macro 'MIN_HIGH'
    4 | #define MIN_HIGH(x, t) (H[x] < H[t] ? (x) : (t))
      |                                  ^
treearray.cpp:40:51: note: in expansion of macro 'Mask'
   40 |             P[i][j] = MIN_HIGH(P[i][j - 1], P[i + Mask(j - 1)][j - 1]);
      |                                                   ^~~~
treearray.cpp:40:58: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   40 |             P[i][j] = MIN_HIGH(P[i][j - 1], P[i + Mask(j - 1)][j - 1]);
      |                                                        ~~^~~
treearray.cpp:4:46: note: in definition of macro 'MIN_HIGH'
    4 | #define MIN_HIGH(x, t) (H[x] < H[t] ? (x) : (t))
      |                                              ^
treearray.cpp:40:51: note: in expansion of macro 'Mask'
   40 |             P[i][j] = MIN_HIGH(P[i][j - 1], P[i + Mask(j - 1)][j - 1]);
      |                                                   ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...