Submission #1263004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263004		tubication	Birthday gift (IZhO18_treearray)	C++20	56 / 100	4094 ms	101924 KiB

treearray

/*
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⡀⡀⡀⠠⢄⣠⣴⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⢿⣿⣿⣿⣾⣆⡀⡀⢻
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⡀⡀⠄⡐⣰⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⣿⣿⣿⣿⣿⣷⡀⠈
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠉⡀⢀⣔⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣿⣿⣿⣿⣿⣿⡄
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⡀⢀⢢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡆⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⢀⣦⣿⠰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠋⡠⣷⣿⡟⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢸⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⣰⣿⣿⣿⠇⢼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠈⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⣴⣿⣿⣿⣿⡀⢸⣿⣿⡏⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⡀⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⠁⣼⣿⣿⣿⣿⣿⡀⠐⣿⣿⠁⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⣿⣿⡀⡆⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⡀⣺⣿⣿⣿⣿⣿⣿⡀⡀⢀⢈⡀⠈⢙⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠿⠿⡀⠹⡿⣸⡇⢺⣿⣿⣿⢻⣿
⣿⣿⣿⣿⣿⣿⠁⢰⣿⡅⠻⣿⣿⣿⣿⡀⣿⡀⣿⡀⠐⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣶⠂⡀⣶⢁⣿⣯⢸⣿⣿⠇⢸⣿
⣿⣿⣿⣿⣿⠁⡀⡀⢿⣿⡀⠉⢻⣿⣿⡇⣿⣷⡀⡀⣅⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⣼⡆⠋⣾⣿⣿⢸⣿⡿⡀⣾⣿
⣿⣿⣿⣿⠃⢠⣮⡀⡀⣈⠃⠘⣦⣴⣦⣤⣾⣿⣿⣶⣿⡈⣿⡀⣿⣿⣿⣿⣿⣿⣿⣿⡿⢀⣾⣿⣁⣾⣿⣿⡟⠸⠋⡤⢀⣿⣿
⣿⣿⣿⠃⢀⣾⣿⡧⠨⠿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣽⡈⡆⠈⣿⣿⣿⣿⣿⡿⠁⣴⣿⣿⣿⣿⣿⣿⣿⣷⠿⢿⡗⢸⣿⠏
⣿⣿⠏⡀⣽⣿⣿⡇⣀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣄⢸⣄⠻⡿⠟⢁⣴⣿⠁⡀⡀⡀⡀⡀⡀⡀⡀⡀⣀⠅⣿⡟⣠
⣿⠏⡀⢲⣿⣿⣿⠇⣿⣿⡇⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿⣿⣷⣴⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⡿⠘⣁⣾⣿
⠟⡀⢔⣿⣿⣿⣿⠂⣿⣿⠁⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⡀⡀⡀⡀⡀⡀⡀⡀⢸⣿⣶⠠⣿⣿⣿
⡀⡀⣺⣿⣿⣿⣿⡀⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⠇⣼⣿⣿⣿
⡀⡐⣿⣿⣿⣿⣿⡀⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⡀⢠⣿⣿⡀⣿⣿⣿⣿
⡀⢿⣿⣿⣿⣿⣿⡂⢿⣿⣷⡀⡀⡀⡀⡀⡀⡀⡀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⡀⢀⣿⣿⡏⢰⣿⣿⣿⣿
⢀⣿⣿⣿⣿⣿⣿⡅⢸⣿⣿⣿⣷⣦⣤⣴⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣀⣀⣀⣤⣶⣿⣿⣿⡀⢼⣿⠫⣿⣿
⢨⣿⣿⣿⣿⣿⣿⡧⠐⣿⣿⣿⣿⣿⣿⣿⠉⡉⠉⣉⣉⠉⣉⣉⢉⠉⢉⡉⠉⠉⠉⠉⠉⠉⢹⣿⣿⣿⣿⣿⡏⡀⣺⡟⢰⣿⣿
⣸⣿⣿⣿⣿⣿⣿⣿⡀⣻⣿⣿⣿⣿⣿⣿⡆⣿⢸⣿⣿⡀⣿⣿⡟⡀⣿⣿⠁⣿⣿⡀⣿⠃⣼⣿⣿⣿⣿⡿⡀⡀⡿⠁⣾⣿⣿
⢺⡟⣿⣿⣿⣿⣿⣿⡀⡀⠻⣿⣿⣿⣿⣿⣿⡈⢸⣿⣿⡀⣿⣿⣷⢸⣿⣿⡀⣿⣿⠰⠋⣴⣿⣿⣿⡿⠋⡀⡀⡀⠁⢠⣿⣿⣿
⠸⡇⠹⣿⣿⣿⣿⣿⣇⡀⡀⡀⠛⢿⣿⣿⣿⣿⣄⠙⡿⢰⣿⣿⣿⢸⣿⣿⠠⡿⠋⣤⣿⣿⣿⠟⠉⡀⡀⡀⡀⡀⡀⣿⣿⣿⣿
⡀⠈⡀⠙⢿⣿⣿⣿⣿⡀⡀⡀⡀⡀⡀⣈⠉⠛⠿⢿⣶⣤⣉⣙⢉⣉⣉⣁⣤⠾⠛⠋⠉⡀⡀⡀⡀⡀⢀⣠⣤⣴⠴⠷⠶⠚⠋
⡀⡀⢰⣷⣄⡀⠛⠿⣿⣷⡀⣆⡀⡀⡀⠘⣿⣿⣿⣶⠖⣀⠲⣶⣶⣶⣶⠆⡀⡀⡀⡀⡀⡀⡀⡀⡀⡀⢀⡀⡀⡀⢈⠉⠉⠉⠉
⡀⡀⡪⣿⣿⣧⡀⢠⣤⣀⡁⡀⡀⡀⡀⣆⠈⠿⠛⣠⣿⣿⣦⠈⢿⣿⡟⢠⡀⡀⡀⡀⡀⡀⡀⡀⢽⣿⠿⡿⣿⣿⢿⡿⣿⣿⣿
⣀⡀⠱⣿⣿⣿⡀⣿⣿⣿⠟⡀⡀⡀⡀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣤⣴⣿⠇⡀⡀⡀⣄⡀⡠⡆⠘⣿⢸⣗⣥⣿⣿⣿⣰⣴⣬
⠋⢠⣦⡀⡹⠻⣷⡟⠛⠁⡀⡀⡀⡀⡀⡀⡀⠉⠉⠋⠙⠛⠛⠛⠛⠛⠉⠉⡀⡀⡀⡀⢹⣦⠘⢿⡀⣿⡎⣾⣿⣫⡶⣾⡿⣽⣭ 
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define synchronize {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);}

#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false); debug("%s time : %.4fs", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))

#define ll long long
#define ld long double
#define ull unsigned long long

#define pii pair <int, int>
#define pli pair <ll, int>
#define pil pair <int, ll>
#define pll pair <ll, ll>

#define vvi vector <vector <int>>

#define all(v) (v).begin(), (v).end()
#define __builtin_popcount __builtin_popcountll

#define fi first
#define se second

template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        }
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) {
            x = y;
            return true;
        }
        return false;
    }   

const int nmax = 3e5 + 5;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r) {
    return uniform_int_distribution <long long>(l, r)(rng);
}

/** END OF TEMPLATE **/

int lg2(int n)  {
    return n ? __builtin_clzll(1) - __builtin_clzll(n) : -1;
}

struct lca {
    int n, ptr, timer;
    vector <int> tin, tout;

    vector <int> euler, depth_arr, fai, h;
    vector <vector <int>> adj, dp;

    void set(int n) {
        this->n = n;

        fai.resize(n + 1, -1);
        adj.resize(n + 1);
        h.resize(n + 1);

        tin.resize(n + 1);
        tout.resize(n + 1);

        this->n = n;
        timer = 0;
        ptr = 0;
    }

    void insert(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void init() {
        dfs(1, -1, 0);
        build(euler.size());
    }

    void dfs(int cur, int prev, int dep) {
        if (fai[cur] == -1) fai[cur] = ptr;
        h[cur] = dep;
        euler.push_back(cur);
        ptr++;

        tin[cur] = ++timer; 

        for (int x : adj[cur]) {
            if (x != prev) {
                dfs(x, cur, dep + 1);
                euler.push_back(cur);
                ptr++;
            }
        }

        tout[cur] = timer;
    }

    void build(int n) {
        depth_arr.clear();
        for (int x : euler) depth_arr.push_back(h[x]);
        int m = depth_arr.size();
        dp.assign(m, vector<int>(20, -1));
        for (int i = 1; i < m; i++) dp[i - 1][0] = (depth_arr[i] > depth_arr[i - 1]) ? i - 1 : i;
        for (int j = 1; (1 << j) <= m; j++) {
            for (int i = 0; i + (1 << j) <= m; i++) {
                dp[i][j] = (depth_arr[dp[i][j - 1]] > depth_arr[dp[i + (1 << (j - 1))][j - 1]]) ? dp[i + (1 << (j - 1))][j - 1] : dp[i][j - 1];
            }
        }
    }

    int query(int l, int r) {
        int d = r - l;
        int dx = lg2(d);
        if (depth_arr[dp[l][dx]] > depth_arr[dp[r - (1 << dx)][dx]]) return dp[r - (1 << dx)][dx];
        else return dp[l][dx];
    }

    int query_lca(int u, int v) {
        if (u == v) return u;
        if (fai[u] > fai[v]) swap(u, v);
        return euler[query(fai[u], fai[v])];
    }
} p;

struct seg_tree {
    struct node {
        int mn, mx;
        int val;

        node() { 
            mn = INT_MAX; 
            mx = INT_MIN; 
            val = -1;
        }

        node(int v) {
            mn = mx = p.tin[v];
            val = v;
        }

        node operator+ (const node &other) const {
            if (val == -1) return other;
            if (other.val == -1) return *this;

            node res;
            res.mn = min(mn, other.mn);
            res.mx = max(mx, other.mx);
            res.val = p.query_lca(val, other.val);
            return res;
        }
    };

    int n;
    vector<node> tr;

    void set(int _n, int arr[]) {
        n = _n;
        tr.assign(4 * n + 5, node());
        build(1, 1, n, arr);
    }

    void build(int id, int l, int r, int arr[]) {
        if (l == r) {
            tr[id] = node(arr[l]);
            return;
        }

        int mid = (l + r) >> 1;
        build(2 * id, l, mid, arr);
        build(2 * id + 1, mid + 1, r, arr);
        
        tr[id] = tr[2 * id] + tr[2 * id + 1];
    }

    void update(int id, int l, int r, int idx, int v) {
        if (idx < l || idx > r) return;
        if (l == r) {
            tr[id] = node(v);
            return;
        }

        int mid = (l + r) >> 1;
        update(2 * id, l, mid, idx, v);
        update(2 * id + 1, mid + 1, r, idx, v);
        
        tr[id] = tr[2 * id] + tr[2 * id + 1];
    }

    node query_node(int id, int l, int r, int u, int v) {
        if (u > r || v < l) return node();
        if (u <= l && r <= v) return tr[id];
        
        int mid = (l + r) >> 1;
        node tl = query_node(2 * id, l, mid, u, v);
        node tr = query_node(2 * id + 1, mid + 1, r, u, v);

        return tl + tr;
    }

    int query(int u, int v) {
        return query_node(1, 1, n, u, v).val;
    }

    int find_inside(int id, int l, int r, int u, int v, int x) {
        if (u > r || v < l) return -1;
        if (tr[id].mn > p.tout[x] || tr[id].mx < p.tin[x]) return -1;
        if (l == r) return l;

        int mid = (l + r) >> 1;
        int tl = find_inside(2 * id, l, mid, u, v, x);
        
        if (tl != -1) return tl;
        return find_inside(2 * id + 1, mid + 1, r, u, v, x);
    }

    int find_outside(int id, int l, int r, int u, int v, int x) {
        if (u > r || v < l) return -1;
        if (p.tin[x] <= tr[id].mn && tr[id].mx <= p.tout[x]) return -1;
        if (l == r) return l;
        
        int mid = (l + r) >> 1;
        int tl = find_outside(2 * id, l, mid, u, v, x);
        
        if (tl != -1) return tl;
        return find_outside(2 * id + 1, mid + 1, r, u, v, x);
    }
};


int n, m, q;
int u, v, arr[nmax];
int ty, idx, l, r, x;

set <int> pos[nmax];
seg_tree seg;

void update(int idx, int x) {
    if (arr[idx] == x) return;

    pos[arr[idx]].erase(idx);
    arr[idx] = x;
    pos[arr[idx]].insert(idx);
    
    seg.update(1, 1, m, idx, x);
}

pii query(int l, int r, int x) {
    auto it = pos[x].lower_bound(l);
    if (it != pos[x].end() && *it <= r) return {*it, *it};

    int curl = l;
    while (true) {
        int s = seg.find_inside(1, 1, m, curl, r, x);
        if (s == -1) break;

        int t = seg.find_outside(1, 1, m, s, r, x);
        int e = (t == -1 ? r : t - 1);
        
        int lc = seg.query(s, e);
        if (lc == x) return {s, e};
        
        curl = e + 1;
        if (curl > r) break;
    }

    return {-1, -1};
}

int main() {
    synchronize;

    cin >> n >> m >> q;

    p.set(n);

    for (int i = 1; i < n; ++i) {
        cin >> u >> v;
        p.insert(u, v);
    }

    p.init();

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

    seg.set(m, arr);

    while (q--) {
        cin >> ty;
        if (ty == 1) {
            cin >> idx >> x;
            update(idx, x);
        } else {
            cin >> l >> r >> x;
            auto res = query(l, r, x);
            cout << res.fi << ' ' << res.se << '\n';
        }
    }

    return (0 ^ 0);
}

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