oj.uz

Submission #887831

# Submission time Handle Problem Language Result Execution time Memory
887831 2023-12-15T09:35:44 Z cpptowin Fancy Fence (CEOI20_fancyfence) C++17
55 / 100
 231 ms 4348 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 14 ms 3164 KB Output is correct
4 Correct 22 ms 3932 KB Output is correct
5 Correct 28 ms 3932 KB Output is correct
6 Correct 18 ms 3980 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 8 ms 1132 KB Output is correct
4 Correct 15 ms 1912 KB Output is correct
5 Correct 15 ms 1884 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 8 ms 1140 KB Output is correct
5 Correct 16 ms 1884 KB Output is correct
6 Correct 20 ms 1996 KB Output is correct
7 Correct 3 ms 2392 KB Output is correct
8 Correct 23 ms 2652 KB Output is correct
9 Correct 51 ms 3440 KB Output is correct
10 Correct 224 ms 4188 KB Output is correct
11 Correct 231 ms 4348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -