Submission #1149246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149246		sitablechair	Flooding Wall (BOI24_wall)	C++20	70 / 100	5091 ms	227264 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native,sse,sse2,sse3")
#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "C"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);

#ifdef NCGM
#include"debug.h"
#else
#define debug(...) "fr";
#endif

using namespace std;

const int N=1e6+3,MOD=1e9+7,INV=500000004;

ll binpow(ll x,ll y) {
    x%=MOD;
    ll res=1;
    while(y>0) {
        if (y%2) res=res*x%MOD;
        x=x*x%MOD;
        y/=2;   
    } 
    return res;
}

struct SegTree {
    ll tr[N*4];
    void reset(int id,int l,int r) {
        tr[id]=0;
        if (l==r) return;
        int mid=l+r>>1;
        reset(id*2,l,mid);
        reset(id*2+1,mid+1,r);
    }
    void update(int id,int l,int r,int u,int x) {
        if (l>u || r<u) return;
        if (l==r) return void(tr[id]=x);
        int mid=l+r>>1;
        update(id*2,l,mid,u,x);
        update(id*2+1,mid+1,r,u,x);
        tr[id]=tr[id*2]*tr[id*2+1]%MOD;
    }
    ll query(int id,int l,int r,int u,int v) {
        if (l>v || r<u) return 1;
        if (l>=u && r<=v) return tr[id];
        int mid=l+r>>1;
        return query(id*2,l,mid,u,v)*query(id*2+1,mid+1,r,u,v)%MOD;
    }
} st;
struct SegTree1 {
    struct Node {
        ll x=0,x1=0;
        Node(ll x=0,ll x1=0): x(x),x1(x1) {};
        Node operator + (const Node oth) {
            return Node(x+oth.x,x1+oth.x1);
        }
    } tr[N*4];
    ll lazy[N*4];
    void reset(int id,int l,int r) {
        tr[id]=Node(0,0);
        lazy[id]=1;
        if (l==r) return;
        int mid=l+r>>1;
        reset(id*2,l,mid);
        reset(id*2+1,mid+1,r);
    }
    void push(int id) {
        if (lazy[id]==1) return;
        lazy[id*2]=lazy[id*2]*lazy[id]%MOD;
        lazy[id*2+1]=lazy[id*2+1]*lazy[id]%MOD;
        tr[id*2+1].x=tr[id*2+1].x*lazy[id]%MOD;
        tr[id*2+1].x1=tr[id*2+1].x1*lazy[id]%MOD;
        tr[id*2].x=tr[id*2].x*lazy[id]%MOD;
        tr[id*2].x1=tr[id*2].x1*lazy[id]%MOD;
        lazy[id]=1;
    }
    void update(int id,int l,int r,int u,int v,int x) {
        if (x==1) return;
        if (l>v || r<u) return;
        if (l>=u && r<=v) {
            tr[id].x=tr[id].x*x%MOD;
            tr[id].x1=tr[id].x1*x%MOD;
            lazy[id]=lazy[id]*x%MOD;
            return;
        }
        push(id);
        int mid=l+r>>1;
        update(id*2,l,mid,u,v,x);
        update(id*2+1,mid+1,r,u,v,x);
        tr[id].x=(tr[id*2].x+tr[id*2+1].x);
        tr[id].x1=(tr[id*2].x1+tr[id*2+1].x1);
    }
    void update1(int id,int l,int r,int u,ll x,ll y) {
        if (l>u || r<u) return;
        if (l==r) return void(tr[id]=Node(x,y));
        int mid=l+r>>1;
        update1(id*2,l,mid,u,x,y);
        update1(id*2+1,mid+1,r,u,x,y);
        tr[id].x=(tr[id*2].x+tr[id*2+1].x);
        tr[id].x1=(tr[id*2].x1+tr[id*2+1].x1);
    }
    Node query(int id,int l,int r,int u,int v) {
        if (l>v || r<u) return Node(0,0);
        if (l>=u && r<=v) return tr[id];
        push(id);
        int mid=l+r>>1;
        return query(id*2,l,mid,u,v)+query(id*2+1,mid+1,r,u,v);
    }
} st1;
struct SegTree2 {
    ll tr[N*4],lazy[N*4];
    void reset(int id,int l,int r) {
        tr[id]=0;
        lazy[id]=1;
        if (l==r) return;
        int mid=l+r>>1;
        reset(id*2,l,mid);
        reset(id*2+1,mid+1,r);
    }
    void push(int id) {
        if (lazy[id]==1) return;
        tr[id*2]=tr[id*2]*lazy[id]%MOD;
        tr[id*2+1]=tr[id*2+1]*lazy[id]%MOD;
        lazy[id*2+1]=lazy[id*2+1]*lazy[id]%MOD;
        lazy[id*2]=lazy[id*2]*lazy[id]%MOD;
        lazy[id]=1;
    }
    void update(int id,int l,int r,int u,int v,int x) {
        if (x==1) return;
        if (l>v || r<u) return;
        if (l>=u && r<=v) {
            tr[id]=tr[id]*x%MOD;
            lazy[id]=lazy[id]*x%MOD;
            return;
        }
        push(id);
        int mid=l+r>>1;
        update(id*2,l,mid,u,v,x);
        update(id*2+1,mid+1,r,u,v,x);
        tr[id]=tr[id*2]+tr[id*2+1];
    }
    void update1(int id,int l,int r,int u,ll x) {
        if (l>u || r<u) return;
        if (l==r) return void(tr[id]=x);
        int mid=l+r>>1;
        update1(id*2,l,mid,u,x);
        update1(id*2+1,mid+1,r,u,x);
        tr[id]=tr[id*2]+tr[id*2+1];
    }
    ll query(int id,int l,int r,int u,int v) {
        if (l>v || r<u) return 0;
        if (l>=u && r<=v) return tr[id];
        push(id);
        int mid=l+r>>1;
        return query(id*2,l,mid,u,v)+query(id*2+1,mid+1,r,u,v);
    }
} st2;

int n,a[N],b[N],c[N],d[N],e[N][2],lft[N][2],rgt[N][2];
int f[N],mi[N],ma[N];
ll pw[N*2],pf[N],pf1[N];
vector<pair<int,int>> in[N*2];
vector<ll> big;
ll ans=0;

struct BIT {
    ll pf[N];
    ll query(int p) {
        int idx=p;
        ll ans=0;
        while(idx>0) {
            ans=ans+pf[idx];
            idx-=(idx&(-idx));
        }
        return ans%MOD;
    }
    void update(int u,ll v) {
        int idx=u;
        while(idx<=n) {
            pf[idx]=pf[idx]+v;
            idx+=(idx&(-idx));
        }
    }
} bit1,bit;

int find_set(int u) {
    return (f[u]<0?u:f[u]=find_set(f[u]));
}

void unite(int u,int v) {
    int a=find_set(u),b=find_set(v);
    if (a==b) return;
    if (f[a]>f[b]) swap(a,b);
    f[a]+=f[b];
    f[b]=a;
    mi[a]=min(mi[a],mi[b]);
    ma[a]=max(ma[a],ma[b]);
}

void solve(bool lmao=0) {
    For(i,1,n) bit1.pf[i]=bit.pf[i]=0;
    For(i,1,n) in[lower_bound(all(big),a[i])-big.begin()+1].pb({i,0});
    For(i,1,n) in[lower_bound(all(big),b[i])-big.begin()+1].pb({i,1});
    fill(c,c+1+n,0);
    st1.reset(1,1,n);
    st2.reset(1,1,n);
    if (!lmao) {
        st.reset(1,1,n);
        For(i,1,sz(big)+1) {
            for(auto el: in[i-1]) {
                c[el.ff]++;
                st.update(1,1,n,el.ff,c[el.ff]);
            }
            for(auto el: in[i-1]) {
                ll x=st.query(1,1,n,1,el.ff-1),y=st.query(1,1,n,el.ff+1,n);
                if (el.ff>1 && el.ff<n) {
                    ans=(ans+1LL*(e[el.ff][el.ss])*x%MOD*pw[n-el.ff]%MOD)%MOD;
                    ans=(ans+1LL*(e[el.ff][el.ss])*y%MOD*pw[el.ff-1]%MOD)%MOD;
                    ans=(ans-1LL*(e[el.ff][el.ss])*x%MOD*y%MOD)%MOD;
                }
                else ans=(ans+1LL*(e[el.ff][el.ss])*pw[n-1]%MOD)%MOD;

                if (el.ff>1) lft[el.ff][el.ss]=x;
                else lft[el.ff][el.ss]=1;
                if (el.ff<n) rgt[el.ff][el.ss]=y;
                else rgt[el.ff][el.ss]=1;
            }
        }
    } else {
        For(i,1,n)
            For(k,0,1) swap(lft[i][k],rgt[n-i+1][k]);
    }
    For(i,1,n) f[i]=-1,mi[i]=ma[i]=i,c[i]=0,d[i]=2;
    For(i,1,sz(big)) {
        for(auto el: in[i]) {
            d[el.ff]--;
            if (d[el.ff]==1) st1.update(1,1,n,el.ff,el.ff,INV);
            else st1.update(1,1,n,el.ff,el.ff,0);
        }
        for(auto el: in[i-1]) {
            c[el.ff]++;
            if (c[el.ff]==1) {
                ll tmp=pw[el.ff-1]*binpow(c[el.ff],MOD-2)%MOD*d[el.ff]%MOD;
                if (c[el.ff-1]>0) {
                    ll mmb=st2.query(1,1,n,el.ff-1,el.ff-1)%MOD;
                    st1.update1(1,1,n,el.ff,tmp*(el.ff+1)%MOD*binpow(mmb,MOD-2)%MOD,tmp*binpow(mmb,MOD-2)%MOD);
                    st2.update1(1,1,n,el.ff,c[el.ff]*mmb%MOD);
                    unite(el.ff,el.ff-1);
                } else {
                    st1.update1(1,1,n,el.ff,tmp*(el.ff+1)%MOD,tmp);
                    st2.update1(1,1,n,el.ff,c[el.ff]);
                }
                if (c[el.ff+1]>0) {
                    ll mmb=st2.query(1,1,n,el.ff,el.ff)%MOD;
                    st1.update(1,1,n,el.ff+1,ma[find_set(el.ff+1)],binpow(mmb,MOD-2));
                    st2.update(1,1,n,el.ff+1,ma[find_set(el.ff+1)],mmb);
                    unite(el.ff,el.ff+1);
                }
            } else {
                st1.update(1,1,n,el.ff,ma[find_set(el.ff)],INV);
                st2.update(1,1,n,el.ff,ma[find_set(el.ff)],2);
            }

        }
        for(auto el: in[i]) {
            if (c[el.ff-1]>0) {
                if (mi[find_set(el.ff-1)]<el.ff-1) {
                    auto mmb=st1.query(1,1,n,mi[find_set(el.ff-1)],el.ff-1);
                    ll x=mmb.x%MOD,x1=mmb.x1%MOD;
                    ll tmp=(1LL*x1*el.ff%MOD-x)%MOD;
                    ans=(ans+big[i-1]*rgt[el.ff][el.ss]%MOD*tmp%MOD*(st2.query(1,1,n,el.ff-1,el.ff-1)%MOD)%MOD);
                }
                if (mi[find_set(el.ff-1)]>1) {
                    int j=mi[find_set(el.ff-1)]-1;
                    ll tmp=st2.query(1,1,n,el.ff-1,el.ff-1)%MOD;
                    ll cnst=big[i-1]*tmp%MOD*(el.ff-j-1)%MOD;
                    For(k,0,1) {
                        if (e[j][k]>big[i-1]) ans=(ans+big[i-1]*tmp%MOD*pw[j-1]%MOD*rgt[el.ff][el.ss]%MOD*(el.ff-j-1)%MOD)%MOD;
                        else if (e[j][k]==big[i-1] && !lmao) {
                            ans=(ans+cnst*(pw[j-1]-lft[j][k])%MOD*rgt[el.ff][el.ss]%MOD)%MOD;
                            ans=(ans+cnst*lft[j][k]%MOD*pw[n-el.ff]%MOD)%MOD;
                        }
                    }
                }
            }
            
        }
        if (!lmao) {
            for(auto el: in[i]) {
                ll tmp=(pw[el.ff-1]-lft[el.ff][el.ss])%MOD*big[i-1]%MOD;
                if (c[el.ff]>0) tmp=tmp*binpow(st2.query(1,1,n,el.ff,el.ff)%MOD,MOD-2)%MOD;
                bit.update(el.ff,tmp);
                bit1.update(el.ff,tmp*(el.ff+1)%MOD);
                pf[el.ff]=(pf[el.ff]+tmp)%MOD;
                pf1[el.ff]=(pf1[el.ff]+tmp*(el.ff+1))%MOD;
            }
            for(auto el: in[i]) 
                if (c[el.ff-1] && el.ff-1>mi[find_set(el.ff-1)]) {
                    ll x=bit.query(el.ff-2)-bit.query(mi[find_set(el.ff-1)]-1);
                    ll x1=bit1.query(el.ff-2)-bit1.query(mi[find_set(el.ff-1)]-1);
                    ans=(ans+(el.ff*x%MOD-x1)*rgt[el.ff][el.ss]%MOD*(st2.query(1,1,n,el.ff-1,el.ff-1)%MOD)%MOD)%MOD;
                }
            for(auto el: in[i]) {
                bit.update(el.ff,-pf[el.ff]);
                bit1.update(el.ff,-pf1[el.ff]);
                pf[el.ff]=pf1[el.ff]=0;
            }
            for(auto el: in[i]) {
                ll tmp=lft[el.ff][el.ss]%MOD*big[i-1]%MOD;
                if (c[el.ff]>0) tmp=tmp*binpow(st2.query(1,1,n,el.ff,el.ff)%MOD,MOD-2)%MOD;
                bit.update(el.ff,tmp);
                bit1.update(el.ff,tmp*(el.ff+1)%MOD);
                pf[el.ff]=(pf[el.ff]+tmp)%MOD;
                pf1[el.ff]=(pf1[el.ff]+tmp*(el.ff+1))%MOD;
            }
            for(auto el: in[i]) 
                if (c[el.ff-1] && el.ff-1>mi[find_set(el.ff-1)]) {
                    ll x=bit.query(el.ff-2)-bit.query(mi[find_set(el.ff-1)]-1);
                    ll x1=bit1.query(el.ff-2)-bit1.query(mi[find_set(el.ff-1)]-1);
                    ans=(ans+(el.ff*x%MOD-x1)*pw[n-el.ff]%MOD*(st2.query(1,1,n,el.ff-1,el.ff-1)%MOD)%MOD)%MOD;
                }
            for(auto el: in[i]) {
                bit.update(el.ff,-pf[el.ff]);
                bit1.update(el.ff,-pf1[el.ff]);
                pf[el.ff]=pf1[el.ff]=0;
            }
        }
        
    }
    
    For(i,1,sz(big)) in[i].clear();
}
int main() {
    // fio
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    pw[0]=1;
    For(i,1,n) pw[i]=pw[i-1]*2%MOD;
    For(i,1,n) {
        a[i]=2;
        cin >> a[i];
        e[i][0]=a[i];
        big.pb(a[i]);
    }
    For(i,1,n) {
        b[i]=1;
        cin >> b[i];
        e[i][1]=b[i];
        big.pb(b[i]);
    }
    sort(all(big));
    unq(big);
    solve();
    reverse(b+1,b+1+n);
    reverse(a+1,a+1+n);
    For(i,1,n) {
        e[i][0]=a[i];
        e[i][1]=b[i];
    }
    solve(1);
    For(i,1,n) ans=(ans-1LL*a[i]*pw[n-1]%MOD)%MOD;
    For(i,1,n) ans=(ans-1LL*b[i]*pw[n-1]%MOD)%MOD;
    ans=(ans+MOD)%MOD;
    cout << ans;

    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