Submission #495902

#TimeUsernameProblemLanguageResultExecution timeMemory
495902armashkaBirthday gift (IZhO18_treearray)C++17
30 / 100
30 ms36144 KiB
#include <bits/stdc++.h> //#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #define fast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); #define all(v) v.begin(),v.end() #define pb push_back #define sz size() #define ft first #define sd second using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef unsigned long long ull; const int N = 3e5 + 5; const ll M = 1e8; const ll inf = 1e3; const ll mod = 1e9; const double Pi = acos(-1); ll binpow(ll x, ll ti) { ll res = 1;while (ti){if(ti & 1)res *= x;x *= x;ti >>= 1; x %= mod; res %= mod;} return res;} ll binmul(ll x, ll ti) { ll res = 0;while (ti){if(ti & 1)res += x;x += x;ti >>= 1; x %= mod; res %= mod;} return res;} ll nok(ll a, ll b) { return (a*b)/__gcd(abs(a),abs(b)) * (a*b > 0 ? 1 : -1); } bool odd(ll n) { return (n % 2 == 1); } bool even(ll n) { return (n % 2 == 0); } ll n, m, q, a[N], d[N], p[N], len, t[N * 4], in[N], out[N], timer; vector <ll> g[N], order; set <ll> st[N], ss[N]; bool used[N]; void dfs(ll v) { used[v] = 1; order.pb(v); in[v] = ++ timer; for (auto to : g[v]) { if (!used[to]) { d[to] = d[v] + 1; dfs(to); order.pb(v); } } out[v] = ++ timer; } void build(ll v = 1, ll tl = 1, ll tr = len) { if (tl == tr) { t[v] = order[tl - 1]; return; } ll tm = (tl + tr) / 2; build(v + v, tl, tm); build(v + v + 1, tm + 1, tr); if (d[t[v + v]] < d[t[v + v + 1]]) t[v] = t[v + v]; else t[v] = t[v + v + 1]; } ll get_lca(ll l, ll r, ll v = 1, ll tl = 1, ll tr = len) { if (r < tl || tr < l) return 0; if (l <= tl && tr <= r) return t[v]; ll tm = (tl + tr) / 2; ll ans1 = get_lca(l, r, v + v, tl, tm); ll ans2 = get_lca(l, r, v + v + 1, tm + 1, tr); if (d[ans1] < d[ans2]) return ans1; else return ans2; } const void solve(/*Armashka*/) { cin >> n >> m >> q; for (int i = 1; i < n; ++ i) { ll u, v; cin >> u >> v; g[u].pb(v); g[v].pb(u); } dfs(1); len = order.sz; build(); for (int i = 0; i < len; ++ i) { ll cur = order[i]; if (!p[cur]) p[cur] = i + 1; } d[0] = inf; for (int i = 1; i <= m; ++ i) cin >> a[i]; for (int i = 1; i < m; ++ i) { ll f = p[a[i]], s = p[a[i + 1]]; if (f > s) swap(f, s); ll lca = get_lca(f, s); st[lca].insert(i); ss[a[i]].insert(i); } ss[a[m]].insert(m); while (q --) { ll type; cin >> type; if (type == 1) { ll pos, val; cin >> pos >> val; if (pos > 1) { ll f = p[a[pos - 1]], s = p[a[pos]]; if (f > s) swap(f, s); st[get_lca(f, s)].erase(pos - 1); } if (pos < m) { ll f = p[a[pos]], s = p[a[pos + 1]]; if (f > s) swap(f, s); st[get_lca(f, s)].erase(pos); } ss[a[pos]].erase(pos); a[pos] = val; ss[a[pos]].insert(pos); if (pos > 1) { ll f = p[a[pos - 1]], s = p[a[pos]]; if (f > s) swap(f, s); st[get_lca(f, s)].insert(pos - 1); } if (pos < m) { ll f = p[a[pos]], s = p[a[pos + 1]]; if (f > s) swap(f, s); st[get_lca(f, s)].insert(pos); } } else { ll L, R, v; cin >> L >> R >> v; auto pos = st[v].lower_bound(L); if (pos != st[v].end() && *pos < R) cout << *pos << " " << *pos + 1 << "\n"; else { auto pos = ss[v].lower_bound(L); if (pos != ss[v].end() && *pos <= R) cout << *pos << " " << *pos << "\n"; else cout << "-1 -1\n"; } } } } signed main() { fast; //freopen("divide.in", "r", stdin); //freopen("divide.out", "w", stdout); int tt = 1; //cin >> tt; while (tt --) { 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 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...