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;
int n;
int h[100005], w[100005];
int pre[100005];
int l[100005], r[100005];
stack<int>st;
int func(int h_, int w_){
return (h_*(h_+1)*w_*(w_+1))/4;
}
int ans=0;
int main(){
cin>>n;
for (int i=1;i <=n; i++){
cin>>h[i];
}
for (int i=1;i <=n; i++){
cin>>w[i];
pre[i]=pre[i-1]+w[i];
}
for (int i=1;i <=n; i++){
while (!st.empty() && h[st.top()]>h[i]){
st.pop();
}
if (st.empty()){l[i]=0;}else{l[i]=st.top();};
st.push(i);
}
/* for (int i=1;i <=n;i ++){
cout<<l[i]<<" ";
} */
while (st.empty()==false){
st.pop();
}
// cout<<st.size();
for (int i=n;i >=1; i--){
while (!st.empty() && h[st.top()]>=h[i]){
st.pop();
}
if (st.empty()){r[i]=n+1;}else{r[i]=st.top();};
st.push(i);
}
/* for (int i=1;i <=n; i++){
cout<<i<<" "<<l[i]<<" "<<r[i]<<'\n';
} */
for (int i=1;i <=n;i ++){
int nearest=max(h[l[i]], h[r[i]]);
int ww=pre[r[i]-1]-pre[l[i]];
ans+=(func(h[i], ww)-func(nearest, ww));
}
cout<<ans;
}
/*
5
1 5 3 3 2
2 2 3 1 2 */
# | 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... |