Submission #154849

#	Time	Username	Problem	Language	Result	Execution time	Memory
154849		andrew	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1501 ms	98364 KiB

treearray

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
const ll MAXN = 2e5 + 2;
const ll N = 2e5;
const ll inf = 3e18;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T> void vout(T s){cout << s << endl;exit(0);}

set <ll> s[MAXN], s1[MAXN];

vector <ll> v[MAXN];

ll tin[MAXN], tout[MAXN], stn, p[MAXN][19];

void dfs(ll x, ll pr){
    p[x][0] = pr;
    for(int i = 1; i < 19; i++)p[x][i] = p[p[x][i - 1]][i - 1];
    tin[x] = ++stn;
    for(auto to : v[x])if(to != pr)dfs(to, x);
    tout[x] = stn;
}

bool is_less(ll a, ll b){
    return (tin[b] <= tin[a] && tout[a] <= tout[b]);
}

ll lca(ll a, ll b){
    if(is_less(a, b))return b;
    if(is_less(b, a))return a;
    for(int i = 18; i >= 0; i--)if(!is_less(b, p[a][i]))a = p[a][i];
    return p[a][0];
}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    tout[0] = 1e18;

    ll n, m, q;
    cin >> n >> m >> q;

    vector <ll> a(m + 1);

    for(int i = 1; i < n; i++){
        ll x, y;
        cin >> x >> y;
        v[x].p_b(y);
        v[y].p_b(x);
    }

    dfs(1ll, 0ll);

    for(int i = 1; i <= m; i++)cin >> a[i];

    for(int i = 1; i <= m; i++)s[a[i]].insert(i);

    for(int i = 1; i < m; i++){
        s1[lca(a[i], a[i + 1])].insert(i);
    }

    while(q--){
        ll t;
        cin >> t;
        if(t == 1){
            ll pos, val;
            cin >> pos >> val;
            s[a[pos]].erase(pos);
            if(pos < m)s1[lca(a[pos], a[pos + 1])].erase(pos);
            if(pos > 1)s1[lca(a[pos], a[pos - 1])].erase(pos - 1);
            a[pos] = val;
            s[a[pos]].insert(pos);
            if(pos < m)s1[lca(a[pos], a[pos + 1])].insert(pos);
            if(pos > 1)s1[lca(a[pos], a[pos - 1])].insert(pos - 1);
        }else{
            ll l, r, v;
            cin >> l >> r >> v;
            ll x, y;
            x = y = -1;
            set <ll> :: iterator it;
            if(!s[v].empty()){
                it = s[v].upper_bound(r);
                if(it != s[v].begin()){
                    --it;
                    if(l <= *it)x = *it, y = *it;
                }
            }

            if(!s1[v].empty()){
                it = s1[v].lower_bound(r);
                if(it != s1[v].begin()){
                    --it;
                    if(l <= *it)x = *it, y = *it + 1;
                }
            }
            cout << x << " " << y << "\n";
        }
    }

    return 0;
}

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