Submission #607713

#	Time	Username	Problem	Language	Result	Execution time	Memory
607713		Loki_Nguyen	Birthday gift (IZhO18_treearray)	C++14	56 / 100	1189 ms	119280 KiB

treearray

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll maxN=3e5+1;
vector<ll> g[maxN];
ll par[maxN][20],h[maxN],p[maxN];
void dfs(ll u, ll pp)
{
    for(auto v:g[u])
    {
        if(v!=pp)
        {
            p[v]=u;
            par[v][0]=u;
            h[v]=h[u]+1;
            for(int i=1;i<=18;i++) par[v][i]=par[par[v][i-1]][i-1];
            dfs(v,u);
        }
    }
}
ll LCA(ll u, ll v)
{
    if(h[u]<h[v]) swap(u,v);
    ll log=log2(h[u])+1;
    for(int i=log;i>=0;i--)
    {
        if(h[par[u][i]]>=h[v]) u=par[u][i];
    }
    if(u==v) return u;
    for(int i=log;i>=0;i--)
    {
        if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
    }
    return p[u];
}
ll n,m,q;
set<int> s[maxN],t[maxN];
ll a[maxN];
#define pb push_back
ll lca[maxN];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >>n>>m>>q;
    for(int i=1;i<n;i++)
    {
        ll u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    p[1]=1;
    for(int i=0;i<=18;i++) par[1][i]=1;
    dfs(1,0);
    for(int i=1;i<=m;i++) cin >> a[i],s[a[i]].insert(i);
    for(int i=1;i<m;i++)
    {
        lca[i]=LCA(a[i],a[i+1]);
        t[lca[i]].insert(i);
    }
    //for(auto z:t[1]) cout << z<<' ';
    //cout << '\n';
    for(int i=1;i<=q;i++)
    {
        ll type,l,r,k;
        cin >> type;
        if(type==1)
        {
            cin >> l >> r;
            s[a[l]].erase(l);
            t[lca[l]].erase(l);
            t[lca[l-1]].erase(l-1);
            a[l]=r;
            s[a[l]].insert(l);
            if(l<n)
            {
 
                lca[l]=LCA(a[l],a[l+1]);
                t[lca[l]].insert(l);
            }
            if(l>1)
            {
 
                lca[l-1]=LCA(a[l-1],a[l]);
                t[lca[l-1]].insert(l-1);
            }
        }
        else
        {
            cin >> l >> r >> k;
            auto x=s[k].lower_bound(l);
            if(*x<=r&&x!=s[k].end())
            {
 
                cout << *x <<' '<<*x<<'\n';
                continue;
            }
            else
            {
                x=t[k].lower_bound(l);
                if(*x<=r-1&&x!=t[k].end())
                {
                    cout << *x<<' '<<*x+1<<'\n';
 
                }
                else
                {
                    cout <<-1<< ' '<<-1<<'\n';
                }
            }
        }
    }
 
}

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