Submission #1105413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105413		alexdd	Flooding Wall (BOI24_wall)	C++17	17 / 100	5064 ms	17976 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
int n,maxh;
int a[500005],b[500005];
int prefmax[500005],suffmax[500005];
int p2[1000005];
int calc_0(int inc[4][500005])
{
    int rez=0;
    for(int i=1;i<=n;i++)
    {
        for(int h=inc[0][i];h<=maxh;h++)
        {
            int cle=0;
            for(int j=1;j<i;j++)
                if(b[j] < h)
                    cle++;
            rez = (rez + p2[n-i+cle])%MOD;
        }
    }
    return rez;
}
int calc_1(int inc[4][500005])
{
    int rez=0;
    for(int i=1;i<=n;i++)
    {
        for(int h=inc[1][i];h<=maxh;h++)
        {
            int cri=0;
            for(int j=i+1;j<=n;j++)
                if(b[j] < h)
                    cri++;
            rez = (rez + p2[i-1+cri])%MOD;
        }
    }
    return rez;
}
int calc_2(int inc[4][500005])
{
    int rez=0;
    for(int i=1;i<=n;i++)
    {
        for(int h=inc[2][i];h<=maxh;h++)
        {
            int cnt=0;
            for(int j=1;j<=n;j++)
                if(j!=i && b[j] < h)
                    cnt++;
            rez = (rez + p2[cnt])%MOD;
        }
    }
    return rez;
}
int calc_3(int inc[4][500005])
{
    int rez=0;
    for(int i=1;i<=n;i++)
    {
        rez += maxh - inc[i][3];
    }
    for(int i=1;i<n;i++)
        rez = rez*2%MOD;
    return rez;
}
int inc[2][4][500005];
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    p2[0]=1;
    for(int i=1;i<=1000000;i++)
        p2[i] = p2[i-1]*2%MOD;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
        if(a[i]>b[i])
            swap(a[i],b[i]);
        maxh = max(maxh, b[i]);
    }
    int rez=0;
    /*for(int i=1;i<=n;i++)
        prefmax[i] = max(prefmax[i-1], a[i]);
    for(int i=n;i>0;i--)
        suffmax[i] = max(suffmax[i+1], a[i]);
    for(int i=1;i<=n;i++)
    {
        inc[0][0][i] = inc[1][0][i] = prefmax[i-1]+1;
        inc[0][1][i] = inc[1][1][i] = suffmax[i+1]+1;
        inc[0][2][i] = inc[1][2][i] = max(prefmax[i-1], suffmax[i+1]) + 1;
        inc[0][3][i] = inc[1][3][i] = min(prefmax[i-1], suffmax[i+1]) + 1;

        for(int j=0;j<4;j++)
        {
            inc[0][j][i] = max(inc[0][j][i], a[i]);
            inc[1][j][i] = max(inc[1][j][i], b[i]);
        }
    }
    for(int i=0;i<2;i++)
    {
        rez = (rez + calc_3(inc[i]) + calc_2(inc[i]))%MOD;
        rez = (rez + MOD - calc_0(inc[i]))%MOD;
        rez = (rez + MOD - calc_1(inc[i]))%MOD;
    }*/
    rez=0;
    for(int i=1;i<=n;i++)
    {
        for(int h=a[i]+1;h<=maxh;h++)
        {
            int cle=0,cri=0,ble=1,bri=1;
            for(int j=1;j<i;j++)
            {
                if(b[j] < h)
                    cle++;
                if(a[j] >= h)
                    ble = 0;
            }
            for(int j=i+1;j<=n;j++)
            {
                if(b[j] < h)
                    cri++;
                if(a[j] >= h)
                    bri = 0;
            }
            int aux = (p2[i-1] - p2[cle]*ble + MOD) * (p2[n-i] - p2[cri]*bri + MOD)%MOD;
            rez = (rez + aux)%MOD;
            if(h > b[i]) rez = (rez + aux)%MOD;
        }
    }
    cout<<rez;
    return 0;
}

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