Submission #1260496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260496		minhpk	Birthday gift (IZhO18_treearray)	C++20	56 / 100	550 ms	263740 KiB

treearray

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b,q;
vector <int> z[1000005];
int t[1000005];

int logarit[1000005];
int sta[1000005];
int fin[1000005];
int euler[1000005];
int tour;
int high[1000005];
int st[800001][20];
void dfs(int i,int par){

    tour++;
    sta[i]=tour;
    euler[tour]=i;

    for (auto p:z[i]){
         if (p==par){
            continue;
         }
         high[p]=high[i]+1;
         dfs(p,i);
         tour++;
         euler[tour]=i;
    }

    tour++;
    euler[tour]=i;
    fin[i]=tour;
}


void buildst(){
    for (int i=1;i<=tour;i++){
         st[i][0]=euler[i];
    }

    for (int j=1;j<=20;j++){
         for (int i=1;i+(1<<j)-1<=tour;i++){
              int l=st[i][j-1];
              int r=st[i+(1<<(j-1))][j-1];

              if (high[l]<high[r]){
                 st[i][j]=l;
              }else{
                 st[i][j]=r;
              }
         }
    }
}

int lca(int x,int y){
    int l = min(sta[x], sta[y]);
    int r = max(sta[x], sta[y]);
    int j = logarit[r - l + 1];
    int idx1 = st[l][j];
    int idx2 = st[r - (1 << j) + 1][j];
    return (high[idx1] < high[idx2] ? idx1 : idx2);
}

set<int> s[1000005];
set<int> s1[1000005];
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b >> q;
    for (int i=1;i<a;i++){
         int x,y;
         cin >> x >> y;
         z[x].push_back(y);
         z[y].push_back(x);
    }
    dfs(1,0);
    buildst();
    logarit[2] = 1;
    for(int i = 3; i <= 1000000; i++){
         logarit[i] = logarit[i/2] + 1;
    }
    for (int i=1;i<=b;i++){
         cin >> t[i];
         s1[t[i]].insert(i);
    }
    for (int i=1;i<b;i++){
         int l=lca(t[i],t[i+1]);
         s[l].insert(i);
    }
    while (q--){
         int c;
         cin >> c;
         if (c==1){
             int x,y;
             cin >> x >> y;
             s1[t[x]].erase(x);
             if (x!=b){
                 int l=lca(t[x],t[x+1]);
                 s[l].erase(x);
             }
             if (x!=1){
                 int l=lca(t[x],t[x-1]);
                 s[l].erase(x-1);
             }
             t[x]=y;
             if (x!=b){
                 int l=lca(t[x],t[x+1]);
                 s[l].insert(x);
             }
             if (x!=1){
                 int l=lca(t[x],t[x-1]);
                 s[l].insert(x-1);
             }
             s1[t[x]].insert(x);
         }else{
             int l,r,x;
             cin >> l >> r >> x;
             auto it=s1[x].lower_bound(l);
             if (*it>=l && *it<=r){
                 cout << *it << " " << *it << "\n";
                 continue;
             }
             auto p=s[x].lower_bound(l);
             if (*p>=l && *p<r){
                 cout << *p << " " <<*p+1 << "\n";
                 continue;
             }
             cout << -1 << " " << -1 << "\n";
         }
    }
    return 0;
}

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