#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
#ifdef local
void CHECK();
void setio(){
freopen("/Users/iantsai/cpp/input.txt","r",stdin);
freopen("/Users/iantsai/cpp/output.txt","w",stdout);
}
#else
void setio(){}
#endif
#define TOI_is_so_de ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);setio();
const int mxn = 5e5 + 5, mod = 1e9 + 7;
int n, a[mxn], b[mxn], pw[mxn];
#define s seg[id]
#define L seg[seg[id].lc]
#define R seg[seg[id].rc]
struct node{
long long val, tag;
int lc, rc;
};
struct segment_tree{
int tmr = 0;
vector<node>seg = {{0, 0, 0, 0}};
void new_node(int l, int r){
int id = ++tmr;
seg.pb({0, 0, 0, 0});
s.val = r - l + 1;
s.tag = 1;
s.lc = s.rc = -1;
}
void push(int id, int l, int r){
int mm = (long long) l + r >> 1;
if(s.lc == -1){
new_node(l, mm);
s.lc = tmr;
}
if(s.rc == -1){
new_node(mm + 1, r);
s.rc = tmr;
}
(L.tag *= s.tag) %= mod;
(R.tag *= s.tag) %= mod;
(L.val *= s.tag) %= mod;
(R.val *= s.tag) %= mod;
s.tag = 1;
}
void merge(int id){
s.val = ((long long)L.val + R.val) % mod;
}
void modify(int l, int r, int id, int ql, int qr, int v){
if(qr < l or r < ql) return;
if(ql <= l and r <= qr){
s.val = (long long)s.val * v % mod;
s.tag = (long long)s.tag * v % mod;
return;
}
push(id, l, r);
int mm = (long long) l + r >> 1;
modify(l, mm, s.lc, ql, qr, v);
modify(mm + 1, r, s.rc, ql, qr, v);
merge(id);
}
};
void solve(){
cin >> n;
pw[0] = 1;
for(int i = 1; i <= n; i++){
pw[i] = pw[i - 1] * 2 % mod;
}
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]);
}
long long ans = 0;
segment_tree t1;
t1.new_node(1, mod);
for(int i = 1; i <= n; i++){
t1.modify(1, mod, 1, 1, a[i], 0);
t1.modify(1, mod, 1, b[i] + 1, mod, 2);
ans = (ans - (long long)t1.seg[1].val * pw[n - i] % mod) % mod;
}
t1.seg.clear();
t1.tmr = 0;
t1.seg.pb({0, 0, 0, 0});
t1.new_node(1, mod);
for(int i = n; i >= 1; i--){
t1.modify(1, mod, 1, 1, a[i], 0);
t1.modify(1, mod, 1, b[i] + 1, mod, 2);
ans = (ans - (long long)t1.seg[1].val * pw[i - 1] % mod) % mod;
}
ans = ((long long)ans + (long long)n * t1.seg[1].val % mod);
for(int i = 1; i <= n; i++){
ans = ((long long)ans + pw[n - 1] * ((long long)b[i] - a[i] + (mod - b[i]) * 2LL % mod)) % mod;
}
if(ans < 0) ans += mod;
cout << ans << '\n';
}
signed main(){
TOI_is_so_de;
int t = 1;
while(t--){
solve();
}
}
/*
input:
*/
Compilation message
Main.cpp: In member function 'void segment_tree::push(int, int, int)':
Main.cpp:47:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | int mm = (long long) l + r >> 1;
| ~~~~~~~~~~~~~~^~~
Main.cpp: In member function 'void segment_tree::modify(int, int, int, int, int, int)':
Main.cpp:73:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
73 | int mm = (long long) l + r >> 1;
| ~~~~~~~~~~~~~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
432 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 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 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 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 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 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
23 ms |
744 KB |
Output is correct |
28 |
Correct |
26 ms |
604 KB |
Output is correct |
29 |
Correct |
23 ms |
348 KB |
Output is correct |
30 |
Correct |
23 ms |
348 KB |
Output is correct |
31 |
Correct |
23 ms |
608 KB |
Output is correct |
32 |
Correct |
24 ms |
604 KB |
Output is correct |
33 |
Correct |
23 ms |
604 KB |
Output is correct |
34 |
Correct |
23 ms |
600 KB |
Output is correct |
35 |
Correct |
23 ms |
604 KB |
Output is correct |
36 |
Correct |
23 ms |
604 KB |
Output is correct |
37 |
Correct |
23 ms |
348 KB |
Output is correct |
38 |
Correct |
23 ms |
348 KB |
Output is correct |
39 |
Correct |
23 ms |
604 KB |
Output is correct |
40 |
Correct |
23 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
432 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 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
344 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
344 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
0 ms |
348 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
0 ms |
348 KB |
Output is correct |
39 |
Correct |
0 ms |
344 KB |
Output is correct |
40 |
Correct |
0 ms |
348 KB |
Output is correct |
41 |
Correct |
1 ms |
348 KB |
Output is correct |
42 |
Correct |
0 ms |
348 KB |
Output is correct |
43 |
Correct |
0 ms |
348 KB |
Output is correct |
44 |
Correct |
1 ms |
348 KB |
Output is correct |
45 |
Correct |
0 ms |
348 KB |
Output is correct |
46 |
Correct |
0 ms |
348 KB |
Output is correct |
47 |
Correct |
1 ms |
348 KB |
Output is correct |
48 |
Correct |
0 ms |
348 KB |
Output is correct |
49 |
Correct |
23 ms |
744 KB |
Output is correct |
50 |
Correct |
26 ms |
604 KB |
Output is correct |
51 |
Correct |
23 ms |
348 KB |
Output is correct |
52 |
Correct |
23 ms |
348 KB |
Output is correct |
53 |
Correct |
23 ms |
608 KB |
Output is correct |
54 |
Correct |
24 ms |
604 KB |
Output is correct |
55 |
Correct |
23 ms |
604 KB |
Output is correct |
56 |
Correct |
23 ms |
600 KB |
Output is correct |
57 |
Correct |
23 ms |
604 KB |
Output is correct |
58 |
Correct |
23 ms |
604 KB |
Output is correct |
59 |
Correct |
23 ms |
348 KB |
Output is correct |
60 |
Correct |
23 ms |
348 KB |
Output is correct |
61 |
Correct |
23 ms |
604 KB |
Output is correct |
62 |
Correct |
23 ms |
604 KB |
Output is correct |
63 |
Correct |
48 ms |
25268 KB |
Output is correct |
64 |
Correct |
49 ms |
25424 KB |
Output is correct |
65 |
Correct |
25 ms |
604 KB |
Output is correct |
66 |
Correct |
24 ms |
604 KB |
Output is correct |
67 |
Correct |
21 ms |
732 KB |
Output is correct |
68 |
Correct |
21 ms |
604 KB |
Output is correct |
69 |
Correct |
25 ms |
7032 KB |
Output is correct |
70 |
Correct |
26 ms |
6860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 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 |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
20 ms |
348 KB |
Output is correct |
11 |
Correct |
20 ms |
344 KB |
Output is correct |
12 |
Correct |
20 ms |
348 KB |
Output is correct |
13 |
Correct |
20 ms |
600 KB |
Output is correct |
14 |
Correct |
984 ms |
6304 KB |
Output is correct |
15 |
Correct |
1058 ms |
6228 KB |
Output is correct |
16 |
Correct |
1043 ms |
6236 KB |
Output is correct |
17 |
Correct |
1084 ms |
6224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
432 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 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
344 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
344 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
0 ms |
348 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
0 ms |
348 KB |
Output is correct |
39 |
Correct |
0 ms |
344 KB |
Output is correct |
40 |
Correct |
0 ms |
348 KB |
Output is correct |
41 |
Correct |
1 ms |
348 KB |
Output is correct |
42 |
Correct |
0 ms |
348 KB |
Output is correct |
43 |
Correct |
0 ms |
348 KB |
Output is correct |
44 |
Correct |
1 ms |
348 KB |
Output is correct |
45 |
Correct |
0 ms |
348 KB |
Output is correct |
46 |
Correct |
0 ms |
348 KB |
Output is correct |
47 |
Correct |
1 ms |
348 KB |
Output is correct |
48 |
Correct |
0 ms |
348 KB |
Output is correct |
49 |
Correct |
23 ms |
744 KB |
Output is correct |
50 |
Correct |
26 ms |
604 KB |
Output is correct |
51 |
Correct |
23 ms |
348 KB |
Output is correct |
52 |
Correct |
23 ms |
348 KB |
Output is correct |
53 |
Correct |
23 ms |
608 KB |
Output is correct |
54 |
Correct |
24 ms |
604 KB |
Output is correct |
55 |
Correct |
23 ms |
604 KB |
Output is correct |
56 |
Correct |
23 ms |
600 KB |
Output is correct |
57 |
Correct |
23 ms |
604 KB |
Output is correct |
58 |
Correct |
23 ms |
604 KB |
Output is correct |
59 |
Correct |
23 ms |
348 KB |
Output is correct |
60 |
Correct |
23 ms |
348 KB |
Output is correct |
61 |
Correct |
23 ms |
604 KB |
Output is correct |
62 |
Correct |
23 ms |
604 KB |
Output is correct |
63 |
Correct |
48 ms |
25268 KB |
Output is correct |
64 |
Correct |
49 ms |
25424 KB |
Output is correct |
65 |
Correct |
25 ms |
604 KB |
Output is correct |
66 |
Correct |
24 ms |
604 KB |
Output is correct |
67 |
Correct |
21 ms |
732 KB |
Output is correct |
68 |
Correct |
21 ms |
604 KB |
Output is correct |
69 |
Correct |
25 ms |
7032 KB |
Output is correct |
70 |
Correct |
26 ms |
6860 KB |
Output is correct |
71 |
Correct |
0 ms |
348 KB |
Output is correct |
72 |
Correct |
0 ms |
348 KB |
Output is correct |
73 |
Correct |
0 ms |
348 KB |
Output is correct |
74 |
Correct |
0 ms |
348 KB |
Output is correct |
75 |
Correct |
0 ms |
348 KB |
Output is correct |
76 |
Correct |
0 ms |
348 KB |
Output is correct |
77 |
Correct |
0 ms |
348 KB |
Output is correct |
78 |
Correct |
1 ms |
348 KB |
Output is correct |
79 |
Correct |
0 ms |
348 KB |
Output is correct |
80 |
Correct |
20 ms |
348 KB |
Output is correct |
81 |
Correct |
20 ms |
344 KB |
Output is correct |
82 |
Correct |
20 ms |
348 KB |
Output is correct |
83 |
Correct |
20 ms |
600 KB |
Output is correct |
84 |
Correct |
984 ms |
6304 KB |
Output is correct |
85 |
Correct |
1058 ms |
6228 KB |
Output is correct |
86 |
Correct |
1043 ms |
6236 KB |
Output is correct |
87 |
Correct |
1084 ms |
6224 KB |
Output is correct |
88 |
Correct |
2491 ms |
804064 KB |
Output is correct |
89 |
Correct |
2510 ms |
804004 KB |
Output is correct |
90 |
Correct |
1036 ms |
8272 KB |
Output is correct |
91 |
Correct |
1165 ms |
16172 KB |
Output is correct |
92 |
Correct |
988 ms |
8272 KB |
Output is correct |
93 |
Correct |
1004 ms |
8272 KB |
Output is correct |
94 |
Correct |
1065 ms |
16344 KB |
Output is correct |
95 |
Correct |
1029 ms |
8368 KB |
Output is correct |
96 |
Correct |
1345 ms |
209380 KB |
Output is correct |
97 |
Correct |
1400 ms |
209152 KB |
Output is correct |