Submission #1125047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125047		kirakosyan	Birthday gift (IZhO18_treearray)	C++20	56 / 100	719 ms	73244 KiB

treearray

#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<random>
#include<cmath>
#include<stack>
#include<map>
#include <iomanip> 
#include <queue>
#include <set>
using namespace std;
using ll = long long;
using ull = unsigned long long;
ll mod = 1e9 + 7;
ll pv(ll a, ll b) {
    if (b == 0)return 1;
    ll res = (pv(a, b / 2));
    if (b % 2) {
        return (((res * res) % mod) * (a % mod)) % mod;
    }
    else {
        return (res * res) % mod;
    }
}
ll gcd(ll n1, ll n2)
{
    if (n2 != 0)
        return gcd(n2, n1 % n2);
    else
        return n1;
}
vector<vector<int>>gp, up;
vector<int>tin, tout;
int timer = 0;
void dfs(int u, int p) {
    tin[u] = ++timer;
    up[u][0] = p;
    for (int i = 1; i < 14; i++) {
        up[u][i] = up[up[u][i - 1]][i - 1];
    }
    for (int& x : gp[u]) {
        if (x != p) {
            dfs(x, u);
        }
    }
    tout[u] = ++timer;

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

int lca(int u, int v) {
    if (stugel(u, v)) {
        return u;
    }
    if (stugel(v, u)) {
        return v;
    }
    for (int i = 13; i >= 0; i--) {
        if (!(stugel(up[u][i], v))) {
            u = up[u][i];
        }
    }
    return up[u][0];
}
void solve() {
    int n, m, q; cin >> n >> m >> q;
    gp = vector<vector<int>>(n);
    up = vector<vector<int>>(n, vector<int>(14));
    tin = tout = vector<int>(n);
    vector<multiset<int>>adj(n),adj1(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        --u, --v;
        gp[u].push_back(v);
        gp[v].push_back(u);
    }
    dfs(0, 0);
    vector<int>v(m);
    for (int i = 0; i < m; i++) {
        cin >> v[i];
        --v[i];
        adj1[v[i]].insert(i);
    }
    
    for (int i = 0; i < m - 1; i++) {
        adj[lca(v[i], v[i + 1])].insert(i);
    }
   
    for (int i = 0; i < q; i++) {
        int harc; cin >> harc;
        if (harc == 1) {
            int pos, v1; cin >> pos >> v1;
            --pos, --v1;
            adj1[v[pos]].erase(adj1[v[pos]].find(pos));
            if (pos < m - 1) {
                adj[lca(v[pos],v[pos+1])].erase(adj[lca(v[pos], v[pos + 1])].find(pos));
            }
            if (pos - 1 >= 0) {
                adj[lca(v[pos], v[pos - 1])].erase(adj[lca(v[pos], v[pos - 1])].find(pos - 1));
            }
            v[pos] = v1;
            adj1[v[pos]].insert(pos);
            if (pos < m - 1) {
                adj[lca(v[pos], v[pos + 1])].insert(pos);
            }
            if (pos - 1 >= 0) {
                adj[lca(v[pos], v[pos - 1])].insert(pos - 1);
            }
        }
        else {
            int l, r, v1; cin >> l >> r >> v1;
            --l, --r, --v1;
            int x1 = -1, y1 = -1;
            auto araj = adj1[v1].lower_bound(l);
            if (araj != adj1[v1].end()) {
                
                if (*araj <= r) {
                    x1 = *araj + 1;
                    y1 = *araj + 1;
                }

            }
            auto erk = adj[v1].lower_bound(l);
            if (erk != adj[v1].end()) {
                if (*erk + 1 <= r) {
                    x1 = *erk + 1;
                    y1 = *erk + 2;
                }
            }
            cout << x1 << " " << y1 << endl;
        }
    }

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll _ = 1;
    //cin >> _;
    while (_--) {
        solve();
    }
}

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