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 all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
const ll mod = 1e9 + 7;
ll n, h[NMAX], w[NMAX], ans, x, ix, mxh, wd;
stack<int> st;
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> h[i];
for(int i = 1; i <= n; i++) cin >> w[i], w[i] = (w[i] + w[i - 1]) % mod;
st.emplace(0);
for(int i = 1; i <= n; i++){
while(st.size() >= 2 && h[st.top()] > h[i]){
ix = st.top(); st.pop();
mxh = max(h[st.top()], h[i]);
x = h[ix] - mxh;
wd = w[ix] - w[st.top()];
ans += (x * (x + 1) / 2 + x * mxh) % mod * wd * (wd + 1) / 2; ans %= mod;
if(h[st.top()] > h[i]) w[st.top()] = w[ix];
}
if(h[st.top()] == h[i]) st.pop();
st.emplace(i);
}
while(st.size() >= 2){
ix = st.top(); st.pop();
x = h[ix] - h[st.top()];
wd = w[n] - w[st.top()];
ans += (x * (x + 1) / 2 + x * h[st.top()]) % mod * wd * (wd + 1) / 2; ans %= mod;
}
cout << ans;
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... |