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 <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pb push_back
#define mp make_pair
typedef pair<ll,ll> pii;
typedef tree<ll ,null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
const ll MAXN = 450;
const ll MOD = 1e9+7;
const ll INF = 1e9+10;
ll calc(ll n, ll m){
m%=MOD; n%=MOD;
ll res = (n%MOD*(n+1)%MOD)%MOD;
if(res%2==1)res+=MOD;
res/=2;
res%=MOD;
ll k = (m%MOD*(m+1)%MOD)%MOD;
if(k%2==1)k+=MOD;
k/=2;
k%=MOD;
res*=k;
res%=MOD;
if(res<0)res+=MOD;
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n,i,k,ans=0;
cin>>n;
ll h[n+2],w[n+2],dp[n+2]; dp[0]=0;
for(i=1;i<=n;i++)cin>>h[i];
for(i=1;i<=n;i++){
cin>>w[i];
dp[i] = dp[i-1]+w[i];
}
stack <ll>st;
ll left[n+1],right[n+1];
bool meh[n+1];
for(i=1;i<=n;i++){
meh[i]=true;
while(!st.empty()&&h[st.top()]>=h[i]){
if(h[st.top()]==h[i])meh[i]=false;
st.pop();
}
if(!st.empty()){
left[i]=st.top();
}else{
left[i]=0;
}
st.push(i);
//cout<<left[i]<<" ";
}//cout<<endl;
while(!st.empty())st.pop();
for(i=n;i>=1;i--){
while(!st.empty()&&h[st.top()]>=h[i]){
st.pop();
}
if(!st.empty()){
right[i]=st.top();
}else{
right[i]=n+1;
}
st.push(i);
}
h[0]=0;
h[n+1]=0;
for(i=1;i<=n;i++){
if(meh[i]==false)continue;
//k é a soma no intervalo
k = dp[right[i]-1] - dp[left[i]];
ans += calc(k,h[i]);
ans -= calc(k , max(h[left[i]], h[right[i]]) );
//cout<<i<<" "<<k<<" "<<h[i]<<" "<<left[i]<<" "<<right[i];
//cout<<" "<<h[left[i]]<<" "<<h[right[i]]<<endl;
ans%=MOD;
}
/*
6
1 2 3 2 2 1
1 1 1 1 1 1
*/
if(ans<0)ans+=MOD;
cout<<ans<<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... |