oj.uz

Submission #895951

# Submission time Handle Problem Language Result Execution time Memory
895951 2023-12-31T08:06:50 Z thunopro Birthday gift (IZhO18_treearray) C++14
30 / 100
 4000 ms 37364 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 ;  	
			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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 36440 KB n=5
2 Correct 9 ms 36440 KB n=100
3 Correct 9 ms 36440 KB n=100
4 Correct 8 ms 36444 KB n=100
5 Correct 8 ms 36444 KB n=100
6 Correct 18 ms 36700 KB n=100
7 Correct 16 ms 36544 KB n=100
8 Correct 9 ms 36444 KB n=100
9 Correct 9 ms 36444 KB n=100
10 Correct 12 ms 36444 KB n=100
11 Correct 14 ms 36444 KB n=100
12 Correct 8 ms 36444 KB n=100
13 Correct 8 ms 36444 KB n=100
14 Correct 8 ms 36444 KB n=100
15 Correct 9 ms 36444 KB n=100
16 Correct 9 ms 36444 KB n=100
17 Correct 9 ms 36444 KB n=100
18 Correct 9 ms 36444 KB n=100
19 Correct 8 ms 36444 KB n=100
20 Correct 9 ms 36444 KB n=100
21 Correct 9 ms 36444 KB n=100
22 Correct 8 ms 36440 KB n=100
23 Correct 10 ms 36440 KB n=100
24 Correct 11 ms 36696 KB n=100
25 Correct 9 ms 36444 KB n=100
26 Correct 8 ms 36444 KB n=12
27 Correct 11 ms 36444 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 36440 KB n=5
2 Correct 9 ms 36440 KB n=100
3 Correct 9 ms 36440 KB n=100
4 Correct 8 ms 36444 KB n=100
5 Correct 8 ms 36444 KB n=100
6 Correct 18 ms 36700 KB n=100
7 Correct 16 ms 36544 KB n=100
8 Correct 9 ms 36444 KB n=100
9 Correct 9 ms 36444 KB n=100
10 Correct 12 ms 36444 KB n=100
11 Correct 14 ms 36444 KB n=100
12 Correct 8 ms 36444 KB n=100
13 Correct 8 ms 36444 KB n=100
14 Correct 8 ms 36444 KB n=100
15 Correct 9 ms 36444 KB n=100
16 Correct 9 ms 36444 KB n=100
17 Correct 9 ms 36444 KB n=100
18 Correct 9 ms 36444 KB n=100
19 Correct 8 ms 36444 KB n=100
20 Correct 9 ms 36444 KB n=100
21 Correct 9 ms 36444 KB n=100
22 Correct 8 ms 36440 KB n=100
23 Correct 10 ms 36440 KB n=100
24 Correct 11 ms 36696 KB n=100
25 Correct 9 ms 36444 KB n=100
26 Correct 8 ms 36444 KB n=12
27 Correct 11 ms 36444 KB n=100
28 Correct 12 ms 36700 KB n=500
29 Correct 134 ms 36700 KB n=500
30 Correct 98 ms 36700 KB n=500
31 Correct 108 ms 36700 KB n=500
32 Correct 13 ms 36696 KB n=500
33 Correct 80 ms 36700 KB n=500
34 Correct 11 ms 36492 KB n=500
35 Correct 111 ms 36696 KB n=500
36 Correct 1088 ms 36692 KB n=500
37 Correct 1113 ms 36680 KB n=500
38 Correct 1100 ms 36676 KB n=500
39 Correct 131 ms 36444 KB n=500
40 Correct 118 ms 36672 KB n=500
41 Correct 115 ms 36672 KB n=500
42 Correct 545 ms 36688 KB n=500
43 Correct 552 ms 36664 KB n=500
44 Correct 525 ms 36444 KB n=500
45 Correct 12 ms 36696 KB n=500
46 Correct 116 ms 36500 KB n=500
47 Correct 98 ms 36696 KB n=500
48 Correct 13 ms 36444 KB n=500
49 Correct 93 ms 36704 KB n=500
50 Correct 95 ms 36440 KB n=500
51 Correct 155 ms 36692 KB n=500
52 Correct 197 ms 36696 KB n=500
53 Correct 149 ms 36696 KB n=500
54 Correct 85 ms 36700 KB n=500
55 Correct 27 ms 36440 KB n=278
56 Correct 694 ms 36700 KB n=500
57 Correct 724 ms 36700 KB n=500
58 Correct 432 ms 36688 KB n=500

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 36440 KB n=5
2 Correct 9 ms 36440 KB n=100
3 Correct 9 ms 36440 KB n=100
4 Correct 8 ms 36444 KB n=100
5 Correct 8 ms 36444 KB n=100
6 Correct 18 ms 36700 KB n=100
7 Correct 16 ms 36544 KB n=100
8 Correct 9 ms 36444 KB n=100
9 Correct 9 ms 36444 KB n=100
10 Correct 12 ms 36444 KB n=100
11 Correct 14 ms 36444 KB n=100
12 Correct 8 ms 36444 KB n=100
13 Correct 8 ms 36444 KB n=100
14 Correct 8 ms 36444 KB n=100
15 Correct 9 ms 36444 KB n=100
16 Correct 9 ms 36444 KB n=100
17 Correct 9 ms 36444 KB n=100
18 Correct 9 ms 36444 KB n=100
19 Correct 8 ms 36444 KB n=100
20 Correct 9 ms 36444 KB n=100
21 Correct 9 ms 36444 KB n=100
22 Correct 8 ms 36440 KB n=100
23 Correct 10 ms 36440 KB n=100
24 Correct 11 ms 36696 KB n=100
25 Correct 9 ms 36444 KB n=100
26 Correct 8 ms 36444 KB n=12
27 Correct 11 ms 36444 KB n=100
28 Correct 12 ms 36700 KB n=500
29 Correct 134 ms 36700 KB n=500
30 Correct 98 ms 36700 KB n=500
31 Correct 108 ms 36700 KB n=500
32 Correct 13 ms 36696 KB n=500
33 Correct 80 ms 36700 KB n=500
34 Correct 11 ms 36492 KB n=500
35 Correct 111 ms 36696 KB n=500
36 Correct 1088 ms 36692 KB n=500
37 Correct 1113 ms 36680 KB n=500
38 Correct 1100 ms 36676 KB n=500
39 Correct 131 ms 36444 KB n=500
40 Correct 118 ms 36672 KB n=500
41 Correct 115 ms 36672 KB n=500
42 Correct 545 ms 36688 KB n=500
43 Correct 552 ms 36664 KB n=500
44 Correct 525 ms 36444 KB n=500
45 Correct 12 ms 36696 KB n=500
46 Correct 116 ms 36500 KB n=500
47 Correct 98 ms 36696 KB n=500
48 Correct 13 ms 36444 KB n=500
49 Correct 93 ms 36704 KB n=500
50 Correct 95 ms 36440 KB n=500
51 Correct 155 ms 36692 KB n=500
52 Correct 197 ms 36696 KB n=500
53 Correct 149 ms 36696 KB n=500
54 Correct 85 ms 36700 KB n=500
55 Correct 27 ms 36440 KB n=278
56 Correct 694 ms 36700 KB n=500
57 Correct 724 ms 36700 KB n=500
58 Correct 432 ms 36688 KB n=500
59 Correct 103 ms 37364 KB n=2000
60 Execution timed out 4022 ms 37264 KB Time limit exceeded
61 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 36440 KB n=5
2 Correct 9 ms 36440 KB n=100
3 Correct 9 ms 36440 KB n=100
4 Correct 8 ms 36444 KB n=100
5 Correct 8 ms 36444 KB n=100
6 Correct 18 ms 36700 KB n=100
7 Correct 16 ms 36544 KB n=100
8 Correct 9 ms 36444 KB n=100
9 Correct 9 ms 36444 KB n=100
10 Correct 12 ms 36444 KB n=100
11 Correct 14 ms 36444 KB n=100
12 Correct 8 ms 36444 KB n=100
13 Correct 8 ms 36444 KB n=100
14 Correct 8 ms 36444 KB n=100
15 Correct 9 ms 36444 KB n=100
16 Correct 9 ms 36444 KB n=100
17 Correct 9 ms 36444 KB n=100
18 Correct 9 ms 36444 KB n=100
19 Correct 8 ms 36444 KB n=100
20 Correct 9 ms 36444 KB n=100
21 Correct 9 ms 36444 KB n=100
22 Correct 8 ms 36440 KB n=100
23 Correct 10 ms 36440 KB n=100
24 Correct 11 ms 36696 KB n=100
25 Correct 9 ms 36444 KB n=100
26 Correct 8 ms 36444 KB n=12
27 Correct 11 ms 36444 KB n=100
28 Correct 12 ms 36700 KB n=500
29 Correct 134 ms 36700 KB n=500
30 Correct 98 ms 36700 KB n=500
31 Correct 108 ms 36700 KB n=500
32 Correct 13 ms 36696 KB n=500
33 Correct 80 ms 36700 KB n=500
34 Correct 11 ms 36492 KB n=500
35 Correct 111 ms 36696 KB n=500
36 Correct 1088 ms 36692 KB n=500
37 Correct 1113 ms 36680 KB n=500
38 Correct 1100 ms 36676 KB n=500
39 Correct 131 ms 36444 KB n=500
40 Correct 118 ms 36672 KB n=500
41 Correct 115 ms 36672 KB n=500
42 Correct 545 ms 36688 KB n=500
43 Correct 552 ms 36664 KB n=500
44 Correct 525 ms 36444 KB n=500
45 Correct 12 ms 36696 KB n=500
46 Correct 116 ms 36500 KB n=500
47 Correct 98 ms 36696 KB n=500
48 Correct 13 ms 36444 KB n=500
49 Correct 93 ms 36704 KB n=500
50 Correct 95 ms 36440 KB n=500
51 Correct 155 ms 36692 KB n=500
52 Correct 197 ms 36696 KB n=500
53 Correct 149 ms 36696 KB n=500
54 Correct 85 ms 36700 KB n=500
55 Correct 27 ms 36440 KB n=278
56 Correct 694 ms 36700 KB n=500
57 Correct 724 ms 36700 KB n=500
58 Correct 432 ms 36688 KB n=500
59 Correct 103 ms 37364 KB n=2000
60 Execution timed out 4022 ms 37264 KB Time limit exceeded
61 Halted 0 ms 0 KB -