Submission #1307144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307144		jahongir	Birthday gift (IZhO18_treearray)	C++20	56 / 100	483 ms	327680 KiB

treearray

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

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

#define pb push_back
#define all(a) a.begin(),a.end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef unsigned long long ull;
typedef vector<int> vi;


const int mxn = 2e5+1, lg2 = 18;
vector<int> g[mxn];
int suc[mxn][lg2];
int tin[mxn],tout[mxn],tim=0;

int arr[2][mxn];
set<pii> st[2][1<<19];


void pre_dfs(int u, int p){
    suc[u][0] = p;
    tin[u] = ++tim;
    for(int i = 1; i < lg2; i++)
        suc[u][i] = suc[suc[u][i-1]][i-1];

    for(auto v : g[u]) if(v!=p)
        pre_dfs(v,u);
    
    tout[u] = tim;
}

bool is_anc(int u, int v){
    return tin[u]<=tin[v] && tout[v]<=tout[u];
}

int get_lca(int u, int v){
    if(is_anc(u,v)) return u;
    if(is_anc(v,u)) return v;
    for(int i = lg2-1; i >= 0; i--)
        if(!is_anc(suc[u][i],v))
            u = suc[u][i];
    return suc[u][0];
}


void build(int i, short t, int l, int r){
    if(l==r){st[t][i].insert({arr[t][l],l}); return;}
    int m = (l+r)>>1;
    build(i<<1,t,l,m);
    build(i<<1|1,t,m+1,r);

    st[t][i].insert(all(st[t][i<<1]));
    st[t][i].insert(all(st[t][i<<1|1]));

}

void update(int i, short t, int l, int r, int k, int val){
    st[t][i].erase({arr[t][k],k});
    st[t][i].insert({val,k});
    if(l==r) return;

    int m = (l+r)>>1;
    if(k <= m) update(i<<1,t,l,m,k,val);
    else update(i<<1|1,t,m+1,r,k,val);
}

int query(int i, short t, int l, int r, int s, int e, int val){
    if(r < s || l > e) return -1;
    if(s <= l && r <= e){
        auto it = st[t][i].lower_bound(make_pair(val,0));
        if(it!=st[t][i].end() && it->first == val) return it->second;
        else return -1;
    }
    int m = (l+r)>>1;
    int r1 = query(i<<1,t,l,m,s,e,val);
    if(r1==-1) return query(i<<1|1,t,m+1,r,s,e,val);
    else return r1;
}



void solve(){
    int n,m,q; cin >> n >> m >> q;

    for(int i = 1; i < n; i++){
        int u,v; cin >> u >> v;
        g[u].pb(v); g[v].pb(u);
    }

    pre_dfs(1,1);

    for(int i = 1; i <= m; i++){
        cin >> arr[0][i];
        if(i>1) arr[1][i-1] = get_lca(arr[0][i-1],arr[0][i]);
    }


    build(1,0,1,m);
    if(m>1) build(1,1,1,m-1);

    for(int _ = 0; _ < q; _++){
        char t; cin >> t;
        if(t=='1'){
            int i,val; cin >> i >> val;
            update(1,0,1,m,i,val);
            arr[0][i] = val;
            if(m>1){
                if(i<m){
                    val = get_lca(arr[0][i],arr[0][i+1]);
                    update(1,1,1,m-1,i,val);
                    arr[1][i] = val;
                }
                if(i>1){
                    val = get_lca(arr[0][i-1],arr[0][i]);
                    update(1,1,1,m-1,i-1,val);
                    arr[1][i-1] = val;
                }
            }
        }else{
            int l,r,v; cin >> l >> r >> v;

            int r1 = query(1,0,1,m,l,r,v);
            if(r1==-1){
                if(l<r){
                    r1 = query(1,1,1,m-1,l,r-1,v);
                    if(r1==-1) cout << "-1 -1\n";
                    else cout << r1 << ' ' << r1+1 << '\n';
                }else cout << "-1 -1\n";
            }else cout << r1 << ' ' << r1 << '\n';
        }
    }

}   


signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while(t--){solve();}
}

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