Submission #1131851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131851		harut_13	Birthday gift (IZhO18_treearray)	C++20	56 / 100	4093 ms	79672 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 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;


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];
        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;
            bool f = 0;
            auto it = lower_bound(st1[vv].begin(), st1[vv].end(), l);
            if (it != st1[vv].end() && *it<=r) {
                cout << *it + 1 << " " << *it + 1 << endl;
                continue;
                
            }
            auto it2 = lower_bound(st2[vv].begin(), st2[vv].end(), l);

            if (it2!= st2[vv].end() && *it2+1<=r && *it2!=m-1) {

                        cout <<*it2+1 << " " << *it2+ 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: 0 / 44