Submission #492370

#	Time	Username	Problem	Language	Result	Execution time	Memory
492370		phamhoanghiep	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1251 ms	62232 KiB

treearray

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int maxn=2e5+5;
int n,m,q;
vector<int> AdjList[maxn];
int up[maxn][20];
int in[maxn];
int out[maxn];
int arr[maxn];
int timer=0;
bool ancestor(int a, int b) {
    if(!a) return 1;
    if(!b) return 0;
    return in[a]<=in[b]&&out[a]>=out[b];
}
void dfs(int s, int p=0) {
    in[s]=++timer;
    //cout<<"in "<<s<<" = "<<in[s]<<endl;
    up[s][0]=p;
    for(int i=1 ; i<20 ; i++) up[s][i]=up[up[s][i-1]][i-1];
    for(int u: AdjList[s]) {
        if(u==p) continue;
        dfs(u,s);
    }
    out[s]=timer;
    //cout<<"out "<<s<<" = "<<out[s]<<endl;
}
int lca(int u, int v) {
    //cout<<"lca "<<u<<" "<<v<<" = ";
    if(ancestor(u,v)) return u;
    if(ancestor(v,u)) return v;
    for(int i=19 ; i>=0 ; i--) {
        if(!ancestor(up[u][i],v)) u=up[u][i];
    }
    //cout<<up[u][0]<<endl;
    return up[u][0];
}
// build segment tree
int lc[maxn]; // between two adjacent in array
set<ii> S;
set<ii> V;
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1 ; i<n ; i++) {
        int u,v;
        cin>>u>>v;
        AdjList[u].push_back(v);
        AdjList[v].push_back(u);
    }
    dfs(1);
    for(int i=1 ; i<=m ; i++) {
        cin>>arr[i];
        V.insert(ii(arr[i],i));
    }
    for(int i=1 ; i<m ; i++) {
        lc[i]=lca(arr[i],arr[i+1]);
        S.insert(ii(lc[i],i));
        // cout<<"S "<<lc[i]<<" "<<i<<endl;
    }
    while(q--) {
        int type,l,r,v;
        cin>>type;
        if(type==2) {
            cin>>l>>r>>v;
            auto it1=V.lower_bound(ii(v,l));
            auto it=S.lower_bound(ii(v,l));
            if(it1!=V.end()) {
                if((*it1).first==v&&(*it1).second<=r) {
                    cout<<(*it1).second<<' '<<(*it1).second<<'\n';
                    continue;
                }
            }
            if(m==1) {
                cout<<"-1 -1\n";
                continue;
            }
            if(it==S.end()) {
                cout<<"-1 -1\n";
                continue;
            }
            else {
                //cout<<"find = "<<(*it).first<<" "<<(*it).second<<endl;
                if((*it).first!=v) {
                    cout<<"-1 -1\n";
                    continue;
                }
                else if((*it).second>=r) {
                    cout<<"-1 -1\n";
                    continue;
                }
                else cout<<(*it).second<<' '<<(*it).second+1<<'\n';
            }
        }
        else {
            cin>>l>>v;
            auto it1=V.find(ii(arr[l],l));
            V.erase(it1);
            arr[l]=v;
            V.insert(ii(arr[l],l));
            if(l!=m) {
                auto it=S.find(ii(lc[l],l));
                S.erase(it);
                lc[l]=lca(arr[l],arr[l+1]);
                //cout<<"lc "<<l<<" = "<<lc[l]<<endl;
                S.insert(ii(lc[l],l));
            }
            if(l!=1) {
                auto it=S.find(ii(lc[l-1],l-1));
                S.erase(it);
                lc[l-1]=lca(arr[l-1],arr[l]);
                //cout<<"lc "<<l-1<<" = "<<lc[l-1]<<endl;
                S.insert(ii(lc[l-1],l-1));
            }
        }
    }
}

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