Submission #1164460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164460		MPG	Birthday gift (IZhO18_treearray)	C++20	56 / 100	4019 ms	260052 KiB

treearray

//#pragma GCC optomize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse4.1,sse4.2") 



#include <bits/stdc++.h>
using namespace std;
typedef long long       ll;
#define     max_heap priority_queue<pair <ll, pair <ll, ll>>>
#define     min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>>
#define     sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define     filE freopen("in.txt", "r", stdin); freopen("out1.txt", "w", stdout); 
#define     endl '\n'
#define     md(a) (a % mod + mod) % mod
#define     pb push_back
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//cout << setprecision(5) << fixed << f;
//hash prime = 769


ll const maxn = 2e5 + 123;
ll const inf = 3e18;
ll const loG = 23;
ll const mod = 1e9 + 7;
//ll const mod = 998244353;
ll const sq = 500;
ll power(ll a, ll b, ll mod){if(b==0)return 1;if(b==1)return a;ll x = power(a, b / 2, mod);return (((x * x) % mod) * (b % 2 ? a : 1)) % mod;}



int n, m, q, sz = 2, par[loG][maxn], h[maxn], arr[maxn], l, r, val;
vector <int> g[maxn];
vector <pair <int, int>> pak, add;
vector <set <pair <int, int>>> seg;
set <int> st[maxn];

void dfs(int v, int p){
    h[v] = h[p] + 1;
    par[0][v] = p;

    for (int u : g[v]){
        if (u != p)
            dfs(u, v);
    }
}

int jump(int v, int d){
    for (int i = 0; i < loG; i++){
        if ((1 << i) & d)
            v = par[i][v];
    }
    return v;
}

int lca(int u, int v){
    if (h[u] < h[v])
        swap(u, v);
    u = jump(u, h[u] - h[v]);
    if(u == v) return u;
    for(int i = loG - 1; i >= 0; i--)
        if(par[i][u] != par[i][v])
            u = par[i][u],
            v = par[i][v];
    return par[0][u];
}

void setter(int i, int x, int lx, int rx){
    //cout << i << ' ' << x << ' ' << lx << ' ' << rx << " :" << endl;
    //for (auto p : pak)
    //   cout << p.first << ' ' << p.second << endl;
    //for (auto p : add)
    //    cout << p.first << ' ' << p.second << endl;
    for (auto p : pak){
        if (seg[x].find(p) != seg[x].end())
            seg[x].erase(p);
    }
    if (rx - lx == 1){
        for (auto p : add)
            seg[x].insert(p);
        return;
    }
    for (auto p : add)
        seg[x].insert(p);
    int mid = (lx + rx) / 2, a = 2 * x + 1, b = a + 1;
    if (i < mid)
        setter(i, a, lx, mid);
    else
        setter(i, b, mid, rx);
}


int getter(int x, int lx, int rx){
    if (l >= rx || lx >= r){
        return -1;
    }
    //cout << x << ' ' << lx << ' ' << rx  << ' ' << val << endl;
    //for (auto p : seg[x])
    //    cout << p.first << ' ' << p.second << endl;
    //cout << endl;
    if (l <= lx && rx <= r){
        auto it = seg[x].upper_bound({val - 1, mod});
        if (it != seg[x].end()){
            auto p = *it;
            if (p.first == val)
                return p.second;
        }
        return -1;
    }
    int mid = (lx + rx) / 2, a = 2 * x + 1, b = a + 1;
    int val1 = getter(a, lx, mid);
    int val2 = getter(b, mid, rx);
    return max(val1, val2);
}



void Solve(){

cin >> n >> m >> q;
while (sz <= m)
    sz = sz * 2;
seg.resize(2 * sz);

for (int i = 1; i < n; i++){
    int a, b; cin >> a >> b;
    g[a].pb(b);
    g[b].pb(a);
}
dfs(1, 1);
for (int i = 1; i < loG; i++)
    for (int j = 1; j < n + 1; j++)
        par[i][j] = par[i - 1][par[i - 1][j]];



for (int i = 1; i < m + 1; i++){
    cin >> arr[i];
    st[arr[i]].insert(i);
}

for (int i = 1; i < m; i++){
    int a = arr[i], b = arr[i + 1];
    int c = lca(a, b);
    add.clear();
    add.pb({c, i});
    setter(i, 0, 0, sz);
}

//cout << "OK?" << endl;

while (q--){
    int c; cin >> c;
    if (c == 1){
        int i, x; cin >> i >> x;
        add.clear();
        pak.clear();
        if (i > 1){
            int a = arr[i - 1], b = arr[i], ah = lca(a, b);
            pak.pb({ah, i - 1});
            ah = lca(a, x);
            add.pb({ah, i - 1});
            setter(i - 1, 0, 0, sz);
        }
        
        add.clear();
        pak.clear();
        
        if (i < m){
            int a = arr[i], b = arr[i + 1], ah = lca(a, b);
            pak.pb({ah, i});
            ah = lca(x, b);
            add.pb({ah, i});
            setter(i, 0, 0, sz);
        }
        st[arr[i]].erase(i);
        arr[i] = x;
        st[x].insert(i);
    }
    else{
        cin >> l >> r >> val;
        auto it = st[val].lower_bound(l);
        if (it != st[val].end()){
            int x = *it;
            if (x <= r){
                cout << x << ' ' << x << endl;
                continue;
            }
        }
        int ans = getter(0, 0, sz);
        if (ans > 0){
            cout << ans << ' ' << ans + 1 << endl;
        }
        else
            cout << -1 << ' ' << -1 << endl;
    }   
}


}





int main(){
sariE;// filE;



int test = 1;
//cin >> test;
while (test--) Solve();
return 0;
}

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