oj.uz

Submission #41679

# Submission time Handle Problem Language Result Execution time Memory
41679 2018-02-20T12:23:18 Z IvanC Birthday gift (IZhO18_treearray) C++14
56 / 100
 4000 ms 34248 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int MAXN = 2*1e5 + 10;
vector<int> grafo[MAXN];
int ini[MAXN],dfsNum,treearray[MAXN],n,m,q;
ii vetorzao[2*MAXN],seg[8*MAXN];
void dfs(int v,int p,int depth){
	ini[v] = ++dfsNum;
	vetorzao[dfsNum] = ii(depth,v);
	for(int u : grafo[v]){
		if(u == p) continue;
		dfs(u,v,depth+1);
		vetorzao[++dfsNum] = ii(depth,v);
	}
}
void build(int pos,int left,int right){
	if(left == right){
		seg[pos] = vetorzao[left];
		return;
	}
	int mid = (left+right)/2;
	build(2*pos,left,mid);
	build(2*pos+1,mid+1,right);
	seg[pos] = min(seg[2*pos],seg[2*pos+1]);
}
ii query(int pos,int left,int right,int i,int j){
	if(left >= i && right <= j) return seg[pos];
	int mid = (left+right)/2;
	if(j <= mid) return query(2*pos,left,mid,i,j);
	else if(i >= mid + 1) return query(2*pos+1,mid+1,right,i,j);
	else return min(query(2*pos,left,mid,i,j),query(2*pos+1,mid+1,right,i,j)); 
}
ii func(int l,int r){
	return query(1,1,dfsNum,l,r);
}
int main(){
	scanf("%d %d %d",&n,&m,&q);
	for(int i = 1;i<n;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		grafo[u].push_back(v);
		grafo[v].push_back(u);
	}
	dfs(1,-1,0);
	build(1,1,dfsNum);
	for(int i = 1;i<=m;i++){
		scanf("%d",&treearray[i]);
		treearray[i] = ini[treearray[i]];
	}
	for(int pergunta = 1;pergunta<=q;pergunta++){
		int operacao;
		scanf("%d",&operacao);
		if(operacao == 1){
			int idx,v;
			scanf("%d %d",&idx,&v);
			treearray[idx] = ini[v];
		}
		else{
			int l,r,v,flag = 0;
			scanf("%d %d %d",&l,&r,&v);
			deque<ii> minQ,maxQ;
			int i = l;
			for(int j = l;j<=r && !flag;j++){
				ii novo = ii(treearray[j],j);
				while(!minQ.empty() && minQ.back() >= novo) minQ.pop_back();
				while(!maxQ.empty() && maxQ.back() <= novo) maxQ.pop_back();
				minQ.push_back(novo);
				maxQ.push_back(novo);
				while(!minQ.empty() && !maxQ.empty() && func(minQ.front().first,maxQ.front().first).first < vetorzao[ini[v]].first){
					if(minQ.front().second == i) minQ.pop_front();
					if(maxQ.front().second == i) maxQ.pop_front();
					i++;
				}
				if(!minQ.empty() && !maxQ.empty() && func(minQ.front().first,maxQ.front().first).second == v ){
					printf("%d %d\n",i,j);
					flag = 1;
				}
			}
			if(!flag) printf("-1 -1\n");
		}
	}
	return 0;
}

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:38:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&m,&q);
                            ^
treearray.cpp:41:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&u,&v);
                       ^
treearray.cpp:48:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&treearray[i]);
                            ^
treearray.cpp:53:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&operacao);
                        ^
treearray.cpp:56:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&idx,&v);
                          ^
treearray.cpp:61:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d",&l,&r,&v);
                              ^

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5056 KB n=5
2 Correct 5 ms 5092 KB n=100
3 Correct 6 ms 5288 KB n=100
4 Correct 5 ms 5288 KB n=100
5 Correct 6 ms 5288 KB n=100
6 Correct 7 ms 5288 KB n=100
7 Correct 7 ms 5304 KB n=100
8 Correct 6 ms 5304 KB n=100
9 Correct 6 ms 5304 KB n=100
10 Correct 6 ms 5304 KB n=100
11 Correct 6 ms 5304 KB n=100
12 Correct 5 ms 5304 KB n=100
13 Correct 6 ms 5304 KB n=100
14 Correct 5 ms 5304 KB n=100
15 Correct 6 ms 5304 KB n=100
16 Correct 6 ms 5304 KB n=100
17 Correct 6 ms 5304 KB n=100
18 Correct 6 ms 5304 KB n=100
19 Correct 5 ms 5304 KB n=100
20 Correct 6 ms 5304 KB n=100
21 Correct 7 ms 5304 KB n=100
22 Correct 5 ms 5304 KB n=100
23 Correct 6 ms 5304 KB n=100
24 Correct 7 ms 5304 KB n=100
25 Correct 6 ms 5304 KB n=100
26 Correct 6 ms 5304 KB n=12
27 Correct 7 ms 5304 KB n=100
28 Correct 8 ms 5340 KB n=500
29 Correct 16 ms 5340 KB n=500
30 Correct 16 ms 5340 KB n=500
31 Correct 15 ms 5380 KB n=500
32 Correct 6 ms 5380 KB n=500
33 Correct 13 ms 5380 KB n=500
34 Correct 6 ms 5380 KB n=500
35 Correct 16 ms 5380 KB n=500
36 Correct 81 ms 5380 KB n=500
37 Correct 74 ms 5380 KB n=500
38 Correct 74 ms 5468 KB n=500
39 Correct 42 ms 5468 KB n=500
40 Correct 41 ms 5468 KB n=500
41 Correct 39 ms 5468 KB n=500
42 Correct 41 ms 5468 KB n=500
43 Correct 45 ms 5468 KB n=500
44 Correct 40 ms 5468 KB n=500
45 Correct 6 ms 5468 KB n=500
46 Correct 16 ms 5468 KB n=500
47 Correct 13 ms 5468 KB n=500
48 Correct 6 ms 5468 KB n=500
49 Correct 14 ms 5468 KB n=500
50 Correct 25 ms 5468 KB n=500
51 Correct 19 ms 5468 KB n=500
52 Correct 20 ms 5468 KB n=500
53 Correct 19 ms 5468 KB n=500
54 Correct 25 ms 5472 KB n=500
55 Correct 7 ms 5472 KB n=278
56 Correct 42 ms 5472 KB n=500
57 Correct 42 ms 5472 KB n=500
58 Correct 42 ms 5472 KB n=500
59 Correct 10 ms 5472 KB n=2000
60 Correct 181 ms 5612 KB n=2000
61 Correct 186 ms 5612 KB n=2000
62 Correct 119 ms 5688 KB n=2000
63 Correct 12 ms 5688 KB n=2000
64 Correct 165 ms 5688 KB n=2000
65 Correct 9 ms 5688 KB n=2000
66 Correct 204 ms 5688 KB n=2000
67 Correct 20 ms 5688 KB n=2000
68 Correct 169 ms 5688 KB n=2000
69 Correct 1406 ms 5932 KB n=2000
70 Correct 1457 ms 5932 KB n=2000
71 Correct 1385 ms 5968 KB n=2000
72 Correct 715 ms 5968 KB n=2000
73 Correct 697 ms 5968 KB n=2000
74 Correct 8 ms 5968 KB n=1844
75 Correct 706 ms 6048 KB n=2000
76 Correct 753 ms 6048 KB n=2000
77 Correct 770 ms 6048 KB n=2000
78 Correct 766 ms 6048 KB n=2000
79 Correct 8 ms 6048 KB n=2000
80 Correct 170 ms 6180 KB n=2000
81 Correct 148 ms 6236 KB n=2000
82 Correct 9 ms 6236 KB n=2000
83 Correct 158 ms 6468 KB n=2000
84 Correct 347 ms 6468 KB n=2000
85 Correct 252 ms 6576 KB n=2000
86 Correct 252 ms 6576 KB n=2000
87 Correct 379 ms 6576 KB n=2000
88 Correct 789 ms 6816 KB n=2000
89 Correct 627 ms 6816 KB n=2000
90 Correct 450 ms 6852 KB n=2000
91 Correct 1000 ms 6904 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5056 KB n=5
2 Correct 5 ms 5092 KB n=100
3 Correct 6 ms 5288 KB n=100
4 Correct 5 ms 5288 KB n=100
5 Correct 6 ms 5288 KB n=100
6 Correct 7 ms 5288 KB n=100
7 Correct 7 ms 5304 KB n=100
8 Correct 6 ms 5304 KB n=100
9 Correct 6 ms 5304 KB n=100
10 Correct 6 ms 5304 KB n=100
11 Correct 6 ms 5304 KB n=100
12 Correct 5 ms 5304 KB n=100
13 Correct 6 ms 5304 KB n=100
14 Correct 5 ms 5304 KB n=100
15 Correct 6 ms 5304 KB n=100
16 Correct 6 ms 5304 KB n=100
17 Correct 6 ms 5304 KB n=100
18 Correct 6 ms 5304 KB n=100
19 Correct 5 ms 5304 KB n=100
20 Correct 6 ms 5304 KB n=100
21 Correct 7 ms 5304 KB n=100
22 Correct 5 ms 5304 KB n=100
23 Correct 6 ms 5304 KB n=100
24 Correct 7 ms 5304 KB n=100
25 Correct 6 ms 5304 KB n=100
26 Correct 6 ms 5304 KB n=12
27 Correct 7 ms 5304 KB n=100
28 Correct 8 ms 5340 KB n=500
29 Correct 16 ms 5340 KB n=500
30 Correct 16 ms 5340 KB n=500
31 Correct 15 ms 5380 KB n=500
32 Correct 6 ms 5380 KB n=500
33 Correct 13 ms 5380 KB n=500
34 Correct 6 ms 5380 KB n=500
35 Correct 16 ms 5380 KB n=500
36 Correct 81 ms 5380 KB n=500
37 Correct 74 ms 5380 KB n=500
38 Correct 74 ms 5468 KB n=500
39 Correct 42 ms 5468 KB n=500
40 Correct 41 ms 5468 KB n=500
41 Correct 39 ms 5468 KB n=500
42 Correct 41 ms 5468 KB n=500
43 Correct 45 ms 5468 KB n=500
44 Correct 40 ms 5468 KB n=500
45 Correct 6 ms 5468 KB n=500
46 Correct 16 ms 5468 KB n=500
47 Correct 13 ms 5468 KB n=500
48 Correct 6 ms 5468 KB n=500
49 Correct 14 ms 5468 KB n=500
50 Correct 25 ms 5468 KB n=500
51 Correct 19 ms 5468 KB n=500
52 Correct 20 ms 5468 KB n=500
53 Correct 19 ms 5468 KB n=500
54 Correct 25 ms 5472 KB n=500
55 Correct 7 ms 5472 KB n=278
56 Correct 42 ms 5472 KB n=500
57 Correct 42 ms 5472 KB n=500
58 Correct 42 ms 5472 KB n=500
59 Correct 10 ms 5472 KB n=2000
60 Correct 181 ms 5612 KB n=2000
61 Correct 186 ms 5612 KB n=2000
62 Correct 119 ms 5688 KB n=2000
63 Correct 12 ms 5688 KB n=2000
64 Correct 165 ms 5688 KB n=2000
65 Correct 9 ms 5688 KB n=2000
66 Correct 204 ms 5688 KB n=2000
67 Correct 20 ms 5688 KB n=2000
68 Correct 169 ms 5688 KB n=2000
69 Correct 1406 ms 5932 KB n=2000
70 Correct 1457 ms 5932 KB n=2000
71 Correct 1385 ms 5968 KB n=2000
72 Correct 715 ms 5968 KB n=2000
73 Correct 697 ms 5968 KB n=2000
74 Correct 8 ms 5968 KB n=1844
75 Correct 706 ms 6048 KB n=2000
76 Correct 753 ms 6048 KB n=2000
77 Correct 770 ms 6048 KB n=2000
78 Correct 766 ms 6048 KB n=2000
79 Correct 8 ms 6048 KB n=2000
80 Correct 170 ms 6180 KB n=2000
81 Correct 148 ms 6236 KB n=2000
82 Correct 9 ms 6236 KB n=2000
83 Correct 158 ms 6468 KB n=2000
84 Correct 347 ms 6468 KB n=2000
85 Correct 252 ms 6576 KB n=2000
86 Correct 252 ms 6576 KB n=2000
87 Correct 379 ms 6576 KB n=2000
88 Correct 789 ms 6816 KB n=2000
89 Correct 627 ms 6816 KB n=2000
90 Correct 450 ms 6852 KB n=2000
91 Correct 1000 ms 6904 KB n=2000
92 Execution timed out 4077 ms 34248 KB Time limit exceeded
93 Halted 0 ms 0 KB -