Submission #58095

#	Time	Username	Problem	Language	Result	Execution time	Memory
58095		Benq	Birthday gift (IZhO18_treearray)	C++14	56 / 100	1777 ms	262360 KiB

treearray

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

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 200001;

template<class T, int SZ> struct RMQ {
    T stor[SZ][32-__builtin_clz(SZ)];
    
    T comb(T a, T b) {
        return min(a,b);
    }
    
    void build(vector<T>& x) {
        F0R(i,sz(x)) stor[i][0] = x[i];
        FOR(j,1,32-__builtin_clz(SZ)) F0R(i,SZ-(1<<(j-1))) 
            stor[i][j] = comb(stor[i][j-1],
                        stor[i+(1<<(j-1))][j-1]);
    }
    
    T query(int l, int r) {
        int x = 31-__builtin_clz(r-l+1);
        return comb(stor[l][x],stor[r-(1<<x)+1][x]);
    }
};

template<int SZ> struct LCA {
    vi edges[SZ];
    RMQ<pi,2*SZ> r;
    vpi tmp;
    int depth[SZ], pos[SZ];
    
    int V, R = 1;
    
    void addEdge(int u, int v) {
        edges[u].pb(v), edges[v].pb(u);
    }
    
    void dfs(int u, int prev){
        pos[u] = sz(tmp); depth[u] = depth[prev]+1;
        tmp.pb({depth[u],u});
        for (int v: edges[u]) if (v != prev) {
            dfs(v, u);
            tmp.pb({depth[u],u});
        }
    }
    
    void construct() {
        dfs(R, 0);
        r.build(tmp);
    }
    
    int lca(int u, int v){
        u = pos[u], v = pos[v];
        if (u > v) swap(u,v);
        return r.query(u,v).s;
    }
    
    int dist(int u, int v) {
        return depth[u]+depth[v]-2*depth[lca(u,v)];
    }
};

LCA<MX> L;

int n,m,q,a[MX];
set<pi> S[MX];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> q;
    L.V = n;
    F0R(i,n-1) {
        int u,v; cin >> u >> v;
        L.addEdge(u,v);
    }
    L.construct();
    FOR(i,1,m+1) {
        cin >> a[i];
        S[a[i]].insert({i,i});
        if (i > 1) S[L.lca(a[i-1],a[i])].insert({i-1,i});
    }
    F0R(i,q) {
        int t; cin >> t;
        if (t == 1) {
            int pos, v; cin >> pos >> v;
            S[a[pos]].erase({pos,pos});
            if (pos > 1) S[L.lca(a[pos-1],a[pos])].erase({pos-1,pos});
            if (pos < m) S[L.lca(a[pos],a[pos+1])].erase({pos,pos+1});
            
            a[pos] = v;
            
            S[a[pos]].insert({pos,pos});
            if (pos > 1) S[L.lca(a[pos-1],a[pos])].insert({pos-1,pos});
            if (pos < m) S[L.lca(a[pos],a[pos+1])].insert({pos,pos+1});
        } else {
            int l,r,v; cin >> l >> r >> v;
            auto it = S[v].lb({l,0});
            if (it != S[v].end() && it->s <= r) cout << it->f << " " << it->s << "\n";
            else cout << "-1 -1\n";
        }
    }
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

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