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>
#include <fstream>
#define endl '\n'
#define mod 1000000007
#define INF 1000000000
#define INF2 2000000000000000000
//#define ll long long
///#define cin fin
///#define cout fout
using namespace std;
double const EPS = 1e-14;
///ofstream fout("herding.out");
///ifstream fin("herding.in");
int main()
{
ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
int n; cin >> n; long long h[n], w[n];
for(int i = 0; i < n; i++) cin >> h[i];
for(int i = 0; i < n; i++) cin >> w[i];
stack<pair<long long, long long>> st;
long long ans = 0, nw = 0;
for(int i = 0; i < n; i++) {
nw = 0;
while(!st.empty() && st.top().first > h[i]) {
pair<long long, long long> now = st.top();
nw += now.second;
nw %= mod;
st.pop();
ans += (((now.first*(now.first+1))/2%mod) * ((nw*(nw+1))/2%mod)%mod);
// cout << (((now.first*(now.first+1))/2%mod) * ((nw*(nw+1))/2%mod)%mod) << 'a' << endl;
ans %= mod;
if(!st.empty() && st.top().first > h[i]) {
ans -= ((st.top().first*(st.top().first+1))/2%mod) * ((nw*(nw+1))/2%mod)%mod;
// cout << ((st.top().first*(st.top().first+1))/2%mod) * ((nw*(nw+1))/2%mod) << 'b'<< endl;
ans += mod;
ans %= mod;
}
else {
ans -= ((h[i]*(h[i]+1))/2%mod) * ((nw*(nw+1))/2%mod)%mod;
ans += mod;
ans %= mod;
}
}
st.push({h[i],w[i]+nw});
// cout << h[i] << ' ' << w[i]+nw << 's' << endl;
}
nw = 0;
while(!st.empty()) {
pair<long long, long long> now = st.top();
nw += now.second;
nw %= mod;
st.pop();
ans += (((now.first*(now.first+1))/2%mod) * ((nw*(nw+1))/2%mod)%mod);
// cout << (((now.first*(now.first+1))/2%mod) * ((nw*(nw+1))/2%mod)%mod) << 'c' << endl;
ans %= mod;
if(!st.empty()) {
ans -= ((st.top().first*(st.top().first+1))/2%mod) * ((nw*(nw+1))/2%mod)%mod;
// cout << ((st.top().first*(st.top().first+1))/2%mod) * ((nw*(nw+1))/2%mod)%mod << 'd' << endl;
ans += mod;
ans %= mod;
}
}
cout << ans%mod << endl;
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... |