#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 1e5+10;
const int mod = 1e9+7;
int n, h[maxn], w[maxn], ps[maxn];
map<int,vector<int>> ed;
int vz(int a, int b) {
return a*b%mod;
}
void solve() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> h[i];
ed[h[i]].pb(i);
}
for(int i = 1; i <= n; i++) {
cin >> w[i];
ps[i] = ps[i-1]+w[i]; ps[i]%= mod;
}
set<pair<int,int>> st;
st.insert(mp(1,n));
int curw = ps[n]*(ps[n]+1)/2; curw%= mod;
int ant = 0;
int ans = 0;
for(auto X : ed) {
int val = X.fr;
// l = ant+1 r = val
int aux = (val-ant)*(val+ant+1)/2;
aux%= mod;
curw%= mod;
ans+= (curw*aux)%mod; ans%= mod;
ant = val;
for(auto i : X.sc) {
auto it = st.upper_bound(mp(i,inf)); it--;
int l = it->fr;
int r = it->sc;
curw-= (ps[r]-ps[l-1])*(ps[r]-ps[l-1]+1)/2; curw%= mod;
st.erase(it);
if(i != l) {
st.insert(mp(l,i-1));
curw+= (ps[i-1]-ps[l-1])*(ps[i-1]-ps[l-1]+1)/2; curw%= mod;
}
if(i != r) {
st.insert(mp(i+1,r));
curw+= (ps[r]-ps[i])*(ps[r]-ps[i]+1)/2; curw%= mod;
}
}
}
ans = (ans+mod)%mod;
cout << ans << endl;
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) {
solve();
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
16 ms |
3652 KB |
Output is correct |
4 |
Correct |
38 ms |
6216 KB |
Output is correct |
5 |
Correct |
34 ms |
6564 KB |
Output is correct |
6 |
Correct |
29 ms |
5904 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
984 KB |
Output is correct |
3 |
Correct |
13 ms |
3412 KB |
Output is correct |
4 |
Correct |
25 ms |
6204 KB |
Output is correct |
5 |
Correct |
32 ms |
6440 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
3 ms |
904 KB |
Output is correct |
4 |
Correct |
12 ms |
3412 KB |
Output is correct |
5 |
Correct |
25 ms |
6216 KB |
Output is correct |
6 |
Correct |
32 ms |
6420 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
5 ms |
1836 KB |
Output is correct |
9 |
Correct |
22 ms |
5200 KB |
Output is correct |
10 |
Correct |
53 ms |
15432 KB |
Output is correct |
11 |
Correct |
53 ms |
15524 KB |
Output is correct |
12 |
Correct |
1 ms |
328 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
328 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
380 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
1 ms |
416 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
328 KB |
Output is correct |
4 |
Correct |
1 ms |
464 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
336 KB |
Output is correct |
11 |
Correct |
18 ms |
3604 KB |
Output is correct |
12 |
Correct |
39 ms |
6196 KB |
Output is correct |
13 |
Correct |
33 ms |
6560 KB |
Output is correct |
14 |
Correct |
26 ms |
5864 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
3 ms |
900 KB |
Output is correct |
17 |
Correct |
13 ms |
3412 KB |
Output is correct |
18 |
Correct |
26 ms |
6312 KB |
Output is correct |
19 |
Correct |
28 ms |
6320 KB |
Output is correct |
20 |
Correct |
1 ms |
464 KB |
Output is correct |
21 |
Correct |
5 ms |
1748 KB |
Output is correct |
22 |
Correct |
21 ms |
5288 KB |
Output is correct |
23 |
Correct |
60 ms |
15404 KB |
Output is correct |
24 |
Correct |
54 ms |
15440 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
468 KB |
Output is correct |
28 |
Correct |
1 ms |
468 KB |
Output is correct |
29 |
Correct |
1 ms |
464 KB |
Output is correct |
30 |
Correct |
9 ms |
1876 KB |
Output is correct |
31 |
Correct |
8 ms |
2004 KB |
Output is correct |
32 |
Correct |
28 ms |
3668 KB |
Output is correct |
33 |
Correct |
57 ms |
8624 KB |
Output is correct |
34 |
Correct |
129 ms |
16316 KB |
Output is correct |
35 |
Correct |
57 ms |
6892 KB |
Output is correct |
36 |
Correct |
138 ms |
17044 KB |
Output is correct |
37 |
Correct |
111 ms |
12900 KB |
Output is correct |
38 |
Correct |
1 ms |
212 KB |
Output is correct |
39 |
Correct |
91 ms |
10396 KB |
Output is correct |
40 |
Correct |
88 ms |
15308 KB |
Output is correct |
41 |
Correct |
57 ms |
15460 KB |
Output is correct |
42 |
Correct |
56 ms |
15540 KB |
Output is correct |