#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], prf_ft[1500005], suf_ft[1500005];
vector<int> disc_vec;
multiset<int> prf_a, suf_a;
int exp_mod(int a, int b) {
int r = 1;
while (b) {
if (b % 2 == 1) {
r = (ll)r * a % MOD;
}
a = (ll)a * a % MOD;
b /= 2;
}
return r;
}
int get_disc(int x) {
return lower_bound(disc_vec.begin(), disc_vec.end(), x) - disc_vec.begin() + 1;
}
int ls(int x) {
return x & -x;
}
int ft_qry(int ft[], int p) {
int r = 0;
for (; p; p -= ls(p)) {
r += ft[p];
}
return r;
}
void ft_upd(int ft[], int p, int v) {
for (; p <= (int)disc_vec.size(); p += ls(p)) {
ft[p] += v;
}
}
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 delta = -1; delta <= 1; delta++) {
disc_vec.pb(a[i] + delta);
disc_vec.pb(b[i] + delta);
}
suf_a.insert(a[i]);
}
sort(disc_vec.begin(), disc_vec.end());
disc_vec.erase(unique(disc_vec.begin(), disc_vec.end()), disc_vec.end());
for (int i = 1; i <= N; i++) {
ft_upd(suf_ft, get_disc(b[i]), 1);
}
for (int i = 1; i <= N; i++) {
ft_upd(suf_ft, get_disc(b[i]), -1);
suf_a.erase(suf_a.find(a[i]));
int max_prf_a = (prf_a.empty() ? 0 : *prf_a.rbegin());
int max_suf_a = (suf_a.empty() ? 0 : *suf_a.rbegin());
for (int h : {a[i], b[i]}) {
int expected = 0;
vector<int> probs = {1}, vals = {h};
for (auto it = upper_bound(disc_vec.begin(), disc_vec.end(), h); it != disc_vec.end(); ++it) {
int v = *it;
int lft_prob = 1, rig_prob = 1;
if (max_prf_a >= v) {
lft_prob = 0;
} else {
int cnt_small = ft_qry(prf_ft, it - disc_vec.begin());
int oth = i - 1 - cnt_small;
lft_prob = exp_mod(INV_2, oth);
}
lft_prob = (1 - lft_prob + MOD) % MOD;
if (max_suf_a >= v) {
rig_prob = 0;
} else {
int cnt_small = ft_qry(suf_ft, it - disc_vec.begin());
int oth = (N - i) - cnt_small;
rig_prob = exp_mod(INV_2, oth);
}
rig_prob = (1 - rig_prob + MOD) % MOD;
int p = (ll)lft_prob * rig_prob % MOD;
probs.pb(p);
vals.pb(v);
}
for (int idx = 0; idx + 1 < (int)probs.size(); idx++) {
int tmp = (probs[idx] - probs[idx + 1] + MOD) % MOD;
expected = (expected + (ll)vals[idx] * tmp % MOD) % MOD;
}
expected = (expected - h + MOD) % MOD;
glob = (glob + expected) % MOD;
}
ft_upd(prf_ft, get_disc(b[i]), 1);
prf_a.insert(a[i]);
}
for (int rep = 0; rep < N - 1; rep++) {
glob = (glob * 2) % MOD;
}
cout << glob << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
0 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4440 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
0 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
1 ms |
4560 KB |
Output is correct |
18 |
Correct |
0 ms |
4444 KB |
Output is correct |
19 |
Correct |
1 ms |
4444 KB |
Output is correct |
20 |
Correct |
0 ms |
4444 KB |
Output is correct |
21 |
Correct |
1 ms |
4444 KB |
Output is correct |
22 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4564 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4568 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
0 ms |
4444 KB |
Output is correct |
9 |
Correct |
0 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4568 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
1 ms |
4568 KB |
Output is correct |
16 |
Correct |
2 ms |
4440 KB |
Output is correct |
17 |
Correct |
1 ms |
4440 KB |
Output is correct |
18 |
Correct |
0 ms |
4444 KB |
Output is correct |
19 |
Correct |
1 ms |
4444 KB |
Output is correct |
20 |
Correct |
1 ms |
4444 KB |
Output is correct |
21 |
Correct |
1 ms |
4444 KB |
Output is correct |
22 |
Correct |
1 ms |
4444 KB |
Output is correct |
23 |
Correct |
1 ms |
4444 KB |
Output is correct |
24 |
Correct |
1 ms |
4444 KB |
Output is correct |
25 |
Correct |
2 ms |
4444 KB |
Output is correct |
26 |
Correct |
2 ms |
4444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4564 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4568 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
0 ms |
4444 KB |
Output is correct |
9 |
Correct |
0 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4568 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
1 ms |
4568 KB |
Output is correct |
16 |
Correct |
2 ms |
4440 KB |
Output is correct |
17 |
Correct |
1 ms |
4440 KB |
Output is correct |
18 |
Correct |
0 ms |
4444 KB |
Output is correct |
19 |
Correct |
1 ms |
4444 KB |
Output is correct |
20 |
Correct |
1 ms |
4444 KB |
Output is correct |
21 |
Correct |
1 ms |
4444 KB |
Output is correct |
22 |
Correct |
1 ms |
4444 KB |
Output is correct |
23 |
Correct |
1 ms |
4444 KB |
Output is correct |
24 |
Correct |
1 ms |
4444 KB |
Output is correct |
25 |
Correct |
2 ms |
4444 KB |
Output is correct |
26 |
Correct |
2 ms |
4444 KB |
Output is correct |
27 |
Correct |
95 ms |
5336 KB |
Output is correct |
28 |
Correct |
94 ms |
5336 KB |
Output is correct |
29 |
Correct |
8 ms |
5336 KB |
Output is correct |
30 |
Correct |
7 ms |
5336 KB |
Output is correct |
31 |
Correct |
11 ms |
5336 KB |
Output is correct |
32 |
Correct |
9 ms |
5376 KB |
Output is correct |
33 |
Correct |
11 ms |
5336 KB |
Output is correct |
34 |
Correct |
11 ms |
3288 KB |
Output is correct |
35 |
Correct |
10 ms |
5336 KB |
Output is correct |
36 |
Correct |
11 ms |
5336 KB |
Output is correct |
37 |
Correct |
7 ms |
5336 KB |
Output is correct |
38 |
Correct |
7 ms |
5336 KB |
Output is correct |
39 |
Correct |
10 ms |
5336 KB |
Output is correct |
40 |
Correct |
11 ms |
5336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
0 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4440 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
0 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
1 ms |
4560 KB |
Output is correct |
18 |
Correct |
0 ms |
4444 KB |
Output is correct |
19 |
Correct |
1 ms |
4444 KB |
Output is correct |
20 |
Correct |
0 ms |
4444 KB |
Output is correct |
21 |
Correct |
1 ms |
4444 KB |
Output is correct |
22 |
Correct |
1 ms |
4444 KB |
Output is correct |
23 |
Correct |
1 ms |
4444 KB |
Output is correct |
24 |
Correct |
1 ms |
4564 KB |
Output is correct |
25 |
Correct |
1 ms |
4444 KB |
Output is correct |
26 |
Correct |
1 ms |
4444 KB |
Output is correct |
27 |
Correct |
1 ms |
4444 KB |
Output is correct |
28 |
Correct |
1 ms |
4568 KB |
Output is correct |
29 |
Correct |
1 ms |
4444 KB |
Output is correct |
30 |
Correct |
0 ms |
4444 KB |
Output is correct |
31 |
Correct |
0 ms |
4444 KB |
Output is correct |
32 |
Correct |
1 ms |
4444 KB |
Output is correct |
33 |
Correct |
1 ms |
4444 KB |
Output is correct |
34 |
Correct |
1 ms |
4444 KB |
Output is correct |
35 |
Correct |
1 ms |
4568 KB |
Output is correct |
36 |
Correct |
1 ms |
4444 KB |
Output is correct |
37 |
Correct |
1 ms |
4568 KB |
Output is correct |
38 |
Correct |
2 ms |
4440 KB |
Output is correct |
39 |
Correct |
1 ms |
4440 KB |
Output is correct |
40 |
Correct |
0 ms |
4444 KB |
Output is correct |
41 |
Correct |
1 ms |
4444 KB |
Output is correct |
42 |
Correct |
1 ms |
4444 KB |
Output is correct |
43 |
Correct |
1 ms |
4444 KB |
Output is correct |
44 |
Correct |
1 ms |
4444 KB |
Output is correct |
45 |
Correct |
1 ms |
4444 KB |
Output is correct |
46 |
Correct |
1 ms |
4444 KB |
Output is correct |
47 |
Correct |
2 ms |
4444 KB |
Output is correct |
48 |
Correct |
2 ms |
4444 KB |
Output is correct |
49 |
Correct |
95 ms |
5336 KB |
Output is correct |
50 |
Correct |
94 ms |
5336 KB |
Output is correct |
51 |
Correct |
8 ms |
5336 KB |
Output is correct |
52 |
Correct |
7 ms |
5336 KB |
Output is correct |
53 |
Correct |
11 ms |
5336 KB |
Output is correct |
54 |
Correct |
9 ms |
5376 KB |
Output is correct |
55 |
Correct |
11 ms |
5336 KB |
Output is correct |
56 |
Correct |
11 ms |
3288 KB |
Output is correct |
57 |
Correct |
10 ms |
5336 KB |
Output is correct |
58 |
Correct |
11 ms |
5336 KB |
Output is correct |
59 |
Correct |
7 ms |
5336 KB |
Output is correct |
60 |
Correct |
7 ms |
5336 KB |
Output is correct |
61 |
Correct |
10 ms |
5336 KB |
Output is correct |
62 |
Correct |
11 ms |
5336 KB |
Output is correct |
63 |
Execution timed out |
5080 ms |
9016 KB |
Time limit exceeded |
64 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4560 KB |
Output is correct |
10 |
Correct |
8 ms |
5336 KB |
Output is correct |
11 |
Correct |
8 ms |
5336 KB |
Output is correct |
12 |
Correct |
8 ms |
5336 KB |
Output is correct |
13 |
Correct |
8 ms |
5244 KB |
Output is correct |
14 |
Correct |
470 ms |
42080 KB |
Output is correct |
15 |
Correct |
453 ms |
42656 KB |
Output is correct |
16 |
Correct |
462 ms |
42704 KB |
Output is correct |
17 |
Correct |
470 ms |
42660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
0 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4440 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
0 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
1 ms |
4560 KB |
Output is correct |
18 |
Correct |
0 ms |
4444 KB |
Output is correct |
19 |
Correct |
1 ms |
4444 KB |
Output is correct |
20 |
Correct |
0 ms |
4444 KB |
Output is correct |
21 |
Correct |
1 ms |
4444 KB |
Output is correct |
22 |
Correct |
1 ms |
4444 KB |
Output is correct |
23 |
Correct |
1 ms |
4444 KB |
Output is correct |
24 |
Correct |
1 ms |
4564 KB |
Output is correct |
25 |
Correct |
1 ms |
4444 KB |
Output is correct |
26 |
Correct |
1 ms |
4444 KB |
Output is correct |
27 |
Correct |
1 ms |
4444 KB |
Output is correct |
28 |
Correct |
1 ms |
4568 KB |
Output is correct |
29 |
Correct |
1 ms |
4444 KB |
Output is correct |
30 |
Correct |
0 ms |
4444 KB |
Output is correct |
31 |
Correct |
0 ms |
4444 KB |
Output is correct |
32 |
Correct |
1 ms |
4444 KB |
Output is correct |
33 |
Correct |
1 ms |
4444 KB |
Output is correct |
34 |
Correct |
1 ms |
4444 KB |
Output is correct |
35 |
Correct |
1 ms |
4568 KB |
Output is correct |
36 |
Correct |
1 ms |
4444 KB |
Output is correct |
37 |
Correct |
1 ms |
4568 KB |
Output is correct |
38 |
Correct |
2 ms |
4440 KB |
Output is correct |
39 |
Correct |
1 ms |
4440 KB |
Output is correct |
40 |
Correct |
0 ms |
4444 KB |
Output is correct |
41 |
Correct |
1 ms |
4444 KB |
Output is correct |
42 |
Correct |
1 ms |
4444 KB |
Output is correct |
43 |
Correct |
1 ms |
4444 KB |
Output is correct |
44 |
Correct |
1 ms |
4444 KB |
Output is correct |
45 |
Correct |
1 ms |
4444 KB |
Output is correct |
46 |
Correct |
1 ms |
4444 KB |
Output is correct |
47 |
Correct |
2 ms |
4444 KB |
Output is correct |
48 |
Correct |
2 ms |
4444 KB |
Output is correct |
49 |
Correct |
95 ms |
5336 KB |
Output is correct |
50 |
Correct |
94 ms |
5336 KB |
Output is correct |
51 |
Correct |
8 ms |
5336 KB |
Output is correct |
52 |
Correct |
7 ms |
5336 KB |
Output is correct |
53 |
Correct |
11 ms |
5336 KB |
Output is correct |
54 |
Correct |
9 ms |
5376 KB |
Output is correct |
55 |
Correct |
11 ms |
5336 KB |
Output is correct |
56 |
Correct |
11 ms |
3288 KB |
Output is correct |
57 |
Correct |
10 ms |
5336 KB |
Output is correct |
58 |
Correct |
11 ms |
5336 KB |
Output is correct |
59 |
Correct |
7 ms |
5336 KB |
Output is correct |
60 |
Correct |
7 ms |
5336 KB |
Output is correct |
61 |
Correct |
10 ms |
5336 KB |
Output is correct |
62 |
Correct |
11 ms |
5336 KB |
Output is correct |
63 |
Execution timed out |
5080 ms |
9016 KB |
Time limit exceeded |
64 |
Halted |
0 ms |
0 KB |
- |