Submission #85338

#	Time	Username	Problem	Language	Result	Execution time	Memory
85338		ToadDaveski	Birthday gift (IZhO18_treearray)	C++14	0 / 100	23 ms	24056 KiB

treearray

#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector <ll> v[200001];
ll p[32][200001],tin[200001],tout[200001],a[200001],timer;
bool isA(ll x,ll y)
{
    if (tin[x]<=tin[y] && tout[x]>=tout[y])
        return true;
    return false;
}
void dfs(ll x,ll pr)
{
    tin[x]=++timer;
    p[0][x]=pr;
    for(ll i=1;i<=30;i++)
        p[i][x]=p[i-1][p[i-1][x]];
    for(ll to : v[x])
        if (to!=pr)
             dfs(to,x);
    tout[x]=++timer;
}
ll lca(ll x,ll y)
{
    if (isA(x,y))
        return x;
    if (isA(y,x))
        return y;
    while(!isA(p[0][x],y))
    {
        ll i;
        for(i=30;i>=0;i--)
            if (!isA(p[i][x],y)) break;
        x=p[i][x];
    }
    return p[0][x];
}
set <ll> ans[200001],answ[200001];
set <ll > :: iterator it;
int main()
{
    ll n,m,q,i,j;
    cin>>n>>m>>q;
    for(i=1;i<=n-1;i++)
    {
        ll x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,1);
    for(i=1;i<=m;i++)
        cin>>a[i];
    for(i=1;i<m;i++)
    {
        answ[a[i]].insert(i);
        ans[lca(a[i],a[i+1])].insert(i);
    }
    ans[a[m]].insert({m,m});
    for(i=1;i<=q;i++)
    {
        ll type;
        cin>>type;
        if (type==1)
        {
            ll x,y;
            cin>>x>>y;
            answ[a[x]].erase(x);
            if (x!=m) ans[lca(a[x],a[x+1])].erase(x);
            answ[y].insert(x);
            if (x!=m) ans[lca(y,a[x+1])].insert(x);
            a[x]=y;
        }
        else
        {
            ll l,r,x;
            cin>>l>>r>>x;
            it=ans[x].lower_bound(l);
            if (it!=ans[x].end() && (*it)+1<=r)
            {
                cout<<(*it)<<" "<<(*it)+1<<endl;
                continue;
            }
            it=answ[x].lower_bound(l);
            if (it!=answ[x].end() && (*it)<=r)
            {
                cout<<(*it)<<" "<<(*it)<<endl;
                continue;
            }
            cout<<-1<<" "<<-1<<endl;
        }
    }
    return 0;
}

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:42:16: warning: unused variable 'j' [-Wunused-variable]
     ll n,m,q,i,j;
                ^

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