#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
const int MOD = (int)1e9 + 7, INV_2 = (MOD + 1) / 2;
int N, glob, a[500005], b[500005];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> a[i];
}
for (int i = 1; i <= N; i++) {
cin >> b[i];
if (a[i] > b[i]) {
swap(a[i], b[i]);
}
}
for (int i = 1; i <= N; i++) {
for (int h : {a[i], b[i]}) {
int expected = 0;
for (int v = h + 1; v <= 1001; v++) {
int lft_prob = 1, rig_prob = 1;
for (int j = 1; j < i; j++) {
int cur_prob = INV_2;
if (a[j] >= v) {
cur_prob = 0;
} else if (b[j] < v) {
cur_prob = 1;
}
lft_prob = ((ll)lft_prob * cur_prob) % MOD;
}
lft_prob = (1 - lft_prob + MOD) % MOD;
for (int j = i + 1; j <= N; j++) {
int cur_prob = INV_2;
if (a[j] >= v) {
cur_prob = 0;
} else if (b[j] < v) {
cur_prob = 1;
}
rig_prob = ((ll)rig_prob * cur_prob) % MOD;
}
rig_prob = (1 - rig_prob + MOD) % MOD;
int p = (ll)lft_prob * rig_prob % MOD;
expected = (expected + p) % MOD;
}
glob = (glob + expected) % MOD;
}
}
for (int rep = 0; rep < N - 1; rep++) {
glob = (glob * 2) % MOD;
}
cout << glob << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
2 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
22 ms |
472 KB |
Output is correct |
16 |
Correct |
20 ms |
348 KB |
Output is correct |
17 |
Correct |
51 ms |
344 KB |
Output is correct |
18 |
Correct |
48 ms |
348 KB |
Output is correct |
19 |
Correct |
52 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
53 ms |
348 KB |
Output is correct |
22 |
Correct |
50 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
43 ms |
448 KB |
Output is correct |
25 |
Correct |
42 ms |
348 KB |
Output is correct |
26 |
Correct |
40 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
2 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
22 ms |
472 KB |
Output is correct |
16 |
Correct |
20 ms |
348 KB |
Output is correct |
17 |
Correct |
51 ms |
344 KB |
Output is correct |
18 |
Correct |
48 ms |
348 KB |
Output is correct |
19 |
Correct |
52 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
53 ms |
348 KB |
Output is correct |
22 |
Correct |
50 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
43 ms |
448 KB |
Output is correct |
25 |
Correct |
42 ms |
348 KB |
Output is correct |
26 |
Correct |
40 ms |
348 KB |
Output is correct |
27 |
Execution timed out |
5074 ms |
348 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
2 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
57 ms |
348 KB |
Output is correct |
9 |
Correct |
51 ms |
600 KB |
Output is correct |
10 |
Execution timed out |
5039 ms |
344 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |