Submission #1242198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242198		Amaarsaa	Birthday gift (IZhO18_treearray)	C++20	0 / 100	3 ms	5188 KiB

treearray

#include<bits/stdc++.h>

using namespace std;
using ll =long long;
const ll N = 2e5 + 2;

vector < ll > adj[N];
ll anc[20][N], tin[N], tout[N], timer = 0;
ll a[N];

bool is_ancestor(ll x, ll y) {
    if ( tin[x] <= tin[y] && tout[y] <= tout[x]) return 1;
    return 0;
}

ll LCA(ll x, ll y) {
    if ( is_ancestor(x, y)) return x;
    if ( is_ancestor(y, x)) return y;

    for (int i = 18; i >= 0; i --) {
        if ( !is_ancestor(anc[i][x], y)) x =anc[i][x];
    }

    return anc[0][x];
}



void Go(ll node, ll par) {
    timer ++;
    anc[0][node] = par;
    tin[node] = timer;
    for (int i = 1; i <= 18; i ++) anc[i][node] = anc[i - 1][anc[i - 1][node]];
    for (ll nxt : adj[node]) {
        if ( nxt == par) continue;
        Go(nxt, node);
    }
    timer ++;
    tout[node] = timer;
}

ll T[4 * N];

void Build(ll p, ll lo, ll hi) {
    if ( lo == hi) {
        T[p] = a[lo];
        return ;
    }
    ll mid = (lo + hi)/2;

    Build(2 * p, lo, mid);
    Build(2 * p + 1, mid + 1, hi);

    T[p]= LCA(T[2 * p], T[2 * p + 1]);
    return ;
}

ll ans_lo , ans_hi, ans_p;
ll Find(ll p, ll lo, ll hi, ll l, ll r, ll x) {
    if ( lo > r || l > hi) return -1;
    if ( l <= lo && hi <=r ) {
        if ( is_ancestor(T[p], x)) {
            ans_lo = max(lo, l);
            ans_hi = min(hi, r);
            ans_p = p;
        }
        return T[p];
    }
    ll mid = (lo + hi)/2, lef, rig;
    lef =Find(2 * p, lo, mid, l, r, x);
    rig =Find(2 * p + 1, mid + 1, hi, l, r, x);

    if ( lef == -1) return rig;
    if ( rig == -1) return lef;
    ll ance = LCA(lef, rig);
    if ( is_ancestor(ance, x) && !is_ancestor(lef, x) && !is_ancestor(rig, x)) {
        ans_lo = lo;
        ans_hi = hi;
        ans_p = p;
    }
    return lef;
}

void Update(ll p, ll lo, ll hi , ll x, ll y){
    if ( lo == hi) {
        T[p] = y;
        return ;
    }

    ll mid = (lo + hi)/2;

    if ( x <= mid) Update(2 * p, lo, mid, x, y);
    else Update(2 * p + 1, mid + 1, hi, x, y);

    T[p] = LCA(T[2 * p], T[2 * p + 1]);
}

int main() {
    ll n, m, r, s, t,q,mid,  i, ans, lo, hi, mx_ind, mx, x, y, j;

    cin >> n >> m >> q;

    for (i = 1; i < n; i++) {
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    Go(1, 1);

    for (i = 1; i <= m; i ++) {
        cin >> a[i];
    }

    Build(1, 1, m);

    //cout<< LCA(3, 2) << endl;
    while (q --) {
        cin >> x;
        if ( x == 2) {
            cin >> lo >> hi >> x;
            ll Lo, Hi;
            Lo = lo;
            Hi = hi;
            ans_lo = ans_hi =ans_p = -1;
            ll r= Find(1, 1, m, lo, hi, x);
            if ( ans_p == -1) {
                cout << "-1 -1" << endl;
                continue;
            } 

            lo = ans_lo;
            hi = ans_hi;
            mid = (lo + hi)/2;
            r = mid;
            for (i = 20; i >= 0; i --) {
                ll node = Find(1, 1, m, max(lo, r - (1<< i)), r, 0); 
                if ( !is_ancestor(node, x)) {
                    r = max(lo, r - (1<< i));
                }
            }
            ll ANS_LO =r;
            r = mid + 1;
            for (i = 20; i >= 0; i --) {
                ll node = Find(1, 1, m, r, min(hi, r + (1<< i)), 0); 
                if ( !is_ancestor(node, x)) {
                    r = min(hi, r + (1<< i));
                }
            }
            cout << ANS_LO << " " << r<< endl;
        }
        else {
            cin >> x >> y;
            a[x] = y;
            Update(1, 1, m, x, y);
        }
    }
}

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