제출 #334889

#제출 시각아이디문제언어결과실행 시간메모리
334889talant117408Birthday gift (IZhO18_treearray)C++17
100 / 100
2423 ms60396 KiB
/* Code written by Talant I.D. */ #include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //using namespace __gnu_pbds; using namespace std; //typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; #define precision(n) fixed << setprecision(n) #define pb push_back #define ub upper_bound #define lb lower_bound #define mp make_pair #define eps (double)1e-9 #define PI 2*acos(0.0) #define endl "\n" #define sz(v) int((v).size()) #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() #define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define OK cout << "OK" << endl; inline bool isvowel(char ch){ ch = tolower(ch); return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'); } inline bool isprime(int n){ if(n < 2 || (n%2 == 0 && n != 2)) return false; for(int i = 3; i*i <= n; i++) if(n%i == 0) return false; return true; } class Union{ private: vector <int> saizu, link; public: Union(int n){ saizu.assign(n, 1); link.resize(n); iota(all(link), 0); } int find(int n){ if(link[n] == n) return n; return link[n] = find(link[n]); } int same(int a, int b){ return find(a) == find(b); } void unite(int a, int b){ if(same(a, b)) return; a = find(a); b = find(b); if(saizu[a] < saizu[b]) swap(a, b); saizu[a] += saizu[b]; link[b] = a; } int getsize(int a){ return saizu[find(a)]; } }; const int mod = 1e9+7; ll mode(ll a){ a %= mod; if(a < 0) a += mod; return a; } ll subt(ll a, ll b){ return mode(mode(a)-mode(b)); } ll add(ll a, ll b){ return mode(mode(a)+mode(b)); } ll mult(ll a, ll b){ return mode(mode(a)*mode(b)); } ll binpow(ll a, ll b){ ll res = 1; while(b){ if(b&1) res = mult(res, a); a = mult(a, a); b >>= 1; } return res; } const int N = 2e5+7; vector <vector <int>> graph(N); set <pii> st, t; int tree[N*4], vec[N], tin[N], tout[N], timer, up[N][20]; void dfs(int v, int p = 1){ 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 : graph[v]){ if(to != p){ 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 i = 19; i >= 0; i--){ if(!upper(up[a][i], b)) a = up[a][i]; } return up[a][0]; } int main(){ // do_not_disturb int n, m, q; cin >> n >> m >> q; for(int i = 0; i < n-1; i++){ int x, y; cin >> x >> y; graph[x].pb(y); graph[y].pb(x); } dfs(1); for(int i = 1; i <= m; i++){ cin >> vec[i]; } for(int i = 1; i <= m; i++){ t.insert(mp(vec[i], i)); if(i < m) st.insert(mp(lca(vec[i], vec[i+1]), i)); } while(q--){ int type; cin >> type; if(type == 1){ int pos, x; cin >> pos >> x; t.erase(mp(vec[pos], pos)); if(pos > 1) st.erase(mp(lca(vec[pos], vec[pos-1]), pos-1)); if(pos < m) st.erase(mp(lca(vec[pos], vec[pos+1]), pos)); vec[pos] = x; t.insert(mp(vec[pos], pos)); if(pos > 1) st.insert(mp(lca(vec[pos], vec[pos-1]), pos-1)); if(pos < m) st.insert(mp(lca(vec[pos], vec[pos+1]), pos)); } else{ int l, r, x; cin >> l >> r >> x; auto to = t.lb(mp(x, l)); if(to != t.end() && to -> first == x && to -> second <= r){ cout << (*to).second << ' ' << (*to).second << endl; } else{ auto it = st.lb(mp(x, l)); if(it != st.end() && it -> first == x && it -> second < r){ cout << (*it).second << ' ' << (*it).second+1 << endl; } else{ cout << "-1 -1" << endl; } } } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...