oj.uz

답안 #465860

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
465860 2021-08-16T23:54:46 Z CaroLinda Birthday gift (IZhO18_treearray) C++14
100 / 100
 2056 ms 99692 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 51908 KB n=5
2 Correct 39 ms 51988 KB n=100
3 Correct 40 ms 51872 KB n=100
4 Correct 38 ms 51964 KB n=100
5 Correct 39 ms 51936 KB n=100
6 Correct 38 ms 51928 KB n=100
7 Correct 41 ms 51916 KB n=100
8 Correct 38 ms 51908 KB n=100
9 Correct 41 ms 51964 KB n=100
10 Correct 38 ms 51980 KB n=100
11 Correct 39 ms 51900 KB n=100
12 Correct 39 ms 51864 KB n=100
13 Correct 38 ms 51916 KB n=100
14 Correct 39 ms 51884 KB n=100
15 Correct 47 ms 51924 KB n=100
16 Correct 39 ms 51968 KB n=100
17 Correct 38 ms 51916 KB n=100
18 Correct 39 ms 51928 KB n=100
19 Correct 40 ms 51924 KB n=100
20 Correct 49 ms 51964 KB n=100
21 Correct 40 ms 51908 KB n=100
22 Correct 40 ms 51964 KB n=100
23 Correct 40 ms 51952 KB n=100
24 Correct 47 ms 51896 KB n=100
25 Correct 39 ms 51908 KB n=100
26 Correct 40 ms 51968 KB n=12
27 Correct 38 ms 51960 KB n=100

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 51908 KB n=5
2 Correct 39 ms 51988 KB n=100
3 Correct 40 ms 51872 KB n=100
4 Correct 38 ms 51964 KB n=100
5 Correct 39 ms 51936 KB n=100
6 Correct 38 ms 51928 KB n=100
7 Correct 41 ms 51916 KB n=100
8 Correct 38 ms 51908 KB n=100
9 Correct 41 ms 51964 KB n=100
10 Correct 38 ms 51980 KB n=100
11 Correct 39 ms 51900 KB n=100
12 Correct 39 ms 51864 KB n=100
13 Correct 38 ms 51916 KB n=100
14 Correct 39 ms 51884 KB n=100
15 Correct 47 ms 51924 KB n=100
16 Correct 39 ms 51968 KB n=100
17 Correct 38 ms 51916 KB n=100
18 Correct 39 ms 51928 KB n=100
19 Correct 40 ms 51924 KB n=100
20 Correct 49 ms 51964 KB n=100
21 Correct 40 ms 51908 KB n=100
22 Correct 40 ms 51964 KB n=100
23 Correct 40 ms 51952 KB n=100
24 Correct 47 ms 51896 KB n=100
25 Correct 39 ms 51908 KB n=100
26 Correct 40 ms 51968 KB n=12
27 Correct 38 ms 51960 KB n=100
28 Correct 39 ms 51964 KB n=500
29 Correct 40 ms 51912 KB n=500
30 Correct 47 ms 51932 KB n=500
31 Correct 40 ms 51976 KB n=500
32 Correct 38 ms 51916 KB n=500
33 Correct 40 ms 51896 KB n=500
34 Correct 39 ms 51892 KB n=500
35 Correct 40 ms 51948 KB n=500
36 Correct 40 ms 51992 KB n=500
37 Correct 39 ms 51956 KB n=500
38 Correct 39 ms 51940 KB n=500
39 Correct 40 ms 51948 KB n=500
40 Correct 41 ms 51916 KB n=500
41 Correct 41 ms 52016 KB n=500
42 Correct 40 ms 52020 KB n=500
43 Correct 40 ms 51908 KB n=500
44 Correct 40 ms 51908 KB n=500
45 Correct 40 ms 52024 KB n=500
46 Correct 40 ms 52052 KB n=500
47 Correct 40 ms 52020 KB n=500
48 Correct 39 ms 52032 KB n=500
49 Correct 39 ms 51992 KB n=500
50 Correct 43 ms 51940 KB n=500
51 Correct 42 ms 51908 KB n=500
52 Correct 40 ms 52040 KB n=500
53 Correct 48 ms 51992 KB n=500
54 Correct 40 ms 52008 KB n=500
55 Correct 42 ms 51892 KB n=278
56 Correct 39 ms 52004 KB n=500
57 Correct 42 ms 51968 KB n=500
58 Correct 49 ms 51988 KB n=500

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 51908 KB n=5
2 Correct 39 ms 51988 KB n=100
3 Correct 40 ms 51872 KB n=100
4 Correct 38 ms 51964 KB n=100
5 Correct 39 ms 51936 KB n=100
6 Correct 38 ms 51928 KB n=100
7 Correct 41 ms 51916 KB n=100
8 Correct 38 ms 51908 KB n=100
9 Correct 41 ms 51964 KB n=100
10 Correct 38 ms 51980 KB n=100
11 Correct 39 ms 51900 KB n=100
12 Correct 39 ms 51864 KB n=100
13 Correct 38 ms 51916 KB n=100
14 Correct 39 ms 51884 KB n=100
15 Correct 47 ms 51924 KB n=100
16 Correct 39 ms 51968 KB n=100
17 Correct 38 ms 51916 KB n=100
18 Correct 39 ms 51928 KB n=100
19 Correct 40 ms 51924 KB n=100
20 Correct 49 ms 51964 KB n=100
21 Correct 40 ms 51908 KB n=100
22 Correct 40 ms 51964 KB n=100
23 Correct 40 ms 51952 KB n=100
24 Correct 47 ms 51896 KB n=100
25 Correct 39 ms 51908 KB n=100
26 Correct 40 ms 51968 KB n=12
27 Correct 38 ms 51960 KB n=100
28 Correct 39 ms 51964 KB n=500
29 Correct 40 ms 51912 KB n=500
30 Correct 47 ms 51932 KB n=500
31 Correct 40 ms 51976 KB n=500
32 Correct 38 ms 51916 KB n=500
33 Correct 40 ms 51896 KB n=500
34 Correct 39 ms 51892 KB n=500
35 Correct 40 ms 51948 KB n=500
36 Correct 40 ms 51992 KB n=500
37 Correct 39 ms 51956 KB n=500
38 Correct 39 ms 51940 KB n=500
39 Correct 40 ms 51948 KB n=500
40 Correct 41 ms 51916 KB n=500
41 Correct 41 ms 52016 KB n=500
42 Correct 40 ms 52020 KB n=500
43 Correct 40 ms 51908 KB n=500
44 Correct 40 ms 51908 KB n=500
45 Correct 40 ms 52024 KB n=500
46 Correct 40 ms 52052 KB n=500
47 Correct 40 ms 52020 KB n=500
48 Correct 39 ms 52032 KB n=500
49 Correct 39 ms 51992 KB n=500
50 Correct 43 ms 51940 KB n=500
51 Correct 42 ms 51908 KB n=500
52 Correct 40 ms 52040 KB n=500
53 Correct 48 ms 51992 KB n=500
54 Correct 40 ms 52008 KB n=500
55 Correct 42 ms 51892 KB n=278
56 Correct 39 ms 52004 KB n=500
57 Correct 42 ms 51968 KB n=500
58 Correct 49 ms 51988 KB n=500
59 Correct 42 ms 52200 KB n=2000
60 Correct 43 ms 52292 KB n=2000
61 Correct 44 ms 52240 KB n=2000
62 Correct 46 ms 52252 KB n=2000
63 Correct 43 ms 52116 KB n=2000
64 Correct 42 ms 52212 KB n=2000
65 Correct 43 ms 52140 KB n=2000
66 Correct 42 ms 52292 KB n=2000
67 Correct 43 ms 52240 KB n=2000
68 Correct 44 ms 52276 KB n=2000
69 Correct 42 ms 52236 KB n=2000
70 Correct 42 ms 52152 KB n=2000
71 Correct 41 ms 52132 KB n=2000
72 Correct 41 ms 52276 KB n=2000
73 Correct 45 ms 52136 KB n=2000
74 Correct 43 ms 52112 KB n=1844
75 Correct 42 ms 52172 KB n=2000
76 Correct 44 ms 52164 KB n=2000
77 Correct 51 ms 52220 KB n=2000
78 Correct 44 ms 52208 KB n=2000
79 Correct 43 ms 52164 KB n=2000
80 Correct 43 ms 52300 KB n=2000
81 Correct 43 ms 52248 KB n=2000
82 Correct 43 ms 52164 KB n=2000
83 Correct 46 ms 52344 KB n=2000
84 Correct 46 ms 52172 KB n=2000
85 Correct 47 ms 52200 KB n=2000
86 Correct 44 ms 52164 KB n=2000
87 Correct 43 ms 52240 KB n=2000
88 Correct 42 ms 52248 KB n=2000
89 Correct 42 ms 52236 KB n=2000
90 Correct 44 ms 52300 KB n=2000
91 Correct 41 ms 52172 KB n=2000

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 51908 KB n=5
2 Correct 39 ms 51988 KB n=100
3 Correct 40 ms 51872 KB n=100
4 Correct 38 ms 51964 KB n=100
5 Correct 39 ms 51936 KB n=100
6 Correct 38 ms 51928 KB n=100
7 Correct 41 ms 51916 KB n=100
8 Correct 38 ms 51908 KB n=100
9 Correct 41 ms 51964 KB n=100
10 Correct 38 ms 51980 KB n=100
11 Correct 39 ms 51900 KB n=100
12 Correct 39 ms 51864 KB n=100
13 Correct 38 ms 51916 KB n=100
14 Correct 39 ms 51884 KB n=100
15 Correct 47 ms 51924 KB n=100
16 Correct 39 ms 51968 KB n=100
17 Correct 38 ms 51916 KB n=100
18 Correct 39 ms 51928 KB n=100
19 Correct 40 ms 51924 KB n=100
20 Correct 49 ms 51964 KB n=100
21 Correct 40 ms 51908 KB n=100
22 Correct 40 ms 51964 KB n=100
23 Correct 40 ms 51952 KB n=100
24 Correct 47 ms 51896 KB n=100
25 Correct 39 ms 51908 KB n=100
26 Correct 40 ms 51968 KB n=12
27 Correct 38 ms 51960 KB n=100
28 Correct 39 ms 51964 KB n=500
29 Correct 40 ms 51912 KB n=500
30 Correct 47 ms 51932 KB n=500
31 Correct 40 ms 51976 KB n=500
32 Correct 38 ms 51916 KB n=500
33 Correct 40 ms 51896 KB n=500
34 Correct 39 ms 51892 KB n=500
35 Correct 40 ms 51948 KB n=500
36 Correct 40 ms 51992 KB n=500
37 Correct 39 ms 51956 KB n=500
38 Correct 39 ms 51940 KB n=500
39 Correct 40 ms 51948 KB n=500
40 Correct 41 ms 51916 KB n=500
41 Correct 41 ms 52016 KB n=500
42 Correct 40 ms 52020 KB n=500
43 Correct 40 ms 51908 KB n=500
44 Correct 40 ms 51908 KB n=500
45 Correct 40 ms 52024 KB n=500
46 Correct 40 ms 52052 KB n=500
47 Correct 40 ms 52020 KB n=500
48 Correct 39 ms 52032 KB n=500
49 Correct 39 ms 51992 KB n=500
50 Correct 43 ms 51940 KB n=500
51 Correct 42 ms 51908 KB n=500
52 Correct 40 ms 52040 KB n=500
53 Correct 48 ms 51992 KB n=500
54 Correct 40 ms 52008 KB n=500
55 Correct 42 ms 51892 KB n=278
56 Correct 39 ms 52004 KB n=500
57 Correct 42 ms 51968 KB n=500
58 Correct 49 ms 51988 KB n=500
59 Correct 42 ms 52200 KB n=2000
60 Correct 43 ms 52292 KB n=2000
61 Correct 44 ms 52240 KB n=2000
62 Correct 46 ms 52252 KB n=2000
63 Correct 43 ms 52116 KB n=2000
64 Correct 42 ms 52212 KB n=2000
65 Correct 43 ms 52140 KB n=2000
66 Correct 42 ms 52292 KB n=2000
67 Correct 43 ms 52240 KB n=2000
68 Correct 44 ms 52276 KB n=2000
69 Correct 42 ms 52236 KB n=2000
70 Correct 42 ms 52152 KB n=2000
71 Correct 41 ms 52132 KB n=2000
72 Correct 41 ms 52276 KB n=2000
73 Correct 45 ms 52136 KB n=2000
74 Correct 43 ms 52112 KB n=1844
75 Correct 42 ms 52172 KB n=2000
76 Correct 44 ms 52164 KB n=2000
77 Correct 51 ms 52220 KB n=2000
78 Correct 44 ms 52208 KB n=2000
79 Correct 43 ms 52164 KB n=2000
80 Correct 43 ms 52300 KB n=2000
81 Correct 43 ms 52248 KB n=2000
82 Correct 43 ms 52164 KB n=2000
83 Correct 46 ms 52344 KB n=2000
84 Correct 46 ms 52172 KB n=2000
85 Correct 47 ms 52200 KB n=2000
86 Correct 44 ms 52164 KB n=2000
87 Correct 43 ms 52240 KB n=2000
88 Correct 42 ms 52248 KB n=2000
89 Correct 42 ms 52236 KB n=2000
90 Correct 44 ms 52300 KB n=2000
91 Correct 41 ms 52172 KB n=2000
92 Correct 1073 ms 83708 KB n=200000
93 Correct 1875 ms 93372 KB n=200000
94 Correct 1733 ms 97984 KB n=200000
95 Correct 1114 ms 86760 KB n=200000
96 Correct 1064 ms 86960 KB n=200000
97 Correct 1791 ms 92276 KB n=200000
98 Correct 1044 ms 86784 KB n=200000
99 Correct 1355 ms 87220 KB n=200000
100 Correct 1085 ms 87028 KB n=200000
101 Correct 1776 ms 99692 KB n=200000
102 Correct 710 ms 88044 KB n=200000
103 Correct 730 ms 88096 KB n=200000
104 Correct 666 ms 88100 KB n=200000
105 Correct 659 ms 88496 KB n=200000
106 Correct 702 ms 88516 KB n=200000
107 Correct 675 ms 88560 KB n=200000
108 Correct 1457 ms 86928 KB n=200000
109 Correct 1334 ms 86984 KB n=200000
110 Correct 1376 ms 87044 KB n=200000
111 Correct 1043 ms 86360 KB n=200000
112 Correct 1881 ms 98476 KB n=200000
113 Correct 1875 ms 92240 KB n=200000
114 Correct 1031 ms 86384 KB n=200000
115 Correct 2056 ms 89428 KB n=200000
116 Correct 1103 ms 87000 KB n=200000
117 Correct 1806 ms 98940 KB n=200000
118 Correct 1906 ms 90764 KB n=200000
119 Correct 1068 ms 87056 KB n=200000
120 Correct 1764 ms 98728 KB n=200000
121 Correct 1687 ms 98776 KB n=200000
122 Correct 1838 ms 98996 KB n=200000
123 Correct 657 ms 88164 KB n=200000
124 Correct 366 ms 65148 KB n=25264