Submission #1162654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162654		m5588ohammed	Birthday gift (IZhO18_treearray)	C++20	100 / 100	828 ms	89940 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[200001];
int t[21][200001],level[200001],arr[200001];
int n,q,m;
ordered_set st1[200001],st2[200001];
void spars(){
    for(int bt=1;bt<=20;bt++){
        for(int i=1;i<=n;i++) t[bt][i]=t[bt-1][t[bt-1][i]];
    }
}
int LCA(int a,int b){
    int la=level[a],lb=level[b],k=abs(la-lb);
    if(la<lb) swap(a,b);
    for(int bt=20;bt>=0;bt--){
        if(k>=(1<<bt)){
            a=t[bt][a];
            k-=(1<<bt);
        }
    }
    
    if(a==b) return a;
    for(int bt=20;bt>=0;bt--){
      if(a!=b&&t[bt][a]!=t[bt][b]){
            a=t[bt][a];
            b=t[bt][b];
      }
    }
    return t[0][a];
}
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) r=mid-1;
        else l=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) r=mid-1;
        else l=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);
    spars();
    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<<" "<<-1<<endl;
        }
    }
    return 0;
}

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