Submission #1242252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242252		Amaarsaa	Birthday gift (IZhO18_treearray)	C++20	0 / 100	2 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 Find(ll p, ll lo, ll hi, ll l, ll r) {
    if ( lo > r || l > hi) return -1;
    if ( l <= lo && hi <=r ) {
        return T[p];
    }
    ll mid = (lo + hi)/2, lef, rig;
    lef =Find(2 * p, lo, mid, l, r);
    rig =Find(2 * p + 1, mid + 1, hi, l, r);

    if ( lef == -1) return rig;
    if ( rig == -1) return lef;
    ll ance = LCA(lef, rig);
    return ance;
}

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, lf, rg,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 >> lf >> rg >> x;
            if (  !is_ancestor(Find(1, 1, m, lf, rg), x)) {
                cout << "-1 -1" << endl;
                continue;
            }
            lo = lf;
            hi = rg + 1;
            while (lo < hi) {
                mid = (lo + hi)/2;
               // cout << mid << "  " << x << " " << Find(1, 1, m, lf, mid) << endl;
                if ( !is_ancestor(Find(1, 1, m, lf, mid), x)) lo = mid + 1;
                else hi = mid;
            }

            ll ANS = lo;
            hi = lo + 1;
            lo = lf;
            while (lo < hi) {
                mid = (lo + hi)/2;
                if ( !is_ancestor(Find(1, 1, m, mid, ANS), x)) lo = mid + 1;
                else hi = mid;
            }
            cout <<lo<<" " <<  ANS<< 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