Submission #1131838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131838		harut_13	Birthday gift (IZhO18_treearray)	C++20	100 / 100	441 ms	89196 KiB

treearray

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <map>
#include <string>
#include <ios>
#include <iomanip>
#include <deque>
#include <queue>
#include <list> 
#include <stack>

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define CY   cout<<"YES"<<'\n'
#define CN   cout<<"NO"<<'\n'
#define ll   long long
#define ciN  cin
#define itn  int
#define pshb  push_back
#define sz  size()
#define vec vector<int>
#define vecl vector<long long>
#define fro for
#define Int int
#define stirng string
#define nedl   '\n' 
#define pi 3.141592653589793238463
#define endl '\n'
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MOD 1000000007

using namespace std;

ll gcd(ll n1, ll n2)
{
    if (n2 != 0)
        return gcd(n2, n1 % n2);
    else
        return n1;
}
ll lcm(ll a, ll b) {
    return a * b / (gcd(a, b));
}

ll pv(ll a, ll b) {
    if (b == 0)return 1;
    ll res = (pv(a, b / 2));
    if (b % 2) {
        return ((res) * (res) * (a));
    }
    else {
        return (res) * (res);
    }
}
vector<vec> gp, up;
vec tin, tout;
int L, timer;
void dfs(int u, int p) {
    tin[u] = ++timer;
    up[u][0] = p;
    for (int i = 1; i <= L; i++) {
        up[u][i] = up[up[u][i - 1]][i - 1];
    }
    for (auto& x : gp[u]) {
        if (x != p)dfs(x, u);
    }
    tout[u] = ++timer;
}
bool cnox(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v) {
    if (cnox(u, v))return u;
    if (cnox(v, u))return v;
    for (int i = L; i >= 0; i--) {
        if (!cnox(up[u][i], v))u = up[u][i];
    }
    return up[u][0];
}
struct four {
    int tes;
    int a;
    int b;
    int c;
};
int m;
vec v;

void solve() {
    int n; cin >> n;
    int q;
    cin >> m >> q;
    gp = vector<vec>(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        gp[--u].pshb(--v);
        gp[v].pshb(u);
    }
   v=vec(m);
    vector<set<int>> st1(n);  
    for (int i = 0; i < m; i++) {
        cin >> v[i];
        v[i]--;
        st1[v[i]].insert(i);
    } 
   
    vector<four> harc(q);
    for (int i = 0; i < q; i++) {
        cin >> harc[i].tes;
        if (harc[i].tes == 1) {
            cin >> harc[i].a >> harc[i].b;
        }
        else {
            cin >> harc[i].a >> harc[i].b >> harc[i].c;
        }
    }
    timer = 0;
    L = ceil(log2(n));
    up = vector<vec>(n, vec(L + 1));
    tin = tout = vec(n);
    dfs(0, 0);
    vector<set<int>> st2(n);
    vec masiv(m - 1);
    for (int i = 0; i < m - 1; i++) {
        int lc = lca(v[i], v[i + 1]);
        masiv[i] = lc;
        st2[lc].insert(i);
    }
    for (int k = 0; k < q; k++) {
        if (harc[k].tes == 1) {
            int idx = harc[k].a - 1;
            int vv = harc[k].b - 1;
            st1[v[idx]].erase(idx);
            if (idx != m-1) {
                int lc = masiv[idx];
                st2[lc].erase(idx);
            }
            if (idx != 0) {
                int lc = masiv[idx-1];
                st2[lc].erase(idx - 1);
            }
            v[idx] = vv;
            st1[vv].insert(idx);
            if (idx != m-1) {
                int lc = lca(v[idx], v[idx + 1]);
                masiv[idx] = lc;
                st2[lc].insert(idx);
            }
            if (idx != 0) {
                int lc = lca(v[idx], v[idx - 1]);
                masiv[idx-1] = lc;
                st2[lc].insert(idx - 1);
            }
        }
        else {
            int l = harc[k].a - 1;
            int r = harc[k].b - 1;
            int vv = harc[k].c - 1;
            if (auto it = st1[vv].lower_bound(l); it != st1[vv].end() && *it <= r) {
                cout << *it + 1 << " " << *it + 1 << endl;
                continue;
            }
            if (auto it = st2[vv].lower_bound(l); it != st2[vv].end() && *it != m - 1 && *it + 1 <= r) {
                cout << *it + 1 << " " << *it + 2 << endl;
                continue;
            }
            cout << -1 << " " << -1 << endl;
        }
    }
}

signed main() {
    FASTIO
    solve();
}

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