Submission #442775

#	Time	Username	Problem	Language	Result	Execution time	Memory
442775		flashhh	Fancy Fence (CEOI20_fancyfence)	C++14	12 / 100	1 ms	460 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],w[nmax];

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

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

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; if (t%2==0) 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) %oo;
        f[i] = (f[i] + f[l] * range(i,i) %oo) %oo;
    }
    
    int res=0;
    for (int i=1;i<=n;++i) res=(res+f[i])%oo;
    
    cout<<res;
    return 0;
}

Compilation message (stderr)

fancyfence.cpp: In function 'long long int cal(long long int, long long int)':
fancyfence.cpp:29:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   29 |     if (z%2==0) z/=2; if (t%2==0) t/=2;
      |     ^~
fancyfence.cpp:29:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   29 |     if (z%2==0) z/=2; if (t%2==0) t/=2;
      |                       ^~

• 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