oj.uz

Submission #887386

# Submission time Handle Problem Language Result Execution time Memory
887386 2023-12-14T11:27:16 Z pcc Birthday gift (IZhO18_treearray) C++14
100 / 100
 906 ms 80980 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define mid ((l+r)>>1)

const int mxn = 2e5+10;
int n,m,q;
pii dfn[mxn];
int par[mxn][20];
int dep[mxn];
vector<int> tree[mxn];
int arr[mxn];
int ppp = 0;
set<pii> ap[mxn];

void dfs(int now){
	for(int i = 1;i<20;i++)par[now][i] = par[par[now][i-1]][i-1];
	for(auto nxt:tree[now]){
		if(nxt == par[now][0])continue;
		dep[nxt] = dep[now]+1;
		par[nxt][0] = now;
		dfs(nxt);
	}
	return;
}

int anc(int a,int b){
	if(dep[a]<dep[b])swap(a,b);
	int d = dep[a]-dep[b];
	for(int i = 19;i>=0;i--){
		if(d&(1<<i))a = par[a][i];
	}
	for(int i = 19;i>=0;i--){
		if(par[a][i] != par[b][i])a = par[a][i],b = par[b][i];
	}
	return a==b?a:par[a][0];
}

void build(){
	for(int i = 1;i<=m;i++){
		ap[arr[i]].insert({i,i});
	}
	for(int i = 2;i<=m;i++){
		ap[anc(arr[i-1],arr[i])].insert({i-1,i});
	}
	return;
}

void modify(int p,int v){
	ap[arr[p]].erase({p,p});
	if(p>1)ap[anc(arr[p-1],arr[p])].erase({p-1,p});
	if(p<m)ap[anc(arr[p],arr[p+1])].erase({p,p+1});
	arr[p] = v;
	ap[arr[p]].insert({p,p});
	if(p>1)ap[anc(arr[p-1],arr[p])].insert({p-1,p});
	if(p<m)ap[anc(arr[p],arr[p+1])].insert({p,p+1});
	return;
}
pii getval(int l,int r,int tar){
	auto it = ap[tar].lower_bound({l,-1});
	if(it == ap[tar].end()||it->sc>r)return {-1,-1};
	else return *it;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m>>q;
	for(int i = 1;i<n;i++){
		int a,b;
		cin>>a>>b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	for(int i = 1;i<=m;i++){
		cin>>arr[i];
	}
	par[1][0] = 1;
	dfs(1);
	build();
	//for(auto &i:segtree[0])cout<<i.fs<<' '<<i.sc.fs<<','<<i.sc.sc<<';';
	while(q--){
		int tp;
		cin>>tp;
		if(tp == 1){
			int p,v;
			cin>>p>>v;
			modify(p,v);
		}
		else{
			int l,r,v;
			cin>>l>>r>>v;
			auto re = getval(l,r,v);
			cout<<re.fs<<' '<<re.sc<<'\n';
		}
	}
	return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB n=5
2 Correct 4 ms 16988 KB n=100
3 Correct 3 ms 16988 KB n=100
4 Correct 3 ms 16988 KB n=100
5 Correct 5 ms 16984 KB n=100
6 Correct 3 ms 16984 KB n=100
7 Correct 3 ms 16988 KB n=100
8 Correct 3 ms 16988 KB n=100
9 Correct 3 ms 16988 KB n=100
10 Correct 3 ms 16988 KB n=100
11 Correct 3 ms 16988 KB n=100
12 Correct 3 ms 16988 KB n=100
13 Correct 3 ms 16984 KB n=100
14 Correct 3 ms 16988 KB n=100
15 Correct 3 ms 16988 KB n=100
16 Correct 4 ms 16988 KB n=100
17 Correct 3 ms 16988 KB n=100
18 Correct 3 ms 16988 KB n=100
19 Correct 3 ms 16988 KB n=100
20 Correct 3 ms 16988 KB n=100
21 Correct 4 ms 16988 KB n=100
22 Correct 4 ms 17312 KB n=100
23 Correct 3 ms 16988 KB n=100
24 Correct 3 ms 16988 KB n=100
25 Correct 3 ms 16988 KB n=100
26 Correct 3 ms 16988 KB n=12
27 Correct 3 ms 16988 KB n=100
28 Correct 4 ms 16984 KB n=500
29 Correct 5 ms 16988 KB n=500
30 Correct 4 ms 16988 KB n=500
31 Correct 4 ms 16988 KB n=500
32 Correct 4 ms 16984 KB n=500
33 Correct 4 ms 17184 KB n=500
34 Correct 6 ms 16988 KB n=500
35 Correct 4 ms 16988 KB n=500
36 Correct 4 ms 17240 KB n=500
37 Correct 4 ms 16988 KB n=500
38 Correct 3 ms 16988 KB n=500
39 Correct 4 ms 16988 KB n=500
40 Correct 4 ms 16988 KB n=500
41 Correct 5 ms 16988 KB n=500
42 Correct 4 ms 16988 KB n=500
43 Correct 4 ms 16988 KB n=500
44 Correct 4 ms 16988 KB n=500
45 Correct 4 ms 17120 KB n=500
46 Correct 4 ms 16988 KB n=500
47 Correct 4 ms 16988 KB n=500
48 Correct 4 ms 16984 KB n=500
49 Correct 4 ms 16988 KB n=500
50 Correct 4 ms 16988 KB n=500
51 Correct 4 ms 16988 KB n=500
52 Correct 4 ms 16988 KB n=500
53 Correct 4 ms 16988 KB n=500
54 Correct 4 ms 16988 KB n=500
55 Correct 4 ms 16988 KB n=278
56 Correct 5 ms 16984 KB n=500
57 Correct 4 ms 17240 KB n=500
58 Correct 4 ms 16988 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB n=5
2 Correct 4 ms 16988 KB n=100
3 Correct 3 ms 16988 KB n=100
4 Correct 3 ms 16988 KB n=100
5 Correct 5 ms 16984 KB n=100
6 Correct 3 ms 16984 KB n=100
7 Correct 3 ms 16988 KB n=100
8 Correct 3 ms 16988 KB n=100
9 Correct 3 ms 16988 KB n=100
10 Correct 3 ms 16988 KB n=100
11 Correct 3 ms 16988 KB n=100
12 Correct 3 ms 16988 KB n=100
13 Correct 3 ms 16984 KB n=100
14 Correct 3 ms 16988 KB n=100
15 Correct 3 ms 16988 KB n=100
16 Correct 4 ms 16988 KB n=100
17 Correct 3 ms 16988 KB n=100
18 Correct 3 ms 16988 KB n=100
19 Correct 3 ms 16988 KB n=100
20 Correct 3 ms 16988 KB n=100
21 Correct 4 ms 16988 KB n=100
22 Correct 4 ms 17312 KB n=100
23 Correct 3 ms 16988 KB n=100
24 Correct 3 ms 16988 KB n=100
25 Correct 3 ms 16988 KB n=100
26 Correct 3 ms 16988 KB n=12
27 Correct 3 ms 16988 KB n=100
28 Correct 4 ms 16984 KB n=500
29 Correct 5 ms 16988 KB n=500
30 Correct 4 ms 16988 KB n=500
31 Correct 4 ms 16988 KB n=500
32 Correct 4 ms 16984 KB n=500
33 Correct 4 ms 17184 KB n=500
34 Correct 6 ms 16988 KB n=500
35 Correct 4 ms 16988 KB n=500
36 Correct 4 ms 17240 KB n=500
37 Correct 4 ms 16988 KB n=500
38 Correct 3 ms 16988 KB n=500
39 Correct 4 ms 16988 KB n=500
40 Correct 4 ms 16988 KB n=500
41 Correct 5 ms 16988 KB n=500
42 Correct 4 ms 16988 KB n=500
43 Correct 4 ms 16988 KB n=500
44 Correct 4 ms 16988 KB n=500
45 Correct 4 ms 17120 KB n=500
46 Correct 4 ms 16988 KB n=500
47 Correct 4 ms 16988 KB n=500
48 Correct 4 ms 16984 KB n=500
49 Correct 4 ms 16988 KB n=500
50 Correct 4 ms 16988 KB n=500
51 Correct 4 ms 16988 KB n=500
52 Correct 4 ms 16988 KB n=500
53 Correct 4 ms 16988 KB n=500
54 Correct 4 ms 16988 KB n=500
55 Correct 4 ms 16988 KB n=278
56 Correct 5 ms 16984 KB n=500
57 Correct 4 ms 17240 KB n=500
58 Correct 4 ms 16988 KB n=500
59 Correct 6 ms 17244 KB n=2000
60 Correct 6 ms 17244 KB n=2000
61 Correct 6 ms 17244 KB n=2000
62 Correct 6 ms 17244 KB n=2000
63 Correct 7 ms 17240 KB n=2000
64 Correct 6 ms 17244 KB n=2000
65 Correct 6 ms 17244 KB n=2000
66 Correct 6 ms 17380 KB n=2000
67 Correct 7 ms 17240 KB n=2000
68 Correct 6 ms 17240 KB n=2000
69 Correct 5 ms 17244 KB n=2000
70 Correct 5 ms 17240 KB n=2000
71 Correct 5 ms 17244 KB n=2000
72 Correct 5 ms 17244 KB n=2000
73 Correct 5 ms 17244 KB n=2000
74 Correct 6 ms 17244 KB n=1844
75 Correct 5 ms 17244 KB n=2000
76 Correct 8 ms 17400 KB n=2000
77 Correct 6 ms 17240 KB n=2000
78 Correct 6 ms 17240 KB n=2000
79 Correct 6 ms 17244 KB n=2000
80 Correct 6 ms 17244 KB n=2000
81 Correct 7 ms 17244 KB n=2000
82 Correct 6 ms 17244 KB n=2000
83 Correct 6 ms 17276 KB n=2000
84 Correct 6 ms 17244 KB n=2000
85 Correct 6 ms 17244 KB n=2000
86 Correct 6 ms 17244 KB n=2000
87 Correct 6 ms 17244 KB n=2000
88 Correct 6 ms 17244 KB n=2000
89 Correct 7 ms 17244 KB n=2000
90 Correct 6 ms 17240 KB n=2000
91 Correct 6 ms 17496 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB n=5
2 Correct 4 ms 16988 KB n=100
3 Correct 3 ms 16988 KB n=100
4 Correct 3 ms 16988 KB n=100
5 Correct 5 ms 16984 KB n=100
6 Correct 3 ms 16984 KB n=100
7 Correct 3 ms 16988 KB n=100
8 Correct 3 ms 16988 KB n=100
9 Correct 3 ms 16988 KB n=100
10 Correct 3 ms 16988 KB n=100
11 Correct 3 ms 16988 KB n=100
12 Correct 3 ms 16988 KB n=100
13 Correct 3 ms 16984 KB n=100
14 Correct 3 ms 16988 KB n=100
15 Correct 3 ms 16988 KB n=100
16 Correct 4 ms 16988 KB n=100
17 Correct 3 ms 16988 KB n=100
18 Correct 3 ms 16988 KB n=100
19 Correct 3 ms 16988 KB n=100
20 Correct 3 ms 16988 KB n=100
21 Correct 4 ms 16988 KB n=100
22 Correct 4 ms 17312 KB n=100
23 Correct 3 ms 16988 KB n=100
24 Correct 3 ms 16988 KB n=100
25 Correct 3 ms 16988 KB n=100
26 Correct 3 ms 16988 KB n=12
27 Correct 3 ms 16988 KB n=100
28 Correct 4 ms 16984 KB n=500
29 Correct 5 ms 16988 KB n=500
30 Correct 4 ms 16988 KB n=500
31 Correct 4 ms 16988 KB n=500
32 Correct 4 ms 16984 KB n=500
33 Correct 4 ms 17184 KB n=500
34 Correct 6 ms 16988 KB n=500
35 Correct 4 ms 16988 KB n=500
36 Correct 4 ms 17240 KB n=500
37 Correct 4 ms 16988 KB n=500
38 Correct 3 ms 16988 KB n=500
39 Correct 4 ms 16988 KB n=500
40 Correct 4 ms 16988 KB n=500
41 Correct 5 ms 16988 KB n=500
42 Correct 4 ms 16988 KB n=500
43 Correct 4 ms 16988 KB n=500
44 Correct 4 ms 16988 KB n=500
45 Correct 4 ms 17120 KB n=500
46 Correct 4 ms 16988 KB n=500
47 Correct 4 ms 16988 KB n=500
48 Correct 4 ms 16984 KB n=500
49 Correct 4 ms 16988 KB n=500
50 Correct 4 ms 16988 KB n=500
51 Correct 4 ms 16988 KB n=500
52 Correct 4 ms 16988 KB n=500
53 Correct 4 ms 16988 KB n=500
54 Correct 4 ms 16988 KB n=500
55 Correct 4 ms 16988 KB n=278
56 Correct 5 ms 16984 KB n=500
57 Correct 4 ms 17240 KB n=500
58 Correct 4 ms 16988 KB n=500
59 Correct 6 ms 17244 KB n=2000
60 Correct 6 ms 17244 KB n=2000
61 Correct 6 ms 17244 KB n=2000
62 Correct 6 ms 17244 KB n=2000
63 Correct 7 ms 17240 KB n=2000
64 Correct 6 ms 17244 KB n=2000
65 Correct 6 ms 17244 KB n=2000
66 Correct 6 ms 17380 KB n=2000
67 Correct 7 ms 17240 KB n=2000
68 Correct 6 ms 17240 KB n=2000
69 Correct 5 ms 17244 KB n=2000
70 Correct 5 ms 17240 KB n=2000
71 Correct 5 ms 17244 KB n=2000
72 Correct 5 ms 17244 KB n=2000
73 Correct 5 ms 17244 KB n=2000
74 Correct 6 ms 17244 KB n=1844
75 Correct 5 ms 17244 KB n=2000
76 Correct 8 ms 17400 KB n=2000
77 Correct 6 ms 17240 KB n=2000
78 Correct 6 ms 17240 KB n=2000
79 Correct 6 ms 17244 KB n=2000
80 Correct 6 ms 17244 KB n=2000
81 Correct 7 ms 17244 KB n=2000
82 Correct 6 ms 17244 KB n=2000
83 Correct 6 ms 17276 KB n=2000
84 Correct 6 ms 17244 KB n=2000
85 Correct 6 ms 17244 KB n=2000
86 Correct 6 ms 17244 KB n=2000
87 Correct 6 ms 17244 KB n=2000
88 Correct 6 ms 17244 KB n=2000
89 Correct 7 ms 17244 KB n=2000
90 Correct 6 ms 17240 KB n=2000
91 Correct 6 ms 17496 KB n=2000
92 Correct 569 ms 61844 KB n=200000
93 Correct 783 ms 73276 KB n=200000
94 Correct 805 ms 79116 KB n=200000
95 Correct 533 ms 65060 KB n=200000
96 Correct 596 ms 65060 KB n=200000
97 Correct 825 ms 71620 KB n=200000
98 Correct 592 ms 64936 KB n=200000
99 Correct 688 ms 65400 KB n=200000
100 Correct 558 ms 64996 KB n=200000
101 Correct 840 ms 80980 KB n=200000
102 Correct 290 ms 66404 KB n=200000
103 Correct 292 ms 66152 KB n=200000
104 Correct 279 ms 66248 KB n=200000
105 Correct 280 ms 66644 KB n=200000
106 Correct 291 ms 66776 KB n=200000
107 Correct 287 ms 66724 KB n=200000
108 Correct 645 ms 65244 KB n=200000
109 Correct 582 ms 64968 KB n=200000
110 Correct 603 ms 65176 KB n=200000
111 Correct 551 ms 64564 KB n=200000
112 Correct 795 ms 79264 KB n=200000
113 Correct 760 ms 71536 KB n=200000
114 Correct 558 ms 64584 KB n=200000
115 Correct 817 ms 67968 KB n=200000
116 Correct 527 ms 65088 KB n=200000
117 Correct 749 ms 80284 KB n=200000
118 Correct 796 ms 70048 KB n=200000
119 Correct 528 ms 65220 KB n=200000
120 Correct 756 ms 79796 KB n=200000
121 Correct 906 ms 80008 KB n=200000
122 Correct 893 ms 80136 KB n=200000
123 Correct 361 ms 66384 KB n=200000
124 Correct 149 ms 32348 KB n=25264