Codeforces Round 942 (Div. 2)


A. Contest Proposal
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2
6
1000 1400 2000 2000 2200 2700
800 1200 1500 1800 2200 3000
6
4 5 6 7 8 9
1 2 3 4 5 6
Output
2
3
----------------------------------------------------------------------------------------------------
B. Coin Games
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
5
UUDUD
5
UDDUD
2
UU
Output
YES
NO
NO
----------------------------------------------------------------------------------------------------
C. Permutation Counting
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
8
1 10
1
2 4
8 4
3 4
6 1 8
3 9
7 6 2
5 3
6 6 7 4 6
9 7
7 6 1 7 6 2 4 3 3
10 10
1 3 1 2 1 9 3 5 7 5
9 8
5 8 7 5 1 3 2 9 8
Output
11
15
15
22
28
32
28
36
----------------------------------------------------------------------------------------------------
D1. Reverse Card (Easy Version)
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
1 1
2 3
3 5
10 8
100 1233
1000000 1145141
Output
1
3
4
14
153
1643498
----------------------------------------------------------------------------------------------------
D2. Reverse Card (Hard Version)
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
1 1
2 3
3 5
10 8
100 1233
1000000 1145141
Output
0
1
1
6
423
5933961
----------------------------------------------------------------------------------------------------
E. Fenwick Tree
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2
8 1
1 2 1 4 1 2 1 8
6 2
1 4 3 17 5 16
Output
1 1 1 1 1 1 1 1
1 2 3 4 5 6
----------------------------------------------------------------------------------------------------
F. Long Way to be Non-decreasing
time limit per test: 4 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
5 8
1 6 3 7 1
2 3 5 8 7 1 5 6
3 3
1 3 2
2 1 3
10 10
2 8 5 4 8 4 1 5 10 10
6 7 2 6 3 4 1 1 3 5
Output
3
-1
3
----------------------------------------------------------------------------------------------------
