Submission #478257

#	Time	Username	Problem	Language	Result	Execution time	Memory
478257		Vladth11	Birthday gift (IZhO18_treearray)	C++14	12 / 100	11 ms	14572 KiB

treearray

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
 
const ll NMAX = 200001;
const ll VMAX = 21;
const ll INF = (1LL << 59);
const ll MOD = 998244353;
const ll BLOCK = 318;
const ll base = 31;
const ll nr_of_bits = 21;
 
vector <int> v[NMAX];
int dp[NMAX][nr_of_bits + 1];
set <pii> st[NMAX];
int a[NMAX], m;
 
 
pii timp[NMAX];
int stamp;
 
bool isParent(int a, int b){
    return timp[a].first <= timp[b].first && timp[b].second <= timp[a].second;
}
 
int LCA(int a, int b){
    if(isParent(a, b))
        return a;
    if(isParent(b, a))
        return b;
    int r = b, pas = nr_of_bits;
    while(pas >= 0){
        int nxt = dp[r][pas];
        if(nxt != 0 && !isParent(nxt, a))
            r = nxt;
        pas--;
    }
    if(!isParent(r, a))
        r = dp[r][0];
    return r;
}
 
void sterge(int stt, int dr){
    if(stt < 1)
        return;
    if(dr > m)
        return;
    int lca = LCA(a[stt], a[dr]);
    st[lca].erase({stt, dr});
}
 
void pune(int stt, int dr){
    if(stt < 1)
        return;
    if(dr > m)
        return;
    int lca = LCA(a[stt], a[dr]);
    st[lca].insert({stt, dr});
}
 
void DFS(int node, int p){
    dp[node][0] = p;
    timp[node].first = ++stamp;
    for(auto x : v[node]){
        if(x == p)
            continue;
        DFS(x, node);
    }
    timp[node].second = stamp;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q, i, j;
    cin >> n >> m >> q;
    for(i = 1; i < n; i++){
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    DFS(1, 0);
    for(j = 1; j <= nr_of_bits; j++){
        for(i = 1; i <= n; i++){
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
    }
    for(i = 1; i <= m; i++){
        cin >> a[i];
        st[a[i]].insert({i, i});
    }
    for(i = 2; i <= m; i++){
        pune(i - 1, i);
    }
    while(q--){
        int c, l, r;
        cin >> c >> l >> r;
        if(c == 1){
            st[a[l]].erase({l, l});
            sterge(l - 1, l);
            sterge(l, l + 1);
            a[l] = r;
            pune(l - 1, l);
            pune(l, l + 1);
            st[a[l]].insert({l, l});
        }else{
            int x;
            cin >> x;
            pii it = *st[x].lower_bound({l, 0});
            if(it.first >= l && it.second <= r){
                cout << it.first << " " << it.second << "\n";
            }else{
                cout << "-1 -1\n";
            }
        }
    }
    return 0;
}

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