Submission #1244961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244961		Jovica	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	57 ms	8164 KiB

fancyfence

#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;
    vector<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_back({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;
    sort(pq.begin(),pq.end());
    for (int i=0;i<pq.size();i++)
    {
        int p = pq[i][1];
        ll h = pq[i][0];
        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;
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27