Submission #1105440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105440		alexdd	Flooding Wall (BOI24_wall)	C++17	70 / 100	5070 ms	400628 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
int n,maxh,cate;
int a[500005],b[500005];
int prefmax[500005],suffmax[500005];
int p2[1000005],inv2;

int put(int a, int exp)
{
    if(exp==0)
        return 1;
    if(exp%2==0)
        return put(a*a%MOD,exp/2);
    else
        return put(a*a%MOD,exp/2)*a%MOD;
}

map<int,int> mp,nrm;
int inv[2000005];

int aint[8000005],lazy[8000005];
void build(int nod, int st, int dr)
{
    lazy[nod]=1;
    if(st==dr)
    {
        aint[nod] = inv[dr]-inv[st-1];
        return;
    }
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    aint[nod] = (aint[nod*2] + aint[nod*2+1])%MOD;
}
void propagate(int nod)
{
    if(lazy[nod]==1)
        return;
    lazy[nod*2] = (lazy[nod*2]*lazy[nod])%MOD;
    lazy[nod*2+1] = (lazy[nod*2+1]*lazy[nod])%MOD;
    aint[nod*2] = (aint[nod*2]*lazy[nod])%MOD;
    aint[nod*2+1] = (aint[nod*2+1]*lazy[nod])%MOD;
    lazy[nod]=1;
}
void upd(int nod, int st, int dr, int le, int ri, int newv)
{
    assert(newv!=0);
    if(le>ri)
        return;
    if(le==st && dr==ri)
    {
        lazy[nod] = (lazy[nod]*newv)%MOD;
        aint[nod] = (aint[nod]*newv)%MOD;
        return;
    }
    propagate(nod);
    int mij=(st+dr)/2;
    upd(nod*2,st,mij,le,min(mij,ri),newv);
    upd(nod*2+1,mij+1,dr,max(mij+1,le),ri,newv);
    aint[nod] = (aint[nod*2] + aint[nod*2+1])%MOD;
}
int qry(int nod, int st, int dr, int le, int ri)
{
    if(le>ri)
        return 0;
    if(le==st && dr==ri)
        return aint[nod];
    propagate(nod);
    int mij=(st+dr)/2;
    return (qry(nod*2,st,mij,le,min(mij,ri)) + qry(nod*2+1,mij+1,dr,max(mij+1,le),ri))%MOD;
}

int calc_0(int inc[4][500005])
{
    int rez=0;
    build(1,1,cate);
    for(int i=1;i<=n;i++)
    {
        rez = (rez + p2[n-i]*qry(1,1,cate,nrm[inc[0][i]],nrm[maxh]))%MOD;
        upd(1,1,cate,nrm[b[i]+1],nrm[maxh],2);
    }
    return rez;
}
int calc_1(int inc[4][500005])
{
    int rez=0;
    build(1,1,cate);
    for(int i=n;i>0;i--)
    {
        rez = (rez + qry(1,1,cate,nrm[inc[1][i]],nrm[maxh])*p2[i-1])%MOD;
        upd(1,1,cate,nrm[b[i]+1],nrm[maxh],2);
    }
    return rez;
}
int calc_2(int inc[4][500005])
{
    int rez=0;
    build(1,1,cate);
    for(int i=1;i<=n;i++)
        upd(1,1,cate,nrm[b[i]+1],nrm[maxh],2);
    for(int i=1;i<=n;i++)
    {
        upd(1,1,cate,nrm[b[i]+1],nrm[maxh],inv2);
        rez = (rez + qry(1,1,cate,nrm[inc[2][i]],nrm[maxh]))%MOD;
        /*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;
        }*/
        upd(1,1,cate,nrm[b[i]+1],nrm[maxh],2);
    }
    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;
    inv2 = put(2,MOD-2);
    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]);
        mp[a[i]]++;
        mp[a[i]+1]++;
        mp[b[i]]++;
        mp[b[i]+1]++;
    }
    mp[0]++;
    mp[1]++;
    //for(int i=0;i<=maxh;i++)
      //  mp[i]++;
    for(auto it:mp)
    {
        if(!it.second)
            continue;
        nrm[it.first] = ++cate;
        inv[cate] = it.first;
    }
    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: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 19 / 19
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 0 / 30