Submission #1171434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171434		danglayloi1	Fancy Fence (CEOI20_fancyfence)	C++20	73 / 100	1095 ms	3180 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 pw(ll a, ll n)
{
    if(!n) return 1;
    ll tmp=pw(a, n>>1);
    tmp=mul(tmp, tmp);
    if(n&1) tmp=mul(tmp, a);
    return tmp;
}
ll base;
ll get(ll l, ll r)
{
    return mul(mul(add(l, r), (r-l+1+mod)%mod), base);
}
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);
    base=pw(2, mod-2);
    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: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 0 / 27