Submission #1244949

#TimeUsernameProblemLanguageResultExecution timeMemory
1244949VMaksimoski008Fancy Fence (CEOI20_fancyfence)C++17
100 / 100
70 ms8252 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const ll mod = 1e9+7;
ll const maxn = 1e5+1;
ll pref[maxn];
const ll inv2 = (mod+1)/2;

ll S(ll pret,ll p)
{
    ll ans = 0;
    ans = (p*(p+1)/2)%mod;
    ans -= (pret*(pret+1)/2)%mod;
    ans += mod;ans %= mod;
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;

    priority_queue<array<ll,2>,vector<array<ll,2> >, greater<array<ll,2> > > pq;
    set<int> s;s.insert(0);s.insert(n+1);
    vector<ll> v(n+2);v[0] = 0;v[n+1] = 0;
    for (int i=1;i<=n;i++)
    {
        ll a;
        cin>>a;
        pq.push({a,i});
        v[i] = a;
    }
    for (int i=1;i<=n;i++)
    {
        ll a;
        cin>>a;
        pref[i] = pref[i-1] + a;
    }

    ll odg = 0;
    while (pq.size())
    {
        int p = pq.top()[1];
        ll h = pq.top()[0];pq.pop();
        auto it = s.lower_bound(p);
        int r = *it;it--;int l = *it;
        s.insert(p);

        //cout<<"p = "<<p<<" l = "<<l<<" r = "<<r<<endl;
        ll w = pref[r-1]-pref[l];w%=mod;
        //cout<<"w = "<<w<<endl;


        ll pret = max(v[l],v[r]);
        //cout<<"odg: "<<odg<<endl;
        odg += S(0,w) * S(pret,h);
        //odg += (((w*(w+1)%mod *inv2)%mod) * ((((h*(h+1)%mod * inv2)%mod) - (pret*(pret+1)%mod *inv2)%mod)%mod))%mod + mod;
        ///(x * (x + 1) % mod * inv2) % mod
        odg%=mod;
        //cout<<"odg: "<<odg<<endl;
    }

    cout<<odg<<endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...