Submission #895948

# Submission time Handle Problem Language Result Execution time Memory
895948 2023-12-31T07:47:31 Z thunopro Birthday gift (IZhO18_treearray) C++14
0 / 100
9 ms 36444 KB
#include<bits/stdc++.h>
using namespace std ; 
#define ll long long 
#define maxn 200009 
#define fi first 
#define se second 
#define pb push_back 
#define left id<<1 
#define right id<<1|1 
#define re exit(0); 
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1  

const int mod = 1e9+7 ; 
const int INF = 1e9 ; 
const int LOG = 18 ; 

typedef vector<int> vi ; 
typedef pair<int,int> pii ; 
typedef vector<ll> vl ; 
typedef vector<pii> vii ; 
 
void add ( int &a , int b ) 
{
	a += b ;
	if ( a < 0 ) a += mod ; 
	if ( a >= mod ) a -= mod ; 
}

template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; } 
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; } 

void rf () 
{
	freopen ("bai1.inp","r",stdin) ; 
//	freopen ("bai1.out","w",stdout) ; 
}

int _pow ( int a , int n ) 
{
	if ( n == 0 ) return 1 ; 
	int res = _pow (a,n/2) ; 
	if ( n % 2 ) return 1ll*res*res%mod*a%mod ; 
	else return 1ll*res*res%mod ; 
}

int n , m , nq ; 
vi adjList [maxn] ; 
int a [maxn] ; 
int tin [maxn] , tout [maxn] , timeDfs , ver [maxn] ; 
int par [maxn][20] , dep [maxn] ; 
void dfs ( int u = 1 ) 
{
	tin [u] = ++ timeDfs ; 
	ver [timeDfs] = u ; 
	for ( auto v : adjList [u] ) 
	{
		if ( v == par [u][0] ) continue ;
		par [v][0] = u , dep [v] = dep [u] + 1 ; 
		for ( int i = 1 ; i <= LOG ; i ++ ) par [v][i] = par[par[v][i-1]][i-1] ; 
		dfs (v) ; 
	}
	tout [u] = timeDfs ; 
}
int lca ( int u , int v ) 
{
	if ( dep[u]<dep[v] ) swap (u,v) ; 
	int h = dep[u]-dep[v] ; 
	for ( int i = LOG ; i >= 0 ; i -- ) if ( h >> i & 1 ) u = par[u][i] ; 
	if ( u == v ) return u ; 
	for ( int i = LOG ; i >= 0 ; i -- ) if ( par[u][i] != par[v][i] ) u = par [u][i] , v = par [v][i] ; 
	return par [u][0] ; 
}

vi T [maxn*4] ; 

vi merge ( vi u , vi v ) 
{
	vi res ; 
	int j = 0 ; 
	for ( auto x : u ) 
	{
		while ( j<v.size() && v[j]<=x ) res.pb(v[j++]) ;
		res.pb(x) ; 
	}
	while ( j < v.size() ) res.pb(v[j++]) ; 
	return res ; 
}

void update ( int id , int l , int r , int pos , int v ) 
{
	if ( l > pos || r < pos ) return ; 
	if ( l == r ) 
	{
		T [id].clear () ; 
		T [id].pb (v) ; 
		return ; 
	}
	int mid = (l+r)/2 ; 
	update (left,l,mid,pos,v) ; update (right,mid+1,r,pos,v) ; 
	T [id] = merge (T[left],T[right]) ;  
}
pii get ( int id , int l , int r , int u , int v , int low , int high )  
{
	if ( l > v || r < u ) return {n+1,0} ; 
	if ( u <= l && r <= v ) 
	{
		pii ans = {n+1,0} ; 
		if ( low <= T[id].back() ) ans.fi = *lower_bound(T[id].begin(),T[id].end(),low) ; 
		if ( high >= T[id][0] ) ans.se = *--upper_bound(T[id].begin(),T[id].end(),high) ; 
		return ans ; 
	}
	int mid = (l+r)/2 ; 
	pii L = get (left,l,mid,u,v,low,high) ; 
	pii R = get (right,mid+1,r,u,v,low,high) ; 
	return {min(L.fi,R.fi),max(L.se,R.se)} ; 
}

set <int> SET [maxn] ; 

int main () 
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0) ; 
//	rf () ; 
	cin >> n >> m >> nq ; 
	for ( int i = 1 ; i < n ; i ++ ) 
	{
		int u , v ; cin >> u >> v ;
		adjList [u] . pb (v) ; 
		adjList [v] . pb (u) ; 
	}
	
	dfs () ; 
	for ( int i = 1 ; i <= m ; i ++ ) 
	{
		cin >> a [i] ;  
		SET[a[i]].insert(i) ; 
		update (1,1,m,i,tin[a[i]]) ; 
	}
	
	while ( nq -- ) 
	{
		int op ; cin >> op ; 
		if ( op == 1 ) 
		{
			int pos , v ; cin >> pos >> v ; 
			SET[a[pos]].erase(pos) ; 
			a [pos] = v ; 
			SET[a[pos]].insert(pos) ; 
			update (1,1,m,pos,tin[v]) ; 
		}
		else 
		{
			int l , r , v ; cin >> l >> r >> v ;  
			pii got = get (1,1,m,l,r,tin[v],tout[v]) ; 
			int A = ver [got.fi] , B = ver [got.se] ; 
			if ( A > 0 && B < n+1 && lca (A,B) == v ) 
			{
				r = *SET [B].lower_bound(l) ; 
				l = *SET [A].lower_bound(l) ; 
				if ( l > r ) swap (l,r) ; 
				cout << l << " " << r << "\n" ; 
			}
			else cout << - 1 << " " << - 1 << "\n" ; 
		}
	}
}

// range , error , check speical , ... 
// find key , find key 
//'-std=c++11' stay hard 
// there is no tomorrow 

Compilation message

treearray.cpp: In function 'vi merge(vi, vi)':
treearray.cpp:82:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   while ( j<v.size() && v[j]<=x ) res.pb(v[j++]) ;
      |           ~^~~~~~~~~
treearray.cpp:85:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  while ( j < v.size() ) res.pb(v[j++]) ;
      |          ~~^~~~~~~~~~
treearray.cpp: In function 'void rf()':
treearray.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 8 ms 36440 KB n=5
2 Incorrect 9 ms 36444 KB Wrong range.
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 8 ms 36440 KB n=5
2 Incorrect 9 ms 36444 KB Wrong range.
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 8 ms 36440 KB n=5
2 Incorrect 9 ms 36444 KB Wrong range.
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 8 ms 36440 KB n=5
2 Incorrect 9 ms 36444 KB Wrong range.
3 Halted 0 ms 0 KB -