Submission #1131518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131518		harut_13	Birthday gift (IZhO18_treearray)	C++20	56 / 100	4091 ms	78860 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);
#define CY   cout<<"YES"<<endl
#define CN   cout<<"NO"<<endl
#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   endl 
#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;
            cin >> harc[i].b;
        }
        else {
            cin >> harc[i].a;
            cin >> harc[i].b;
            cin >> 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);
    for (int i = 0; i < m - 1; i++) {
        int lc = lca(v[i], v[i + 1]);
        st2[lc].insert(i);
    }
    for (int k = 0; k < q; k++) {
        if (harc[k].tes == 1) {
            int idx = harc[k].a;
            int vv = harc[k].b;
            idx--;
            vv--;
            st1[v[idx]].erase(idx);
            if (idx != m-1) {
                int lc = lca(v[idx], v[idx + 1]);
                st2[lc].erase(idx);
            }
            if (idx != 0) {
                int lc = lca(v[idx], v[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]);
                st2[lc].insert(idx);
            }
            if (idx != 0) {
                int lc = lca(v[idx], v[idx - 1]);
                st2[lc].insert(idx - 1);
            }
        }
        else {
            int l = harc[k].a;
            int r = harc[k].b;
            int vv = harc[k].c;
            l--;
            r--;
            vv--;
            bool f = 0;
            if (lower_bound(st1[vv].begin(), st1[vv].end(), l) != st1[vv].end()) {
                int idx1 = *lower_bound(st1[vv].begin(), st1[vv].end(), l);
                if (idx1 <= r) {
                    cout << idx1 + 1 << " " << idx1 + 1 << endl;
                    continue;
                }
            }
            if (lower_bound(st2[vv].begin(), st2[vv].end(), l) != st2[vv].end()) {
                int idx = *lower_bound(st2[vv].begin(), st2[vv].end(), l);
                if (idx != m - 1 && idx+1<=r) {
                    int lc = lca(v[idx], v[idx + 1]);
                    if (lc == vv) {
                        cout << idx + 1 << " " << idx + 2 << endl;
                        continue;
                    }
                }
            }
            cout << -1 << " " << -1 << endl;
        }
    }
}



signed main() {
    FASTIO
        //int t; cin >> t;
    //while (t--)
        solve();


}

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