Submission #465860

#	Time	Username	Problem	Language	Result	Execution time	Memory
465860		CaroLinda	Birthday gift (IZhO18_treearray)	C++14	100 / 100	2056 ms	99692 KiB

treearray

#include <bits/stdc++.h>
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
const int MAXN = 2e5+10 ;
const int LOG = 20 ;
 
using namespace std ;
using namespace __gnu_pbds;
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
 
int N , M , Q ;
int arr[MAXN ] ;
int dp[LOG][MAXN] , lvl[MAXN] ;
vector<int> adj[MAXN] ;
ordered_set o_set[MAXN] , norma[MAXN] ;
 
void dfs(int x)
{
	for(int i = 1 ; dp[i-1][x] != -1 ; i++ )
		dp[i][x] = dp[i-1][ dp[i-1][x] ] ;
		
	for(auto e : adj[x] )
	{
		if(e == dp[0][x]) continue ;
		dp[0][e] = x ;
		lvl[e] = lvl[x]+1 ;
		dfs(e) ;
	}
}
 
int getLca(int x, int y)
{
	if(lvl[x] < lvl[y])	 swap(x,y) ;
	
	for(int i = LOG-1 ; i >= 0 ; i-- )
		if( dp[i][x] != -1 && lvl[dp[i][x]] >= lvl[y] )
			x = dp[i][x] ;
	
	if(x == y ) return x ;
	
	for(int i  = LOG-1 ; i >= 0 ; i-- )
		if(dp[i][x] != -1 && dp[i][x] != dp[i][y])
		{
			x = dp[i][x] ;
			y = dp[i][y] ;
		}
	
	return dp[0][x] ;
}
 
void op(int idx, int type )
{
	int L ;
	
	if(type == -1) norma[ arr[idx] ].erase( norma[ arr[idx] ].find(idx) ) ;
	else norma[arr[idx]].insert(idx) ;
	
	if( idx > 1 ) 
	{
		L = getLca(arr[idx-1] , arr[idx]) ;
		
		if(type == -1) o_set[L].erase( o_set[L].find(idx-1) ) ;
		else o_set[L].insert(idx-1) ;
	}
	if(idx+1 <= M)
	{
		L = getLca(arr[idx] , arr[idx+1]) ;
		
		if(type == -1) o_set[L].erase( o_set[L].find(idx) ) ;
		else o_set[L].insert(idx) ;
	}
}
 
int main()
{
	memset(dp, -1, sizeof dp );
	
	cin >> N >> M >> Q ;
	for(int i = 0 , x , y; i < N-1 ; i++ )
	{
		scanf("%d %d", &x, &y ) ;
		adj[x].push_back(y) ;
		adj[y].push_back(x) ;
	}
	
	dfs(1) ;
	
	for(int i = 1 ; i <= M ; i++ ) scanf("%d", &arr[i]) , norma[arr[i]].insert(i) ;
	for(int i = 1 ; i < M ; i++ ) o_set[ getLca(arr[i] , arr[i+1]) ].insert(i) ;
	
	while(Q--)
	{
		int t , l , r , v , pos ;
		scanf("%d", &t ) ;
		if(t == 1)
		{
			scanf("%d %d", &pos, &v ) ;
			op(pos, -1) ;
			arr[pos] = v ;
			op(pos, 1) ;
		}
		else
		{
			scanf("%d %d %d", &l, &r, &v ) ;
			
			auto aux = norma[v].lower_bound(l) ;
			if(aux != norma[v].end() && *aux <= r )
			{
				printf("%d %d\n" , *aux, *aux ) ;
				continue ;
			}
			
			auto it = o_set[v].lower_bound(l) ;
			
			if(it == o_set[v].end() || *it >= r ) 
			{
				printf("-1 -1\n") ;
				continue ;
			}
			
			
			else printf("%d %d\n", *it , (*it)+1 ) ;
		}
	}
	
}

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |   scanf("%d %d", &x, &y ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~
treearray.cpp:91:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |  for(int i = 1 ; i <= M ; i++ ) scanf("%d", &arr[i]) , norma[arr[i]].insert(i) ;
      |                                 ~~~~~^~~~~~~~~~~~~~~
treearray.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |   scanf("%d", &t ) ;
      |   ~~~~~^~~~~~~~~~~
treearray.cpp:100:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |    scanf("%d %d", &pos, &v ) ;
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~
treearray.cpp:107:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |    scanf("%d %d %d", &l, &r, &v ) ;
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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