Submission #1011035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011035		phoenix	Birthday gift (IZhO18_treearray)	C++17	100 / 100	560 ms	83280 KiB

treearray

#include <bits/stdc++.h>

using namespace std;

const int N = 200200;

vector<int> g[N];
int tin[N], tout[N], T;
int par[N][18];

void precalc(int s, int p) {
    tin[s] = T++;
    par[s][0] = p;
    for (int i = 1; i < 18; i++) par[s][i] = par[par[s][i - 1]][i - 1];
    for (int to : g[s]) if (to != p)
        precalc(to, s);
    tout[s] = T++;
}

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

int lca(int u, int v) {
    if (up(u, v)) return u;
    if (up(v, u)) return v;
    for (int i = 17; i >= 0; i--) 
        if (!up(par[u][i], v))
            u = par[u][i];
    return par[u][0];
}

int n, m, q;
int A[N];

set<int> s1[N], s2[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= m; i++)
        cin >> A[i];
    A[0] = A[m + 1] = 1;
    precalc(1, 1);
    for (int i = 0; i <= m; i++) {
        s1[lca(A[i], A[i + 1])].insert(i);
        s2[A[i]].insert(i);
    }
    
    while (q --> 0) {
        int t;
        cin >> t;
        if (t == 1) {
            int pos, v;
            cin >> pos >> v;
            s2[A[pos]].erase(pos);
            s1[lca(A[pos], A[pos + 1])].erase(pos);
            s1[lca(A[pos - 1], A[pos])].erase(pos - 1);
            A[pos] = v;
            s2[A[pos]].insert(pos);
            s1[lca(A[pos], A[pos + 1])].insert(pos);
            s1[lca(A[pos - 1], A[pos])].insert(pos - 1);
        } else {
            int l, r, v;
            cin >> l >> r >> v;
            auto it = s1[v].lower_bound(l);
            if (it != s1[v].end() && *it < r) 
                cout << *it << ' ' << *it + 1;
            else {
                it = s2[v].lower_bound(l);
                if (it != s2[v].end() && *it <= r) 
                    cout << *it << ' ' << *it;
                else 
                    cout << -1 << ' ' << -1;
            }
            cout << '\n';
        }
    }
}

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