Submission #492394

#	Time	Username	Problem	Language	Result	Execution time	Memory
492394		generic_placeholder_name	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1144 ms	72876 KiB

treearray

#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,fma")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/rope>
 
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define gcd __gcd
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rep(i, n) for (int i=0; i<(n); i++)
#define rep1(i, n) for (int i=1; i<=(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl "\n"
 
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
template<typename T, typename cmp = less<T>>
using ordered_set=tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;
 
constexpr int N = 2e5 + 5;
constexpr int K = 18;
 
vi adj[N];
int dep[N];
int par[N][K + 1];
 
void dfs(int u = 0, int p = -1){
    rep1(i, K) par[u][i] = par[par[u][i - 1]][i - 1];
    for(int v: adj[u]) if(v != p) {
        par[v][0] = u;
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}
 
int lca(int u, int v) {
    if(u == v) return u;
    if(dep[u] > dep[v]) swap(u, v);
    for(int i = K; ~i; i--) {
        if(dep[par[v][i]] >= dep[u]) {
            v = par[v][i];
        }
    }
    if(u == v) return u;
    for(int i = K; ~i; i--) {
        if(par[u][i] != par[v][i]) {
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}
 
int a[N];
set<int> id[N][2];
 
int32_t main() {
    fastio;
    int n, m, q; cin >> n >> m >> q;
    rep(_, n - 1) {
        int u, v; cin >> u >> v; --u, --v;
        adj[u].eb(v);
        adj[v].eb(u);
    }
    dfs();
    rep(i, m) cin >> a[i], --a[i];
    rep(i, m) id[a[i]][0].insert(i);
    rep(i, m - 1) id[lca(a[i], a[i + 1])][1].insert(i);
    while(q--) {
        int t; cin >> t;
        if(t == 1) {
            int i, x; cin >> i >> x; --i, --x;
            if(i + 1 < m) {
                id[lca(a[i], a[i + 1])][1].erase(i);
                id[lca(x, a[i + 1])][1].insert(i);
            }
            if(i > 0) {
                id[lca(a[i - 1], a[i])][1].erase(i - 1);
                id[lca(a[i - 1], x)][1].insert(i - 1);
            }
            id[a[i]][0].erase(i);
            id[x][0].insert(i);
            a[i] = x;
        }
        else {
            int l, r, v; cin >> l >> r >> v; --l, --r, --v;
            auto x = id[v][0].lower_bound(l);
            auto y = id[v][1].lower_bound(l);
            if(x != id[v][0].end() && *x <= r) cout << 1 + *x << ' ' << 1 + *x << endl;
            else if(y != id[v][1].end() && *y < r) cout << 1 + *y << ' ' << 2 + *y << endl;
            else cout << "-1 -1\n";
        }
    }
}

Compilation message (stderr)

treearray.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization("unroll-loops")
      |

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