Submission #1105426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105426		alexdd	Flooding Wall (BOI24_wall)	C++17	36 / 100	5095 ms	56920 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 cv[500005];

int calc_0(int inc[4][500005])
{
    int rez=0;
    for(int i=1;i<=maxh;i++)
        cv[i]=1;
    for(int i=1;i<=n;i++)
    {
        int aux=0;
        for(int h=inc[0][i];h<=maxh;h++)
        {
            /*int cle=0;
            for(int j=1;j<i;j++)
                if(b[j] < h)
                    cle++;
            aux = (aux + p2[cle])%MOD;*/
            aux = (aux + cv[h])%MOD;
        }
        rez = (rez + p2[n-i]*aux)%MOD;
        for(int j=b[i]+1;j<=maxh;j++)
            cv[j] = cv[j]*2%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 = (rez + 5LL*MOD + maxh - inc[3][i] + 1)%MOD;
    }
    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] = 0;

        for(int j=0;j<4;j++)
        {
            inc[0][j][i] = max(inc[0][j][i], a[i]+1);
            inc[1][j][i] = max(inc[1][j][i], b[i]+1);
        }
    }
    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;
    }
    cout<<rez;
    return 0;
}

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