#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define int long long
using namespace std;
const int MAXN=1e5+5;
const int MOD=1e9+7;
int n;
int h[MAXN];
int w[MAXN];
long long pref[MAXN];
int ord[MAXN];
bool used[MAXN];
vector<pair<int,int> > ev;
pair<int,int> rng[MAXN];
int ans=0;
int rect(long long w,long long h)
{
w%=MOD;
h%=MOD;
return ((w*(w+1)/2)%MOD*(h*(h+1)/2)%MOD)%MOD;
}
void sum(int &a,int val)
{
a+=val;
if(a>=MOD) a-=MOD;
}
void subtr(int &a,int val)
{
a-=val;
if(a<0) a+=MOD;
}
void addL(int ind)
{
ev.push_back({rng[ind-1].fi, ind});
long long d=pref[ind-1]-pref[rng[ind-1].fi-1];
subtr(ans, rect(d,h[ind]));
}
void changeRngL(int ind)
{
int l=rng[ind-1].fi;
int r=rng[ind].se;
rng[l]={rng[l].fi, rng[r].se};
rng[r]={rng[l].fi, rng[r].se};
}
void addR(int ind)
{
ev.push_back({ind, rng[ind+1].se});
long long d=pref[rng[ind+1].se]-pref[ind];
subtr(ans, rect(d,h[ind]));
}
void changeRngR(int ind)
{
int l=rng[ind].fi;
int r=rng[ind+1].se;
rng[l]={rng[l].fi, rng[r].se};
rng[r]={rng[l].fi, rng[r].se};
}
void calc(int h)
{
for(auto cur: ev)
{//cout<<"("<<cur.fi<<","<<cur.se<<") ";
long long d=pref[cur.se]-pref[cur.fi-1];
sum(ans, rect(d,h));
cout<<1/0<<endl;
}
ev.clear();
//cout<<ans<<endl;
}
bool cmp(int x,int y)
{
if(h[x]==h[y]) return x<y;
return h[x]>h[y];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n;
for(int i=1;i<=n;i++) cin>>h[i];
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<=n;i++) pref[i]=pref[i-1]+w[i];
for(int i=1;i<=n;i++) rng[i]={i,i};
iota(ord,ord+n,1);
sort(ord,ord+n,cmp);
for(int i=0;i<n;i++)
{
if(i>0 && h[ord[i]]<h[ord[i-1]]) calc(h[ord[i-1]]);
int ind=ord[i];
pair<int,int> last({-1,-1});
if(!ev.empty()) last=ev.back();
if(used[ind-1])
{//cout<<i<<" "<<ind<<" "<<last.fi<<" "<<last.se<<endl;
if(ind-1==last.se) last.se++, ev.back().se++;
else addL(ind);
changeRngL(ind);
//cout<<ans<<" "<<rng[ind].fi<<" "<<rng[ind].se<<endl;
}
if(ev.size()>0) last=ev.back();
if(used[ind+1])
{//cout<<i<<" "<<ind<<" "<<last.fi<<" "<<last.se<<endl;
if(last.se==ind)
{
last.se=rng[ind+1].se; ev.back().se=rng[ind+1].se;
long long d=pref[rng[ind+1].se]-pref[ind];
subtr(ans, rect(d,h[ind]));
}
else addR(ind);
changeRngR(ind);
//cout<<ans<<" "<<rng[ind].fi<<" "<<rng[ind].se<<endl;
}
if(!used[ind-1] && !used[ind+1]) sum(ans, rect(w[ind], h[ind]));
used[ind]=1;
//cout<<i<<" "<<ord[i]<<": "<<ans<<endl;
}
calc(h[ord[n-1]]);
cout<<ans<<endl;
return 0;
}
/*
6
1 3 5 3 2 6
1 1 1 1 1 1
5
1 3 5 3 2
3 2 1 3 3
7
3 4 1 9 8 3 9
1 1 1 1 1 1 1
10
4 4 4 4 4 4 4 4 4 4
1 3 7 8 4 5 9 2 7 5
17
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
2 3 9 5 7 3 8 1 9 9 6 1 2 4 8 5 4
*/
Compilation message
fancyfence.cpp: In function 'void calc(long long int)':
fancyfence.cpp:77:16: warning: division by zero [-Wdiv-by-zero]
77 | cout<<1/0<<endl;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
652 KB |
Execution killed with signal 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
