Submission #500801

#TimeUsernameProblemLanguageResultExecution timeMemory
500801pragmatistBirthday gift (IZhO18_treearray)C++17
56 / 100
4046 ms56344 KiB
#include <bits/stdc++.h> #define pb push_back #define sz(v) (int)v.size() #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() #define x first #define y second #define int long long #define nl "\n" using namespace std; typedef long long ll; typedef pair<long long, long long> pll; typedef pair <ll, ll> pii; const int N = (int)2e5 + 7; const int M = (int)7e6 + 7; const ll MOD = (ll)1e9 + 7; const int inf = (int)1e9 + 7; const ll INF = (ll)3e18 + 7; pii dir[] = {{-1, -1}, {1, 1}, {-1, 1}, {1, -1}}; int n, m, q, a[N], t[4*N], leaf; int timer, tin[N], tout[N], up[N][19]; vector<int> g[N]; void calc(int v, int pr) { up[v][0] = pr; tin[v] = ++timer; for(int i = 1; i <= 18; ++i) { up[v][i] = up[up[v][i-1]][i-1]; } for(auto to : g[v]) { if(to != pr) { calc(to, v); } } tout[v] = ++timer; } bool is_parent(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; } int lca(int u, int v) { if(u == -1) return v; if(v == -1) return u; if(is_parent(u, v)) return u; if(is_parent(v, u)) return v; for(int i = 18; i >= 0; --i) { if(!is_parent(up[u][i], v)) { u = up[u][i]; } } return up[u][0]; } void build(int v, int tl, int tr) { if(tl == tr) { t[v] = a[tl]; return; } int mid = (tl + tr) >> 1; build(v * 2, tl, mid); build(v * 2 + 1, mid + 1, tr); t[v] = lca(t[v * 2], t[v * 2 + 1]); } void upd(int v, int tl, int tr, int id, int x) { if(tl == tr) { t[v] = x; return; } int mid = (tl + tr) >> 1; if(id <= mid) upd(v * 2, tl, mid, id, x); else upd(v * 2 + 1, mid + 1, tr, id, x); t[v] = lca(t[v * 2], t[v * 2 + 1]); } int get(int v, int tl, int tr, int l, int r) { if(tl >= l && tr <= r) return t[v]; if(tl > r || l > tr) return -1; int mid = (tl + tr) >> 1; return lca(get(v * 2, tl, mid, l, r), get(v * 2 + 1, mid + 1, tr, l, r)); } void solve() { cin >> n >> m >> q; for(int i = 1; i < n; ++i) { int u, v; cin >> u >> v; g[u].pb(v); g[v].pb(u); } for(int i = 1; i <= m; ++i) cin >> a[i]; calc(1, 1); build(1, 1, m); while(q--) { char tp; cin >> tp; int l, r, v; if(tp == '1') { cin >> l >> r; upd(1, 1, m, l, r); } else { cin >> l >> r >> v; int a = -1, b = -1; for(int i = l; i <= r && a == -1; ++i) { int L = i, R = r, res = -1; while(L <= R) { int mid = (L + R) >> 1; int x = get(1, 1, m, i, mid); if(x == v) { a = i; b = mid; break; } if(is_parent(x, v)) { res = mid; R = mid - 1; } else L = mid + 1; } } cout << a << ' ' << b << nl; } } } signed main() { ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0); int test = 1; //cin >> test; for(int i = 1; i <= test; ++i) { //cout << "Case " << i << ": "; solve(); } return 0; } /* 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 */

Compilation message (stderr)

treearray.cpp: In function 'void solve()':
treearray.cpp:116:23: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  116 |     int L = i, R = r, res = -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...