Submission #1171429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171429		danglayloi1	Fancy Fence (CEOI20_fancyfence)	C++20	12 / 100	1 ms	328 KiB

fancyfence

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=1e5+5;
ll add(ll a, ll b)
{
    a+=b;
    if(a>=mod) a-=mod;
    return a;
}
ll mul(ll a, ll b)
{
    a*=b;
    if(a>=mod) a%=mod;
    return a;
}
ll del(ll a, ll b)
{
    a-=b;
    if(a<0) a+=mod;
    return a;
}
ll get(ll l, ll r)
{
    return ((l+r)*(r-l+1)/2)%mod;
}
int n, r[nx];
ll h[nx], w[nx], ans=0, pre[nx];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++)
        cin>>h[i];
    for(int i = 1; i <= n; i++)
        cin>>w[i], pre[i]=add(pre[i-1], w[i]);
    for(int i = n; i >= 1; i--)
    {
        r[i]=i+1;
        while(r[i]<=n && h[r[i]]>=h[i])
            r[i]=r[r[i]];
    }
    for(int i = 1; i <= n; i++)
    {
        int pos=r[i];
        ll hei=h[i];
        while(true)
        {
            ll len=del(pre[pos-1], pre[i-1]);
            ans=add(ans, mul(get(del(len, w[i]-1), len), get(h[pos]+1, hei)));
            if(pos>n) break;
            hei=h[pos];
            pos=r[pos];
        }
    }
    cout<<ans;
}

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