Pagini recente » Cod sursa (job #3141229) | Cod sursa (job #1147847) | Cod sursa (job #2030946) | Cod sursa (job #1812236) | Cod sursa (job #3305522)
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int nmax=3e5+5;
map <int,vector<int> > mp;
stack <pair<int,int> > st;
int n, rez, v[nmax], e[nmax], rmq[20][nmax], lg[nmax];
void init ()
{
for (int i=1; i<=n; i++)
{
rmq[0][i]=v[i];
rez+=v[i];
mp[v[i]].push_back(i);
}
for (int i=2; i<=n; i++)
lg[i]=lg[i/2]+1;
for (int i=1; i<=lg[n]; i++)
for (int j=1; j<=n-(1<<i)+1; j++)
rmq[i][j]=max(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
}
int query (int x, int y)
{
int k=lg[y-x];
return max(rmq[k][x],rmq[k][y-(1<<k)+1]);
}
int main()
{
cin >> n;
for (int i=1; i<=n; i++)
cin >> v[i];
for (int i=1; i<=n; i++)
cin >> e[i];
init();
for (auto it:mp)
{
int i=0, s=0;
for (auto j:it.second)
{
if (i==0)
{
i=j;
continue;
}
int mx=query(i,j);
int cnt=1;
while (!st.empty() && st.top().first<=mx)
{
cnt+=st.top().second;
s=(s-(st.top().first*1LL*st.top().second)%mod+mod)%mod
st.pop();
}
st.push({mx,cnt});
s=(s+mx*1LL*cnt)%mod;
rez+=s;
i=j;
}
}
cout << rez;
return 0;
}