Submission #1283804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283804		Faisal_Saqib	Birthday gift (IZhO18_treearray)	C++20	100 / 100	1066 ms	71716 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+100,lg=18;
vector<int> ma[N];
int a[N],h[N],par[N][lg];
void dfs(int x,int p=0)
{
    par[x][0]=p;
    for(int j=1;j<lg;j++)
    {
        par[x][j]=par[par[x][j-1]][j-1];
    }
    for(auto y:ma[x])
    {
        if(y!=p){h[y]=h[x]+1;dfs(y,x);}
    }
}
int lca(int x,int y)
{
    if(x==0)return y;
    if(h[x]<h[y])swap(x,y);
    for(int j=lg-1;j>=0;j--)
    {
        if(h[par[x][j]]>=h[y])
        {
            x=par[x][j];
        }
    }
    if(x==y)return x;
    for(int j=lg-1;j>=0;j--)
    {
        if(par[x][j]!=par[y][j])
        {
            x=par[x][j];
            y=par[y][j];
        }
    }
    return par[x][0];
}
int main()
{
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        ma[x].push_back(y);
        ma[y].push_back(x);
    }
    h[1]=1;
    dfs(1);
    set<pair<int,int>> pos1,pos2;
    a[0]=1;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i];
        pos1.insert({a[i],i});
        pos2.insert({lca(a[i-1],a[i]),i});
    }
    while(q--)
    {
        int type;
        cin>>type;
        if(type==1)
        {
            int p,v;
            cin>>p>>v;
            pos1.erase({a[p],p});
            pos2.erase({lca(a[p-1],a[p]),p});
            pos2.erase({lca(a[p+1],a[p]),p+1});
            a[p]=v;
            pos1.insert({a[p],p});
            pos2.insert({lca(a[p-1],a[p]),p});
            pos2.insert({lca(a[p+1],a[p]),p+1});
        }
        else{
            int l,r,v;
            cin>>l>>r>>v;
            auto it=pos1.lower_bound({v,l});
            if(it!=end(pos1) and it->first==v and it->second<=r)
            {
                cout<<it->second<<' '<<it->second<<endl;
            }
            else{
                it=pos2.lower_bound({v,l+1});
                if(it!=end(pos2) and it->first==v and it->second<=r)
                {
                    cout<<it->second-1<<' '<<it->second<<endl;
                }
                else
                {
                    cout<<-1<<' '<<-1<<endl;
                }
            }
        }
    }
}

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