Submission #895951

#	Time	Username	Problem	Language	Result	Execution time	Memory
895951		thunopro	Birthday gift (IZhO18_treearray)	C++14	30 / 100	4022 ms	37364 KiB

treearray

#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 ;  	
			int res_l = - 1 , res_r = - 1 ; 
			for ( int i = l ; i <= r ; i ++ ) 
			{
				int _lca = a [i] ; 
				for ( int j = i ; j <= r && res_l == - 1 ; j ++ ) 
				{
					_lca = lca (_lca,a[j]) ; 
					if ( _lca == v ) 
					{
						res_l = i , res_r = j ; 
					}
				}
			}
			cout << res_l << " " << res_r << "\n" ; 
		}
	}
}

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

Compilation message (stderr)

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) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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