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
const int MOD = 1e9+7;
int n;
int h[100005];
int w[100005];
int nrp(int x)
{
return (x*(x+1)/2LL)%MOD;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>h[i];
}
deque<pair<int,int>> dq;///{h, cnt}
int sumdq=0,rez=0;
for(int i=1;i<=n;i++)
{
cin>>w[i];
int cnt = w[i];
while(!dq.empty() && h[i] <= dq.back().first)
{
cnt += dq.back().second;
cnt %= MOD;
sumdq = (sumdq + MOD - nrp(dq.back().first) * dq.back().second)%MOD;
dq.pop_back();
}
dq.push_back({h[i],cnt});
rez += (sumdq*w[i])%MOD + nrp(h[i]) * (((cnt - w[i] + MOD)*w[i] + nrp(w[i]))%MOD);
rez %= MOD;
sumdq += (nrp(h[i]) * cnt)%MOD;
sumdq %= MOD;
}
cout<<rez;
return 0;
}
# | 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... |