This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pi pair <int, int>
#define pii pair <int, pi>
int n, H[100005], W[100005], P[100005];
stack <pi> s;
int lst[105];
const int mod = 1e9 + 7;
struct node{
int s, e, m, val, lz, val2;
node *l, *r;
node(int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1;
val = lz = val2 = 0;
l = r = nullptr;
}
void mc(){
if(s == e || l != nullptr)return;
l = new node(s, m);
r = new node(m+1, e);
}
void prop(){
if(lz){
int brr = e * (e + 1) / 2;
brr %= mod;
int brr2 = s * (s - 1) / 2;
brr2 %= mod;
brr = (brr - brr2 + mod) % mod;
val = lz * (brr) % mod;
if(s != e){
mc();
l->lz = lz; r->lz = lz;
}
lz = 0;
}
}
void upd(int a, int b, int c){
prop();
if(a == s && b == e)lz = c;
else{
mc();
if(b <= m)l->upd(a, b, c);
else if(a > m)r->upd(a, b, c);
else l->upd(a, m, c), r->upd(m+1, b, c);
l->prop(), r->prop();
val = l->val + r->val;
val %= mod;
}
}
int qry(int a, int b){
prop();
if(a == s && b == e)return val;
if(l == nullptr)return 0;
if(b <= m)return l->qry(a, b);
if(a > m)return r->qry(a, b);
return (l->qry(a, m) + r->qry(m+1, b)) % mod;
}
}*root;
void solve(){
cin >> n;
for(int i = 1; i <= n; i++)cin >> H[i];
for(int i = 1; i <= n; i++)cin >> W[i];
s.push({0, 0});
int ans = 0;
root = new node(0, 1e9);
for(int i = 1; i <= n; i++){
P[i] = P[i - 1] + W[i];
P[i] %= mod;
root->upd(H[i] + 1, 1e9, P[i]);
//for(int j = H[i] + 1; j <= 100; j++)lst[j] = P[i];
/*
for(int j = 1; j <= H[i]; j++){
ans += j * W[i] % mod * (P[i - 1] - lst[j] + mod) % mod;
ans %= mod;
}
*/
root->prop();
int tot = root->qry(1, H[i]);
int tot2 = H[i] * (H[i] + 1) / 2;
tot2 %= mod;
tot2 *= P[i - 1];
tot2 %= mod;
tot2 -= tot;
tot2 = (tot2 + mod) % mod;
ans += tot2 * W[i] % mod;
ans %= mod;
int a = W[i] * (W[i] + 1) / 2;
a %= mod;
int b = H[i] * (H[i] + 1) / 2;
b %= mod;
ans += (a * b % mod);
ans %= mod;
//cout << ans << '\n';
}
cout << ans;
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int tc = 1;
//cin >> tc;
while(tc--)solve();
}
Compilation message (stderr)
fancyfence.cpp:108:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
108 | main(){
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |