Cod sursa(job #3305522)

Utilizator brianabucur11Briana Bucur brianabucur11 Data 2 august 2025 13:11:38
Problema Zeap Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#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;
}