Submission #873753

#	Time	Username	Problem	Language	Result	Execution time	Memory
873753		maxFedorchuk	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1569 ms	106068 KiB

treearray

#include <bits/stdc++.h>
using namespace std;

const long long MX=2e5+10;
const long long lg=22;

vector < long long > mas[MX];
set < long long > mlca[MX];
set < long long > mel[MX];
long long prd[lg][MX]={0};

long long bbb[MX];
long long el[MX];
long long tin[MX];
long long tou[MX];
long long timer=0;

void DFS(long long zar,long long mun)
{
    timer++;
    tin[zar]=timer;

    prd[0][zar]=mun;
    for(long long i=1;i<lg;i++)
    {
        prd[i][zar]=prd[i-1][prd[i-1][zar]];
    }

    for(auto u:mas[zar])
    {
        if(u!=mun)
        {
            DFS(u,zar);
        }
    }

    timer++;
    tou[zar]=timer;

    return;
}


long long fun_lca(long long a,long long b)
{
    if(tin[a]<=tin[b] && tou[b]<=tou[a])
    {
        return a;
    }

    if(tin[b]<=tin[a] && tou[a]<=tou[b])
    {
        return b;
    }

    for(long long i=lg-1;i>=0;i--)
    {
        if(tin[prd[i][a]]<=tin[b] && tou[b]<=tou[prd[i][a]])
        {

        }
        else
        {
            a=prd[i][a];
        }
    }

    return prd[0][a];
}

long long n,m,q;

void upd(long long pos,long long zn)
{
    mel[el[pos]].erase(pos);
    el[pos]=zn;
    mel[el[pos]].insert(pos);

    if(pos!=1)
    {
        mlca[bbb[pos-1]].erase(pos-1);
        bbb[pos-1]=fun_lca(el[pos-1],el[pos]);
        mlca[bbb[pos-1]].insert(pos-1);
    }

    if(pos!=m)
    {
        mlca[bbb[pos]].erase(pos);
        bbb[pos]=fun_lca(el[pos],el[pos+1]);
        mlca[bbb[pos]].insert(pos);
    }

    return;
}

void get_zn(long long l,long long r,long long zn)
{
    auto it1=mel[zn].lower_bound(l);
    auto it2=mlca[zn].lower_bound(l);

    if(it1!=mel[zn].end() && (*it1)<=r)
    {
        cout<<(*it1)<<" "<<(*it1)<<"\n";
    }
    else
    {
        if(it2!=mlca[zn].end() && (*it2)<r)
        {
            cout<<(*it2)<<" "<<(*it2)+1<<"\n";
        }
        else
        {
            cout<<"-1 -1\n";
        }
    }

    return;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin>>n>>m>>q;

    long long a,b,c;
    for(long long i=1;i<n;i++)
    {
        cin>>a>>b;
        mas[a].push_back(b);
        mas[b].push_back(a);
    }

    tin[0]=0;
    DFS(1,0);
    timer++;
    tou[0]=timer;

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

    for(long long i=1;i<=m;i++)
    {
        upd(i,el[i]);
    }

    while(q--)
    {
        long long zp;
        cin>>zp;

        if(zp==1)
        {
            cin>>a>>b;
            upd(a,b);
        }
        else
        {
            cin>>a>>b>>c;
            get_zn(a,b,c);
        }
    }

    return 0;
}

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