oj.uz

Submission #492388

# Submission time Handle Problem Language Result Execution time Memory
492388 2021-12-07T04:05:11 Z hohohaha Birthday gift (IZhO18_treearray) C++14
100 / 100
 960 ms 130116 KB 
// #pragma GCC optimize("Ofast")
// #pragma GCC targt("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")

#include "bits/stdc++.h"

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int> 
#define vvi vector<vi>


#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front

#define fr front
#define bc back

#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)

#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
#define sp ' '

#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

void solve();

signed main() {
// freopen("output.out","w",stdout);
   fastio();
   
   int tc = 1;
   
//   cin >> tc; 
   
   fori(test, 1, tc) {
      solve();
   }
   return 0;
}

const ld pi = 4 * atan(1.0), eps = 1e-9;

#define int long long
const int maxn = 200000 + 5, mod = 924844033; 

const int inf = LLONG_MAX / 2; 

int n; 

int m; 

int q; 

int arr[maxn], L[maxn]; 

set<int> poses[maxn], mns[maxn]; 

vi g[maxn]; 

int tin[maxn], inptr; 

int lca[maxn << 1][21]; 

int higher(int i, int j) { 
	return tin[i] < tin[j]? i: j; 
}

int getlca(int i, int j) {  
	int ll = tin[i], rr = tin[j];
	if(ll > rr) swap(ll, rr);
	
	int bit = log2(rr - ll + 1); 
	
	int rel = lca[ll][bit], rer = lca[rr - (1 << bit) + 1][bit]; 
	
	return higher(rel, rer); 
}

void dfs(int i, int p){ 
	++inptr; 
	tin[i] = inptr; 
	
	lca[inptr][0] = i; 
	
	for(int j: g[i]) { 
		if(j - p) { 
			dfs(j, i); 
			
			++inptr; 
			lca[inptr][0] = i; 
		}
	}
}

void solve() {
	cin>> n >> m >> q; 
	fori(i,1,n - 1) { 
		int u, v; cin >> u >> v; 
		g[u].eb(v);
		g[v].eb(u); 
	}
	
	dfs(1, 1); 
	fori(bit, 1, 20) {
		fori(i, 1, inptr - (1 << bit) + 1) { 
			lca[i][bit] = higher(lca[i][bit - 1], lca[i + (1 << bit - 1)][bit - 1]); 
			assert(lca[i][bit] ); 
		}
	}
	
	fori(i, 1, m) {
		cin >> arr[i]; 
		poses[arr[i]].em(i);
		if(i > 1) { 
			L[i - 1] = getlca(arr[i - 1], arr[i]); 
			mns[L[i - 1]].em(i - 1); 
		}
	}
	
	fori(i, 1, q) { 
		int tp; cin>> tp; 
		if(tp == 1) { 
			int x, y; cin>> x >> y; 
			if(x > 1) {
				mns[L[x - 1]].erase(x - 1); 
			}
			if(x < m) mns[L[x]].erase(x); 
			
			poses[arr[x]].erase(x); 
			
			arr[x] = y; 
			
			poses[arr[x]].em(x); 
			
			if(x > 1) {
				L[x - 1] = getlca(arr[x - 1], arr[x]); 
				mns[L[x - 1]].em(x - 1); 
			}
			if(x < m) {
				L[x] = getlca(arr[x], arr[x + 1]); 
				mns[L[x]].em(x); 
			}
		}
		else { 
			int l, r, y; cin >> l >> r >> y; 
			auto it = poses[y].lower_bound(l); 
			if(it != end(poses[y]) and *it <= r) { 
				cout << *it << sp << *it << endl; 
				assert(arr[*it] == y); 
			}
			
			else { 
				auto it = mns[y].lower_bound(l); 
				if(it != end(mns[y]) and *it < r) { 
					cout << *it << sp << *it + 1 << endl; 
					assert(getlca(arr[*it], arr[*it + 1]) == y); 
				}
				else { 
					cout << -1 << sp << -1 << endl;  	
				}
			}
		}
	}
}

Compilation message

treearray.cpp: In function 'void solve()':
treearray.cpp:131:60: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  131 |    lca[i][bit] = higher(lca[i][bit - 1], lca[i + (1 << bit - 1)][bit - 1]);
      |                                                        ~~~~^~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB n=5
2 Correct 12 ms 23828 KB n=100
3 Correct 11 ms 23756 KB n=100
4 Correct 15 ms 23800 KB n=100
5 Correct 12 ms 23756 KB n=100
6 Correct 12 ms 23764 KB n=100
7 Correct 14 ms 23820 KB n=100
8 Correct 12 ms 23756 KB n=100
9 Correct 11 ms 23756 KB n=100
10 Correct 14 ms 23756 KB n=100
11 Correct 11 ms 23808 KB n=100
12 Correct 11 ms 23756 KB n=100
13 Correct 11 ms 23836 KB n=100
14 Correct 11 ms 23756 KB n=100
15 Correct 12 ms 23876 KB n=100
16 Correct 11 ms 23756 KB n=100
17 Correct 12 ms 23756 KB n=100
18 Correct 15 ms 23756 KB n=100
19 Correct 12 ms 23820 KB n=100
20 Correct 12 ms 23884 KB n=100
21 Correct 11 ms 23876 KB n=100
22 Correct 13 ms 23884 KB n=100
23 Correct 13 ms 23880 KB n=100
24 Correct 12 ms 23756 KB n=100
25 Correct 11 ms 23756 KB n=100
26 Correct 12 ms 23756 KB n=12
27 Correct 12 ms 23808 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB n=5
2 Correct 12 ms 23828 KB n=100
3 Correct 11 ms 23756 KB n=100
4 Correct 15 ms 23800 KB n=100
5 Correct 12 ms 23756 KB n=100
6 Correct 12 ms 23764 KB n=100
7 Correct 14 ms 23820 KB n=100
8 Correct 12 ms 23756 KB n=100
9 Correct 11 ms 23756 KB n=100
10 Correct 14 ms 23756 KB n=100
11 Correct 11 ms 23808 KB n=100
12 Correct 11 ms 23756 KB n=100
13 Correct 11 ms 23836 KB n=100
14 Correct 11 ms 23756 KB n=100
15 Correct 12 ms 23876 KB n=100
16 Correct 11 ms 23756 KB n=100
17 Correct 12 ms 23756 KB n=100
18 Correct 15 ms 23756 KB n=100
19 Correct 12 ms 23820 KB n=100
20 Correct 12 ms 23884 KB n=100
21 Correct 11 ms 23876 KB n=100
22 Correct 13 ms 23884 KB n=100
23 Correct 13 ms 23880 KB n=100
24 Correct 12 ms 23756 KB n=100
25 Correct 11 ms 23756 KB n=100
26 Correct 12 ms 23756 KB n=12
27 Correct 12 ms 23808 KB n=100
28 Correct 11 ms 24012 KB n=500
29 Correct 12 ms 24076 KB n=500
30 Correct 12 ms 24012 KB n=500
31 Correct 14 ms 24012 KB n=500
32 Correct 12 ms 24012 KB n=500
33 Correct 13 ms 24012 KB n=500
34 Correct 14 ms 24012 KB n=500
35 Correct 12 ms 24012 KB n=500
36 Correct 13 ms 24076 KB n=500
37 Correct 12 ms 24012 KB n=500
38 Correct 12 ms 24076 KB n=500
39 Correct 12 ms 23968 KB n=500
40 Correct 13 ms 24040 KB n=500
41 Correct 15 ms 24012 KB n=500
42 Correct 12 ms 24012 KB n=500
43 Correct 13 ms 24012 KB n=500
44 Correct 12 ms 24068 KB n=500
45 Correct 12 ms 24068 KB n=500
46 Correct 12 ms 24012 KB n=500
47 Correct 13 ms 24056 KB n=500
48 Correct 13 ms 24020 KB n=500
49 Correct 12 ms 24012 KB n=500
50 Correct 13 ms 24076 KB n=500
51 Correct 12 ms 24012 KB n=500
52 Correct 12 ms 24020 KB n=500
53 Correct 13 ms 24012 KB n=500
54 Correct 13 ms 24088 KB n=500
55 Correct 13 ms 23992 KB n=278
56 Correct 12 ms 24024 KB n=500
57 Correct 12 ms 24012 KB n=500
58 Correct 12 ms 24056 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB n=5
2 Correct 12 ms 23828 KB n=100
3 Correct 11 ms 23756 KB n=100
4 Correct 15 ms 23800 KB n=100
5 Correct 12 ms 23756 KB n=100
6 Correct 12 ms 23764 KB n=100
7 Correct 14 ms 23820 KB n=100
8 Correct 12 ms 23756 KB n=100
9 Correct 11 ms 23756 KB n=100
10 Correct 14 ms 23756 KB n=100
11 Correct 11 ms 23808 KB n=100
12 Correct 11 ms 23756 KB n=100
13 Correct 11 ms 23836 KB n=100
14 Correct 11 ms 23756 KB n=100
15 Correct 12 ms 23876 KB n=100
16 Correct 11 ms 23756 KB n=100
17 Correct 12 ms 23756 KB n=100
18 Correct 15 ms 23756 KB n=100
19 Correct 12 ms 23820 KB n=100
20 Correct 12 ms 23884 KB n=100
21 Correct 11 ms 23876 KB n=100
22 Correct 13 ms 23884 KB n=100
23 Correct 13 ms 23880 KB n=100
24 Correct 12 ms 23756 KB n=100
25 Correct 11 ms 23756 KB n=100
26 Correct 12 ms 23756 KB n=12
27 Correct 12 ms 23808 KB n=100
28 Correct 11 ms 24012 KB n=500
29 Correct 12 ms 24076 KB n=500
30 Correct 12 ms 24012 KB n=500
31 Correct 14 ms 24012 KB n=500
32 Correct 12 ms 24012 KB n=500
33 Correct 13 ms 24012 KB n=500
34 Correct 14 ms 24012 KB n=500
35 Correct 12 ms 24012 KB n=500
36 Correct 13 ms 24076 KB n=500
37 Correct 12 ms 24012 KB n=500
38 Correct 12 ms 24076 KB n=500
39 Correct 12 ms 23968 KB n=500
40 Correct 13 ms 24040 KB n=500
41 Correct 15 ms 24012 KB n=500
42 Correct 12 ms 24012 KB n=500
43 Correct 13 ms 24012 KB n=500
44 Correct 12 ms 24068 KB n=500
45 Correct 12 ms 24068 KB n=500
46 Correct 12 ms 24012 KB n=500
47 Correct 13 ms 24056 KB n=500
48 Correct 13 ms 24020 KB n=500
49 Correct 12 ms 24012 KB n=500
50 Correct 13 ms 24076 KB n=500
51 Correct 12 ms 24012 KB n=500
52 Correct 12 ms 24020 KB n=500
53 Correct 13 ms 24012 KB n=500
54 Correct 13 ms 24088 KB n=500
55 Correct 13 ms 23992 KB n=278
56 Correct 12 ms 24024 KB n=500
57 Correct 12 ms 24012 KB n=500
58 Correct 12 ms 24056 KB n=500
59 Correct 13 ms 24780 KB n=2000
60 Correct 13 ms 24864 KB n=2000
61 Correct 19 ms 24740 KB n=2000
62 Correct 15 ms 24780 KB n=2000
63 Correct 17 ms 24780 KB n=2000
64 Correct 14 ms 24792 KB n=2000
65 Correct 15 ms 24780 KB n=2000
66 Correct 15 ms 24868 KB n=2000
67 Correct 14 ms 24804 KB n=2000
68 Correct 15 ms 24780 KB n=2000
69 Correct 14 ms 24752 KB n=2000
70 Correct 14 ms 24780 KB n=2000
71 Correct 14 ms 24728 KB n=2000
72 Correct 14 ms 24780 KB n=2000
73 Correct 17 ms 24780 KB n=2000
74 Correct 17 ms 24652 KB n=1844
75 Correct 16 ms 24780 KB n=2000
76 Correct 16 ms 24720 KB n=2000
77 Correct 16 ms 24780 KB n=2000
78 Correct 19 ms 24804 KB n=2000
79 Correct 14 ms 24780 KB n=2000
80 Correct 15 ms 24780 KB n=2000
81 Correct 15 ms 24836 KB n=2000
82 Correct 16 ms 24776 KB n=2000
83 Correct 13 ms 24780 KB n=2000
84 Correct 18 ms 24780 KB n=2000
85 Correct 17 ms 24828 KB n=2000
86 Correct 15 ms 24796 KB n=2000
87 Correct 15 ms 24780 KB n=2000
88 Correct 14 ms 24780 KB n=2000
89 Correct 16 ms 24780 KB n=2000
90 Correct 15 ms 24784 KB n=2000
91 Correct 18 ms 24756 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB n=5
2 Correct 12 ms 23828 KB n=100
3 Correct 11 ms 23756 KB n=100
4 Correct 15 ms 23800 KB n=100
5 Correct 12 ms 23756 KB n=100
6 Correct 12 ms 23764 KB n=100
7 Correct 14 ms 23820 KB n=100
8 Correct 12 ms 23756 KB n=100
9 Correct 11 ms 23756 KB n=100
10 Correct 14 ms 23756 KB n=100
11 Correct 11 ms 23808 KB n=100
12 Correct 11 ms 23756 KB n=100
13 Correct 11 ms 23836 KB n=100
14 Correct 11 ms 23756 KB n=100
15 Correct 12 ms 23876 KB n=100
16 Correct 11 ms 23756 KB n=100
17 Correct 12 ms 23756 KB n=100
18 Correct 15 ms 23756 KB n=100
19 Correct 12 ms 23820 KB n=100
20 Correct 12 ms 23884 KB n=100
21 Correct 11 ms 23876 KB n=100
22 Correct 13 ms 23884 KB n=100
23 Correct 13 ms 23880 KB n=100
24 Correct 12 ms 23756 KB n=100
25 Correct 11 ms 23756 KB n=100
26 Correct 12 ms 23756 KB n=12
27 Correct 12 ms 23808 KB n=100
28 Correct 11 ms 24012 KB n=500
29 Correct 12 ms 24076 KB n=500
30 Correct 12 ms 24012 KB n=500
31 Correct 14 ms 24012 KB n=500
32 Correct 12 ms 24012 KB n=500
33 Correct 13 ms 24012 KB n=500
34 Correct 14 ms 24012 KB n=500
35 Correct 12 ms 24012 KB n=500
36 Correct 13 ms 24076 KB n=500
37 Correct 12 ms 24012 KB n=500
38 Correct 12 ms 24076 KB n=500
39 Correct 12 ms 23968 KB n=500
40 Correct 13 ms 24040 KB n=500
41 Correct 15 ms 24012 KB n=500
42 Correct 12 ms 24012 KB n=500
43 Correct 13 ms 24012 KB n=500
44 Correct 12 ms 24068 KB n=500
45 Correct 12 ms 24068 KB n=500
46 Correct 12 ms 24012 KB n=500
47 Correct 13 ms 24056 KB n=500
48 Correct 13 ms 24020 KB n=500
49 Correct 12 ms 24012 KB n=500
50 Correct 13 ms 24076 KB n=500
51 Correct 12 ms 24012 KB n=500
52 Correct 12 ms 24020 KB n=500
53 Correct 13 ms 24012 KB n=500
54 Correct 13 ms 24088 KB n=500
55 Correct 13 ms 23992 KB n=278
56 Correct 12 ms 24024 KB n=500
57 Correct 12 ms 24012 KB n=500
58 Correct 12 ms 24056 KB n=500
59 Correct 13 ms 24780 KB n=2000
60 Correct 13 ms 24864 KB n=2000
61 Correct 19 ms 24740 KB n=2000
62 Correct 15 ms 24780 KB n=2000
63 Correct 17 ms 24780 KB n=2000
64 Correct 14 ms 24792 KB n=2000
65 Correct 15 ms 24780 KB n=2000
66 Correct 15 ms 24868 KB n=2000
67 Correct 14 ms 24804 KB n=2000
68 Correct 15 ms 24780 KB n=2000
69 Correct 14 ms 24752 KB n=2000
70 Correct 14 ms 24780 KB n=2000
71 Correct 14 ms 24728 KB n=2000
72 Correct 14 ms 24780 KB n=2000
73 Correct 17 ms 24780 KB n=2000
74 Correct 17 ms 24652 KB n=1844
75 Correct 16 ms 24780 KB n=2000
76 Correct 16 ms 24720 KB n=2000
77 Correct 16 ms 24780 KB n=2000
78 Correct 19 ms 24804 KB n=2000
79 Correct 14 ms 24780 KB n=2000
80 Correct 15 ms 24780 KB n=2000
81 Correct 15 ms 24836 KB n=2000
82 Correct 16 ms 24776 KB n=2000
83 Correct 13 ms 24780 KB n=2000
84 Correct 18 ms 24780 KB n=2000
85 Correct 17 ms 24828 KB n=2000
86 Correct 15 ms 24796 KB n=2000
87 Correct 15 ms 24780 KB n=2000
88 Correct 14 ms 24780 KB n=2000
89 Correct 16 ms 24780 KB n=2000
90 Correct 15 ms 24784 KB n=2000
91 Correct 18 ms 24756 KB n=2000
92 Correct 719 ms 122088 KB n=200000
93 Correct 755 ms 125904 KB n=200000
94 Correct 743 ms 128628 KB n=200000
95 Correct 744 ms 121896 KB n=200000
96 Correct 630 ms 121872 KB n=200000
97 Correct 811 ms 125092 KB n=200000
98 Correct 759 ms 122032 KB n=200000
99 Correct 960 ms 122020 KB n=200000
100 Correct 822 ms 122300 KB n=200000
101 Correct 794 ms 130052 KB n=200000
102 Correct 532 ms 123404 KB n=200000
103 Correct 540 ms 123392 KB n=200000
104 Correct 552 ms 123372 KB n=200000
105 Correct 497 ms 123288 KB n=200000
106 Correct 503 ms 123272 KB n=200000
107 Correct 520 ms 123372 KB n=200000
108 Correct 795 ms 122268 KB n=200000
109 Correct 735 ms 122292 KB n=200000
110 Correct 801 ms 122384 KB n=200000
111 Correct 740 ms 122216 KB n=200000
112 Correct 733 ms 129384 KB n=200000
113 Correct 800 ms 125500 KB n=200000
114 Correct 831 ms 122436 KB n=200000
115 Correct 959 ms 123332 KB n=200000
116 Correct 691 ms 122288 KB n=200000
117 Correct 682 ms 129536 KB n=200000
118 Correct 797 ms 124176 KB n=200000
119 Correct 705 ms 122068 KB n=200000
120 Correct 671 ms 129936 KB n=200000
121 Correct 687 ms 129852 KB n=200000
122 Correct 688 ms 130116 KB n=200000
123 Correct 520 ms 123060 KB n=200000
124 Correct 200 ms 44676 KB n=25264