Submission #442788

#	Time	Username	Problem	Language	Result	Execution time	Memory
442788		flashhh	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	97 ms	15236 KiB

fancyfence

#include <bits/stdc++.h>
#define nmax 100010
#define ll long long

const int oo=1e9+7;

using namespace std;

int n,h[nmax],rmq[nmax][25];
ll f[nmax],g[nmax],w[nmax];

ll range(int l,int r)
{
    if (l==0) return w[r];
    return w[r]-w[l-1];
}

ll get(int x,int y)
{
    int z=log2(y-x+1);
    return min(rmq[x][z],rmq[y-(1<<z)+1][z]);
}

int rangemod(int l,int r)
{
    if (l==0) return w[r]%oo;
    return (w[r]-w[l-1])%oo;
}

ll cal(ll x,ll y)
{
    if (x>y) return 0;
    
    ll z=x+y; ll t=y-x+1;
    if (z%2==0) z/=2; else t/=2;
    z%=oo; t%=oo;
    
    return z*t%oo;
}

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];
        rmq[i][0]=h[i];
    }
    
    for (int i=1;i<=n;++i)
    {
        cin>>w[i];
        w[i]+=w[i-1];
    }
    
    for (int j=1;j<20;++j)
        for (int i=0;i<=n-(1<<j)+1;++i)
            rmq[i][j]=min(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
    
    for (int i=1;i<=n;++i)
    {
        int l=0; int r=i-1;
        while (l<r)
        {
            int mid=(l+r+1)>>1;
            if (get(mid,i)<h[i]) l=mid;
            else r=mid-1;
        }
        
        f[i] = f[i] + cal(1,h[i]) * cal(range(l+1,i-1)+1,range(l+1,i)) %oo; if (f[i]>=oo) f[i]-=oo;
        f[i] = f[i] + g[l] * rangemod(i,i) %oo; if (f[i]>=oo) f[i]-=oo;
        
        g[i] = g[i] + cal(1,h[i]) * rangemod(l+1,i) %oo; if (g[i]>=oo) g[i]-=oo;
        g[i] = g[i] + g[l]; if (g[i]>=oo) g[i]-=oo;
    }
    
    int res=0;
    for (int i=1;i<=n;++i)
    {
        res+=f[i];
        if (res>=oo) res-=oo;
    }
    
    cout<<res;
    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