Submission #887831

#	Time	Username	Problem	Language	Result	Execution time	Memory
887831		cpptowin	Fancy Fence (CEOI20_fancyfence)	C++17	55 / 100	231 ms	4348 KiB

fancyfence

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;
ll n,h[100005],w[100005],a,b,c,d,sub3=1,m[55][55],sum[55][55],sub2=1,cc[100005],cd[100005],tong[100005],sub4=1;
ll getsum(ll u,ll v,ll x,ll y)
{
    return sum[u][v]-sum[u][y-1]-sum[x-1][v]+sum[x-1][y-1];
}
long long nhan(long long a, long long b, long long mod)
{
    if (b == 0)
        return 0;

    long long t = nhan(a, b / 2, mod) % mod;

    if (b & 1)
        return ((t + t) % mod + a % mod) % mod;
    else
        return (t + t) % mod;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("brickwall.inp","r",stdin);
    // freopen("brickwall.out","w",stdout);
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>h[i];
        c=h[i];
        if(i>1&&h[i]!=h[i-1])
        {
            sub3=0;
        }
        if(h[i]>2||h[i]<1)
        {
            sub2=0;
        }
        if(i>1&&h[i]<h[i-1])
        {
            sub4=0;
        }
    }
    for(int i=1; i<=n; i++)
    {
        cin>>w[i];
        a+=w[i];
    }
    if(sub3==1)
    {
        b=a+1;
        d=c+1;
        if(a%2==0)
        {
            a/=2;
        }
        else b/=2;
        if(c%2==0)
        {
            c/=2;
        }
        else d/=2;
        ll ans=nhan(nhan(a,b,mod)%mod,nhan(c,d,mod)%mod,mod)%mod;
        cout<<ans%mod;
        return 0;
    }
    if(sub2==1)
    {
        a=b=0;
        ll cnt=1;
        a=w[1];
        ll ans=h[1]*w[1];
        ans%=mod;
        cc[cnt]=h[1];
        cd[cnt]=w[1];
        for(int i=2; i<=n; i++)
        {
            if(h[i]==h[i-1])
            {
                cd[cnt]+=w[i];
            }
            else
            {
                cnt++;
                cc[cnt]=h[i];
                cd[cnt]=w[i];
            }
            ans=(ans+h[i]*w[i])%mod;
            a+=w[i];
        }
        b=a-1;
        if(a%2==0)
        {
            a/=2;
        }
        else b/=2;
        ans=(ans+nhan(a,b,mod))%mod;
        for(int i=1; i<=cnt; i++)
        {
            // cout<<cc[i]<<' '<<cd[i]<<'\n';
            if(cc[i]==2)
            {
                a=cd[i];
                ans=(ans+cd[i])%mod;
                b=a-1;
                if(a%2==0)
                {
                    a/=2;
                }
                else b/=2;
                ans=(ans+nhan(a,b,mod))%mod;
                a=cd[i];
                b=a-1;
                if(a%2==0)
                {
                    a/=2;
                }
                else b/=2;
                ans=(ans+nhan(a,b,mod))%mod;
            }
        }
        cout<<ans%mod;
        return 0;
    }
    if(sub4==1)
    {
        ll cnt=1;
        ll ans=0;
        cc[cnt]=h[1];
        cd[cnt]=w[1];
        for(int i=2; i<=n; i++)
        {
            if(h[i]==h[i-1])
            {
                cd[cnt]+=w[i];
            }
            else
            {
                cnt++;
                cc[cnt]=h[i];
                cd[cnt]=w[i];
            }
        }
        for(int i=1; i<=cnt; i++)
        {
            tong[i]=tong[i-1]+cd[i];
        }
        for(int i=1; i<=cnt; i++)
        {
            a=cc[i];
            c=tong[cnt]-tong[i-1];
            b=a+1;
            d=c+1;
            if(a%2==0)
            {
                a/=2;
            }
            else b/=2;
            if(c%2==0)
            {
                c/=2;
            }
            else d/=2;
            ans=(ans%mod+nhan(nhan(a,b,mod)%mod,nhan(c,d,mod)%mod,mod)%mod)%mod;
            a=cc[i-1];
            c=tong[cnt]-tong[i-1];
            b=a+1;
            d=c+1;
            if(a%2==0)
            {
                a/=2;
            }
            else b/=2;
            if(c%2==0)
            {
                c/=2;
            }
            else d/=2;
            ans=(ans%mod-nhan(nhan(a,b,mod)%mod,nhan(c,d,mod)%mod,mod)%mod+mod*mod)%mod;
        }
        cout<<ans%mod;
        return 0;
    }
    if(n<=52)
    {
        ll ans=0;
        for(int i=1; i<=51; i++)
        {
            for(int j=1; j<=51; j++)
            {
                m[i][j]=1;
            }
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=h[i]; j++)
            {
                m[i][j]=0;
            }
        }
        for(int i=1; i<=51; i++)
        {
            for(int j=1; j<=51; j++)
            {
                sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+m[i][j];
            }
        }
        for(int i=1; i<=51; i++)
        {
            for(int j=1; j<=51; j++)
            {
                for(int u=i; u<=51; u++)
                {
                    for(int v=j; v<=51; v++)
                    {
                        if(getsum(u,v,i,j)==0)
                        {
                            ans++;
                            ans%=mod;
                        }
                    }
                }
            }
        }
        cout<<ans%mod;
        return 0;
    }
    return 0;
}
/*
2
1 2
1 1
*/

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