Submission #1162649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162649		m5588ohammed	Birthday gift (IZhO18_treearray)	C++20	0 / 100	4094 ms	34112 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define mod 1000000007
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

vector <int> v[100001];
int t[21][100001],level[100001],arr[200001];
int n,q,m;
ordered_set st1[200001],st2[200001];
int LCA(int a,int b){
    int la=level[a],lb=level[b],A=a,B=b;
    if(la<lb){
        swap(la,lb);
        swap(a,b);
        swap(A,B);
    }
    int k=la-lb;
    for(int i=20;i>=0;i--){
        if(k-(1<<i)>=0){
            k-=(1<<i);
            a=t[i][a];
        }
    }
    if(a==b) return level[A]-level[B];
    for(int i=20;i>=0;i--){
        if(t[i][a]!=t[i][b]){
            a=t[i][a];
            b=t[i][b];
        }
    }
    return level[A]+level[B]-level[t[0][a]]*2;
}
void dfs(int i,int last){
    level[i]=level[last]+1;
    t[0][i]=last;
    for(int j:v[i]) if(j!=last) dfs(j,i);
    return;
}
void ers(int i){
    st1[arr[i]].erase(i);
    if(i!=1) st2[LCA(arr[i],arr[i-1])].erase(i-1);
    if(i!=m) st2[LCA(arr[i],arr[i+1])].erase(i);
    return;
}
void ins(int i){
    st1[arr[i]].insert(i);
    if(i!=1) st2[LCA(arr[i],arr[i-1])].insert(i-1);
    if(i!=m) st2[LCA(arr[i],arr[i+1])].insert(i);
    return;
}
int find1(int l1,int r1,int x){
    int l=0,r=st1[x].size(),ans=-1;
    while(l<=r){
        int mid=(l+r)/2;
        int idx=*st1[x].find_by_order(mid);
        if(l1<=idx&&idx<=r1) ans=idx;
        if(l1<=idx) l=mid-1;
        else r=mid+1;
    }
    return ans;
}
int find2(int l1,int r1,int x){
    int l=0,r=st2[x].size(),ans=-1;
    while(l<=r){
        int mid=(l+r)/2;
        int idx=*st2[x].find_by_order(mid);
        if(l1<=idx&&idx<=r1) ans=idx;
        if(l1<=idx) l=mid-1;
        else r=mid+1;
    }
    return ans;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m>>q;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1,0);
    for(int i=1;i<=m;i++){
        cin>>arr[i];
        st1[arr[i]].insert(i);
    }
    for(int i=1;i<=m-1;i++){
        st2[LCA(arr[i],arr[i+1])].insert(i);
    }
    while(q--){
        int tp;
        cin>>tp;
        if(tp==1){
            int idx,val;
            cin>>idx>>val;
            ers(idx);
            arr[idx]=val;
            ins(idx);
        }
        else{
            int l,r,val;
            cin>>l>>r>>val;
            int num1=find1(l,r,val),num2=find2(l,r-1,val);
            if(num1!=-1) cout<<num1<<" "<<num1<<endl;
            else if(num2!=-1) cout<<num2<<" "<<num2+1<<endl;
            else cout<<-1<<endl;
        }
    }
    return 0;
}

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