Submission #1195063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195063		Hamed_Ghaffari	Birthday gift (IZhO18_treearray)	C++20	100 / 100	448 ms	78104 KiB

treearray

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

#define X first
#define Y second

const int MXN = 2e5+5, LOG = 18;

int n, m, q, a[MXN], h[MXN], par[MXN][LOG];
vector<int> g[MXN];
set<int> st1[MXN], st2[MXN];

void dfs(int v) {
    for(int i=1; i<LOG; i++)
        par[v][i] = par[par[v][i-1]][i-1];
    for(int u : g[v]) 
        if(u!=par[v][0]) {
            h[u] = h[v]+1;
            par[u][0] = v;
            dfs(u);
        }
}

inline int jump(int v, int d) {
    for(int i=0; i<LOG; i++)
        if(d>>i&1)
            v = par[v][i];
    return v;
}

inline int LCA(int u, int v) {
    if(h[u]<h[v]) swap(u, v);
    u = jump(u, h[u]-h[v]);
    if(u==v) return u;
    for(int i=LOG-1; i>=0; i--)
        if(par[u][i]!=par[v][i])
            u = par[u][i], v = par[v][i];
    return par[u][0];
}

inline void upd(int p, int v) {
    st1[a[p]].erase(p);
    if(p>1) st2[LCA(a[p-1], a[p])].erase(p-1);
    if(p+1<=m) st2[LCA(a[p], a[p+1])].erase(p);
    a[p] = v;
    st1[a[p]].insert(p);
    if(p>1) st2[LCA(a[p-1], a[p])].insert(p-1);
    if(p+1<=m) st2[LCA(a[p], a[p+1])].insert(p);
}

inline pair<int, int> get(int l, int r, int v) {
    auto it = st1[v].lower_bound(l);
    if(it!=st1[v].end() && *it<=r) return {*it, *it};
    it = st2[v].lower_bound(l);
    if(it!=st2[v].end() && *it<r) return {*it, (*it)+1};
    return {-1, -1};
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m >> q;
    for(int i=0,u,v; i<n-1; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1);
    for(int i=1; i<=m; i++) {
        cin >> a[i];
        st1[a[i]].insert(i);
        if(i>1) st2[LCA(a[i-1], a[i])].insert(i-1);
    }
    while(q--) {
        int t;
        cin >> t;
        if(t==1) {
            int p, v;
            cin >> p >> v;
            upd(p, v);
        }
        else {
            int l, r, v;
            cin >> l >> r >> v;
            auto ans = get(l, r, v);
            cout << ans.first << ' ' << ans.second << '\n';
        }
    }
    return 0;
}

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