제출 #1307145

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307145		jahongir	Birthday gift (IZhO18_treearray)	C++20	100 / 100	519 ms	79752 KiB

treearray

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

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(a) a.begin(),a.end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef unsigned long long ull;
typedef vector<int> vi;


static const int buf_size = 4096;
 
inline int getChar() {
	static char buf[buf_size];
	static int len = 0, pos = 0;
	if (pos == len)
		pos = 0, len = fread(buf, 1, buf_size, stdin);
	if (pos == len)
		return -1;
	return buf[pos++];
}
 
inline int readChar() {
	int c = getChar();
	while (c <= 32)
		c = getChar();
	return c;
}
 
template <class T = int>
inline T readInt() {
	int s = 1, c = readChar();
	T x = 0;
	if (c == '-')
		s = -1, c = getChar();
	while ('0' <= c && c <= '9')
		x = x * 10 + c - '0', c = getChar();
	return s == 1 ? x : -x;
}
 
/** Write */
 
static int write_pos = 0;
static char write_buf[buf_size];
 
inline void writeChar( int x ) {
	if (write_pos == buf_size)
		fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
	write_buf[write_pos++] = x;
}
 
inline void flush() {
	if (write_pos)
		fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
}
 
template <class T = int> 
inline void writeInt( T x ) {
	if (x < 0)
		writeChar('-'), x = -x;
 
	char s[24];
	int n = 0;
	while (x || !n)
		s[n++] = '0' + x % 10, x /= 10;
	while (n--)
		writeChar(s[n]);
}



const int mxn = 2e5+1, lg2 = 18;
vector<int> g[mxn];
int suc[mxn][lg2];
int tin[mxn],tout[mxn],tim=0;

int arr[2][mxn];


void pre_dfs(int u, int p){
    suc[u][0] = p;
    tin[u] = ++tim;
    for(int i = 1; i < lg2; i++)
        suc[u][i] = suc[suc[u][i-1]][i-1];

    for(auto v : g[u]) if(v!=p)
        pre_dfs(v,u);
    
    tout[u] = tim;
}

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

int get_lca(int u, int v){
    if(is_anc(u,v)) return u;
    if(is_anc(v,u)) return v;
    for(int i = lg2-1; i >= 0; i--)
        if(!is_anc(suc[u][i],v))
            u = suc[u][i];
    return suc[u][0];
}


set<int> st[2][mxn];

void solve(){
    int n,m,q; cin >> n >> m >> q;

    for(int i = 1; i < n; i++){
        int u,v; cin >> u >> v;
        g[u].pb(v); g[v].pb(u);
    }

    pre_dfs(1,1);

    for(int i = 1; i <= m; i++){
        cin >> arr[0][i];
        st[0][arr[0][i]].insert(i);
        if(i>1){
            arr[1][i-1] = get_lca(arr[0][i-1],arr[0][i]);
            st[1][arr[1][i-1]].insert(i-1);
        }
    }

    for(int _ = 0; _ < q; _++){
        char t; cin >> t;
        if(t=='1'){
            int i,v; cin >> i >> v;
            st[0][arr[0][i]].erase(i);
            st[0][v].insert(i);
            arr[0][i] = v;

            if(i<m){
                st[1][arr[1][i]].erase(i);
                arr[1][i] = get_lca(arr[0][i],arr[0][i+1]);
                st[1][arr[1][i]].insert(i);
            }
            if(i>1){
                st[1][arr[1][i-1]].erase(i-1);
                arr[1][i-1] = get_lca(arr[0][i-1],arr[0][i]);
                st[1][arr[1][i-1]].insert(i-1);
            }
        }else{
            int l,r,v; cin >> l >> r >> v;
            auto it = st[0][v].lower_bound(l);
            if(it != st[0][v].end() && *it <= r){
                cout << *it << ' ' << *it << '\n';
            }else{
                if(l < r){
                    it = st[1][v].lower_bound(l);
                    if(it != st[1][v].end() && *it < r){
                        cout << *it << ' ' << *it+1 << '\n';
                    }else cout << "-1 -1\n";
                }else cout << "-1 -1\n";
            }
        }
    }



}   


signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while(t--){solve();}
}

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