Codeforces Round 881 (Div. 3)


A. Sasha and Array Coloring
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
5
1 5 6 3 4
1
5
4
1 6 3 9
6
1 13 9 3 7 2
4
2 2 2 2
5
4 5 2 2 3
Output
7
0
11
23
0
5
----------------------------------------------------------------------------------------------------
B. Long Long
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
6
-1 7 -4 -2 5 -8
8
-1 0 0 -2 1 0 -3 0
5
2 -1 0 -3 -7
5
0 -17 0 1 0
4
-1 0 -2 -1
Output
27 3
7 2
13 1
18 1
4 1
----------------------------------------------------------------------------------------------------
C. Sum in Binary Tree
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
3
10
37
1
10000000000000000
15
Output
4
18
71
1
19999999999999980
26
----------------------------------------------------------------------------------------------------
D. Apple Tree
time limit per test: 4 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
2
5
1 2
3 4
5 3
3 2
4
3 4
5 1
4 4
1 3
3
1 2
1 3
3
1 1
2 3
3 1
Output
2
2
1
4
4
1
2
Input
2
5
5 1
1 2
2 3
4 3
2
5 5
5 1
5
3 2
5 3
2 1
4 2
3
4 3
2 1
4 2
Output
1
2
1
4
2
----------------------------------------------------------------------------------------------------
E. Tracking Segments
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
5 5
1 2
4 5
1 5
1 3
2 4
5
5
3
1
2
4
4 2
1 1
4 4
2
2
3
5 2
1 5
1 5
4
2
1
3
4
5 2
1 5
1 3
5
4
1
2
3
5
5 5
1 5
1 5
1 5
1 5
1 4
3
1
4
3
3 2
2 2
1 3
3
2
3
1
Output
3
-1
3
3
3
1
----------------------------------------------------------------------------------------------------
F1. Omsk Metro (simple version)
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
1
8
+ 1 -1
? 1 1 2
? 1 2 1
+ 1 1
? 1 3 -1
? 1 1 1
? 1 3 2
? 1 1 0
Output
NO
YES
NO
YES
YES
YES
Input
1
10
+ 1 -1
+ 1 -1
+ 3 1
+ 3 -1
+ 3 1
? 1 6 -1
? 1 6 2
? 1 2 0
? 1 5 -2
? 1 4 3
Output
YES
NO
YES
YES
NO
----------------------------------------------------------------------------------------------------
F2. Omsk Metro (hard version)
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
1
8
+ 1 -1
? 1 1 2
? 1 2 1
+ 1 1
? 1 3 -1
? 1 1 1
? 1 3 2
? 1 1 0
Output
NO
YES
NO
YES
YES
YES
Input
1
7
+ 1 -1
+ 2 -1
+ 2 1
+ 3 -1
? 5 2 2
? 3 1 -1
? 5 4 -3
Output
NO
YES
YES
----------------------------------------------------------------------------------------------------
