Submission #579996

#	Time	Username	Problem	Language	Result	Execution time	Memory
579996		loggerr	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1169 ms	85596 KiB

treearray

#include "bits/stdc++.h"

using namespace std;
using ll = int;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vpl = vector<pll>;
using ld = long double;
using str = string;
using big_int = __int128_t;

const ld eps = 1e-7;
const ld PI = acos(-1);

#define all(c) (c).begin(), (c).end()
#define rall(c) ((c).rbegin()), ((c).rend())
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define fast ios_base::sync_with_stdio(0); cin.tie(0)
#define forn(i, n) for (ll i = 0; i < n; ++i)
#define sz(a) (ll)a.size()
#define endl '\n'
#define u_map unordered_map
#define mset multiset
//#define x first
//#define y second

#ifdef ONLINE_JUDGE
#define debug(x);
#else
#define debug(x) cerr << #x << ": " << x << endl;
#endif

str IO[2] = {"NO\n", "YES\n"};
str io[2] = {"no\n", "yes\n"};
str Io[2] = {"No\n", "Yes\n"};
//
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnd(1232423);

template<class T> bool inmin(T& x_, T y_) {return y_ < x_ ? (x_ = y_, true) : false;}
template<class T> bool inmax(T& x_, T y_) {return y_ > x_ ? (x_ = y_, true) : false;}

//const ll Mod = 1e9 + 7;
const ll Mod = 998244353;
//const ll Mod = 1e9 + 9;
//const ll Mod = 1234567891;
//const ll INF = 1e18;

template<class T> void add(T& x_, T y_) { x_ = (x_ + y_) % Mod; };
template<class T> void sub(T& x_, T y_) { x_ = (x_ + Mod - y_) % Mod; };
template<class T> void mul(T& x_, T y_) { x_ = (x_ * y_) % Mod; };

const ll Maxn = 2e5 + 10;
const ll Lg = 22;

vll gr[Maxn];
ll up[Lg][Maxn];
ll d[Maxn];

void dfs(ll v, ll p) {
    up[0][v] = p;
    d[v] = d[p] + 1;
    for (ll adj : gr[v]) {
        if (adj == p) continue;
        dfs(adj, v);
    }
}

ll la(ll v, ll k) {
    forn (i, Lg) {
        if (k & (1 << i))
            v = up[i][v];
    }
    return v;
}

ll lca(ll u, ll v) {
    if (d[u] < d[v]) swap(u, v);
    u = la(u, d[u] - d[v]);
    if (u == v)
        return u;
    for (ll i = Lg - 1; i >= 0; --i) {
        if (up[i][u] == up[i][v]) continue;
        u = up[i][u], v = up[i][v];
    }
    return up[0][u];
}

set<ll> dcV[Maxn], dcL[Maxn];

inline void solve() {
    ll n, m, q;
    cin >> n >> m >> q;
    forn (i, n - 1) {
        ll u, v;
        cin >> u >> v;
        --u, --v;
        gr[u].pb(v), gr[v].pb(u);
    }
    dfs(0, 0);
    for (ll i = 1; i < Lg; ++i) {
        forn (v, Maxn) {
            up[i][v] = up[i - 1][up[i - 1][v]];
        }
    }
    vll que(m);
    forn (i, m) {
        cin >> que[i];
        --que[i];
        dcV[que[i]].insert(i);
        if (i) {
            dcL[lca(que[i - 1], que[i])].insert(i - 1);
        }
    }
    while (q--) {
        ll tp;
        cin >> tp;
        if (tp == 1) {
            ll pos, v;
            cin >> pos >> v;
            --pos, --v;
            dcV[que[pos]].erase(pos);
            if (pos) dcL[lca(que[pos], que[pos - 1])].erase(pos - 1);
            if (pos < m - 1) dcL[lca(que[pos], que[pos + 1])].erase(pos);
            que[pos] = v;
            dcV[que[pos]].insert(pos);
            if (pos) dcL[lca(que[pos], que[pos - 1])].insert(pos - 1);
            if (pos < m - 1) dcL[lca(que[pos], que[pos + 1])].insert(pos);
            continue;
        }
        ll l, r, v;
        cin >> l >> r >> v;
        --l, --r, --v;
        auto id = dcV[v].lower_bound(l);
        if (id != dcV[v].end() && *id <= r) {
            cout << *id + 1 << ' ' << *id + 1 << endl;
            continue;
        }
        --r;
        id = dcL[v].lower_bound(l);
        if (id != dcL[v].end() && *id <= r) {
            cout << *id + 1 << ' ' << *id + 2 << endl;
            continue;
        }
        cout << -1 << ' ' << -1 << endl;
    }
    return;
}

int main() {
    fast;
    //cout << fixed << satprecision(10);
    ll test;
    test = 1;
    //cin >> test;
    for (ll id = 0; id < test; ++id) solve();
    return 0;
}

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