Submission #1310994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310994		okahak71	Birthday gift (IZhO18_treearray)	C++20	100 / 100	1521 ms	82884 KiB

treearray

#include <bits/stdc++.h>
#define ll long long
#define pll array<ll, 2>
#define lll array<ll, 3>
#define all(X) X.begin(), X.end()
#define pb push_back
using namespace std;

const ll inf = 1e17;

ll timer = 0;
vector<vector<ll>>g, up;
vector<ll>tin, tout;

void dfs(ll u, ll p = 0){
    tin[u] = ++timer;
    up[0][u] = p;
    for(ll &v : g[u]){
        if(v == p) continue;
        dfs(v, u);
    }
    tout[u] = ++timer;
}

bool is_anc(ll a, ll b){
    return tin[a] <= tin[b] and tout[a] >= tout[b];
}

ll lca(ll a, ll b){
    if(!(a * b)) return (a ? a : b);
    if(is_anc(a, b)) return a;
    if(is_anc(b, a)) return b;
    for(ll i = 19; i >= 0; i--){
        if(up[i][a] and !is_anc(up[i][a], b))
            a = up[i][a];
    }
    return up[0][a];
}

void _(){
    ll n, m, q;
    cin >> n >> m >> q;
    g.assign(n + 1, {});
    tin.assign(n + 1, 0);
    tout.assign(n + 1, 0);
    vector<ll>vv(m); set<pll>lc, st;
    up.assign(20, vector<ll>(n + 1, 0));
    for(ll i = 1; i < n; i++){
        ll a, b; cin >> a >> b;
        g[a].pb(b), g[b].pb(a);
    }
    dfs(1);
    for(ll i = 1; i < 20; i++){
        for(ll j = 1; j <= n; j++)
            up[i][j] = up[i - 1][up[i - 1][j]];
    }
    for(ll i = 0; i < m; i++){
        cin >> vv[i]; st.insert({vv[i], i});
        if(i) lc.insert({lca(vv[i], vv[i - 1]), i - 1});
    }
    while(q--){
        ll t; cin >> t;
        if(t == 1){
            ll id, vl; cin >> id >> vl;
            --id; if(id) lc.erase({lca(vv[id - 1], vv[id]), id - 1});
            if(id < m - 1) lc.erase({lca(vv[id], vv[id + 1]), id});
            st.erase({vv[id], id}); vv[id] = vl; st.insert({vv[id], id});
            if(id) lc.insert({lca(vv[id - 1], vv[id]), id - 1});
            if(id < m - 1) lc.insert({lca(vv[id], vv[id + 1]), id});
        }
        else{
            ll l, r, v;
            cin >> l >> r >> v; --l, --r;
            auto itt = st.lower_bound({v, l});
            auto it = lc.lower_bound({v, l});
            if(itt != st.end() and (*itt)[1] <= r and (*itt)[0] == v){
                cout << (*itt)[1] + 1 << ' ' << (*itt)[1] + 1 << endl;
                continue;
            }
            //if(itt == st.end()) cout << "no";
            if(it == lc.end() or (*it)[1] >= r or (*it)[0] != v) cout << "-1 -1";
            else cout << (*it)[1] + 1 << ' ' << (*it)[1] + 2; cout << endl;
        }
        //for(auto [x, y] : lc) cout << x << 'l' << y << endl;
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0); _();
}

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44