Submission #1308332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308332		mohmed_gado	Birthday gift (IZhO18_treearray)	C++20	0 / 100	3 ms	24080 KiB

treearray

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int MAXN=200000+5;
const int LOG=20;

vector<int>adj[MAXN];
int up[MAXN][LOG],deth[MAXN];
int a[MAXN];
int seg[4*MAXN];
int n, m, q;
//lca
void dfs(int v, int p) {
    up[v][0]=p;
    for (int i=1;i<LOG;i++)
        up[v][i]=up[ up[v][i-1]][i-1];

    for (int u:adj[v]){
        if (u==p){
        	continue;
        } 
        deth[u] = deth[v] + 1;
        dfs(u, v);
    }
}
int lca(int u, int v) {
    if (u==0){
     return v;	
    }
    if (v==0){
    	return u;
    } 
    if (deth[u]<deth[v]){
    	swap(u, v);
    } 
    int diff=deth[u]-deth[v];
    for (int i=0;i<LOG;i++)
        if (diff&(1<<i))
            u=up[u][i];
            
    if (u == v) return u;

    for (int i=LOG-1;i>=0;i--) {
        if (up[u][i]!=up[v][i]) {
            u=up[u][i];
            v=up[v][i];
        }
    }
    return up[u][0];
}
//sg
void build(int idx, int l, int r) {
    if (l==r) {
        seg[idx] = a[l];
        return;
    }
    int mid=(l+r)/2;
    build(idx*2,l,mid);
    build(idx*2+1,mid+1,r);
    seg[idx]=lca(seg[idx*2],seg[idx*2+1]);
}
int query(int idx,int l,int r,int ql, int qr) {
    if (qr<l or ql>r) return 0;
    if (ql<=l and r<=qr) return seg[idx];
    int mid=(l+r)/2;
    return lca(
        query(idx*2,l,mid,ql,qr),
        query(idx*2+1,mid+1,r,ql,qr)
    );
}
void update(int idx, int l, int r, int pos, int val) {
    if (l == r) {
        seg[idx] = val;
        return;
    }
    int mid = (l + r) / 2;
    if (pos <= mid) update(idx * 2, l, mid, pos, val);
    else update(idx * 2 + 1, mid + 1, r, pos, val);
    seg[idx] = lca(seg[idx * 2], seg[idx * 2 + 1]);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>m>>q;
    for (int i=1;i<=n;i++)
        adj[i].clear();

    for (int i=0;i<n-1;i++) {
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i=1;i<=m;i++)
        cin>>a[i];

    dfs(1,0);
    build(1,1,m);

    while (q--) {
        int x;
        cin>>x;
        if (x==1) {
            int pos,v;
            cin>>pos>>v;
            a[pos]=v;
            update(1,1,m,pos,v);
        }
        else{
            int l,r,v;
            cin>>l>>r>>v;
            int ansX=-1,ansY=-1;
            int lo=l,hi=r;
            while (lo<=hi) {
                int mid=(lo+hi)>>1;
                if (query(1,1,m,l,mid)==v) {
                    ansX=l;
                    ansY=mid;
                    hi=mid-1;
                } else {
                    lo=mid+1;
                }
            }
            /*
            for (int x=l;x<=r;x++) {
                int cur=a[x];
                for (int y=x;y<=r;y++) {
                    if (y>x)
                        cur=lca(cur,a[y]);
                    if (cur==v){
                        ansX=x;
                        ansY=y;
                        goto done;
                    }
                }
            }
            done:;
            */
            if (ansX==-1){
            	cout<<"-1 -1\n";
            }
                
            else{
             cout<<ansX<<" "<<ansY<<endl;	
            }
        }
    }
}

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