Submission #340710

#	Time	Username	Problem	Language	Result	Execution time	Memory
340710		Dilshod_Imomov	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1252 ms	100588 KiB

treearray

# include <bits/stdc++.h>
# define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
# define inht long long
# define fi first
# define se second
 
using namespace std;
 
const int N = 2e5 + 7;
const int mod = 1e9 + 7;

int a[N], up[N][40], tin[N], tout[N], timer = 1, lg, x, y;
vector < int > adj[N];
set < int > st[N][2];

void dfs( int v, int p ) {
    up[v][0] = p;
    for ( int i = 1; i <= lg; i++ ) {
        up[v][i] = up[ up[v][i - 1] ][i - 1];
    }
    tin[v] = timer++;
    for ( auto u: adj[v] ) {
        if ( u != p ) {
            dfs( u, v );
        }
    }
    tout[v] = timer++;
}

bool is_upper( int a, int b ) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int LCA( int a, int b ) {
    if ( is_upper( a, b ) ) {
        return a;
    }
    if ( is_upper( b, a ) ) {
        return b;
    }
    for ( int i = lg; i >= 0; i-- ) {
        if ( !is_upper( up[a][i], b ) ) {
            a = up[a][i];
        }
    }
    return up[a][0];
}

pair < int, int > solve( int l, int r, int v ) {
    auto s = st[v];
    auto it = s[0].lower_bound(l);
    if ( it != s[0].end() && *it <= r ) {
        return { *it, *it };
    }
    it = s[1].lower_bound(l);
    if ( it != s[1].end() && *it + 1 <= r ) {
        return { *it, *it + 1 };
    }
    return {-1, -1};
}

int32_t main() {
    speed;
    int n, m, q;
    cin >> n >> m >> q;
    lg = log2(n) + 1;
    for ( int i = 1; i < n; i++ ) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs( 1, 1 );
    for ( int i = 1; i <= m; i++ ) {
        cin >> a[i];
    }
    for ( int i = 1; i <= m; i++ ) {
        st[ a[i] ][0].insert(i);
        if ( i + 1 <= m ) {
            st[ LCA( a[i], a[i + 1] ) ][1].insert(i);
        }
    }
    for ( int i = 1; i <= q; i++ ) {
        int t;
        cin >> t;
        if ( t == 1 ) {
            int pos, val;
            cin >> pos >> val;
            st[ a[pos] ][0].erase(pos);
            if ( pos + 1 <= m ) {
                st[ LCA( a[pos], a[pos + 1] ) ][1].erase(pos);
            }
            if ( pos - 1 > 0 ) {
                st[ LCA( a[pos - 1], a[pos] ) ][1].erase(pos - 1);
            }
            a[pos] = val;
            st[ a[pos] ][0].insert(pos);
            if ( pos + 1 <= m ) {
                st[ LCA( a[pos], a[pos + 1] ) ][1].insert(pos);
            }
            if ( pos - 1 > 0 ) {
                st[ LCA( a[pos - 1], a[pos] ) ][1].insert(pos - 1);
            }
        }
        else {
            int l, r, v;
            cin >> l >> r >> v;
            auto pr = solve( l, r, v );
            cout << pr.fi << ' ' << pr.se << '\n';
        }
    }
}

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