Submission #1084988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084988		vjudge1	Flooding Wall (BOI24_wall)	C++17	44 / 100	172 ms	1920 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
#define for1(i,x,n) for(int i=x;i<=n;i++)
#define for2(i,x,n) for(int i=x;i>=n;i--)
#define int ll

typedef long long ll;
typedef pair<int,int> pii;

const ll maxn=2e5+69;
const ll mod=1e9+7;
const ll inf=1e18;

int n,a[maxn],b[maxn];
int mu2[maxn],chia2;
namespace sub2
{
    void sol()
    {
        int res=0;
        for1(i,1,n)
        {
            res+=(mu2[i-1]-1)*(mu2[n-i]-1)%mod;
            res%=mod;
        }
        cout << res;
    }
}
namespace sub1
{
    int x[50],pre[50],suf[50];
    void sol()
    {
        int ans=0;
        for1(mask,0,(1<<n)-1)
        {
            for1(i,1,n)
            {
                if ((mask>>(i-1))&1) x[i]=a[i];
                else x[i]=b[i];
            }
            for1(i,1,n) pre[i]=max(pre[i-1],x[i]);
            for2(i,n,1) suf[i]=max(suf[i+1],x[i]);
            for1(i,1,n)
            {
                ans+=min(pre[i],suf[i])-x[i];
                ans%=mod;
            }
        }
        cout << ans;
    }
}
namespace sub23
{
    int f[1001]; // fi la so truong hop ma i la gia tri lon nhat, gi=fi*i
    int res[10001];
    void Update(int i)
    {
        int x=0;
        for1(j,0,b[i]) x+=f[j];
        f[b[i]]+=x;
        f[b[i]]%=mod;
        x=0;
        for1(j,0,a[i]-1) x+=f[j],f[j]=0;
        f[a[i]]+=x;
        f[a[i]]%=mod;
        for1(j,b[i]+1,1000) f[j]=f[j]*2%mod;
    }
    int Get(int x)
    {
        int r1=0,r2=0,res=0;
        for1(i,b[x]+1,1000)
        {
            r1+=f[i];
//            if (x==1 && i!=0) cerr<< i<<'\n';
            r2+=f[i]*i%mod;
        }
        r1=(r1%mod)*chia2%mod;
        r2=(r2%mod)*chia2%mod;
        res=r2+mod-(r1*b[x]%mod);
        res%=mod;
        int fb=f[b[x]];
        for1(i,a[x],b[x]-1)
        {
            fb-=f[i];
            r1+=f[i];
            r2+=f[i]*i%mod;
        }
        fb%=mod;
        if (fb<0) fb+=mod;
        fb=fb*chia2%mod;
        r1+=fb;
        r2+=fb*b[x]%mod;
        r1%=mod;
        r2%=mod;
        res+=r2+mod-(r1*a[x]%mod);
//        if (x==1) cerr<< res<<'\n';
        return res%mod;
    }
    void sol()
    {
        f[0]=1;
        for1(i,1,n)
        {
            Update(i);
            res[i]=Get(i)*mu2[n-i]%mod;
        }
        for1(i,0,1000)f[i]=0;
        f[0]=1;
        for2(i,n,1)
        {
            Update(i);
            res[i]=(res[i]+ (Get(i)*mu2[i-1]%mod))%mod;
        }
        int ans=0;
        for1(i,1,n)
        {
            ans=ans+res[i]+mod-Get(i);
            ans%=mod;
        }
        cout << ans;
    }
}
void sol()
{
//    cerr<< pw(2,mod-2);
    chia2=500000004;
    cin >> n;
    for1(i,1,n) cin >> a[i];
    bool is_sub2=1;
    mu2[0]=1;
    for1(i,1,n) mu2[i]=mu2[i-1]*2%mod;
    for1(i,1,n)
    {
        cin >> b[i];
        if (b[i]<a[i]) swap(a[i],b[i]);
        if (a[i]!=1 || b[i]!=2) is_sub2=0;
    }
    if (is_sub2)
    {
        sub2::sol();
        return;
    }
    if (n<=20)
    {
        sub1::sol();
        return;
    }
    if (n<=1e4)
    {
        sub23::sol();
        return;
    }

}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("wall.inp","r",stdin);
//    freopen("wall.out","w",stdout);
    int t=1;//cin >> t;
    while (t--)
    {
        sol();
    }
}
/*

10
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
*/

• Subtask 1: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 19 / 19
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 30