Submission #1254194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254194		Zbyszek99	Flooding Wall (BOI24_wall)	C++20	100 / 100	4254 ms	211460 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

ll P[2000051];

int tree_siz = 1024*2048-1;
pll tags[1024*2048];
ll val_sum[1024*2048];
ll cnt_sum[1024*2048];
ll mul[1024*2048];

inline void add_tag(int v, pll t)
{
    val_sum[v] = (((val_sum[v]+mul[v]*t.ff)%MOD)*P[t.ss])%MOD;
    mul[v] = (mul[v]*P[t.ss])%MOD;
    cnt_sum[v] = (cnt_sum[v]*P[t.ss])%MOD;
}

inline void upd(int v)
{
    if(tags[v].ff == 0) return;
    tags[v*2].ff += tags[v].ff;
    tags[v*2].ss += tags[v].ss;
    tags[v*2+1].ff += tags[v].ff;
    tags[v*2+1].ss += tags[v].ss;
    add_tag(v*2,tags[v]);
    add_tag(v*2+1,tags[v]);
    tags[v] = {0,0};
}

void add_tag(int akt, int p1, int p2, int s1, int s2, const pll& t)
{
    if(p2 < s1 || p1 > s2) return;
    if(p1 >= s1 && p2 <= s2)
    {
        tags[akt].ff += t.ff;
        tags[akt].ss += t.ss;
        add_tag(akt,t);
        return;
    }
    upd(akt);
    add_tag(akt*2,p1,(p1+p2)/2,s1,s2,t);
    add_tag(akt*2+1,(p1+p2)/2+1,p2,s1,s2,t);
    val_sum[akt] = (val_sum[akt*2]+val_sum[akt*2+1])%MOD;
    cnt_sum[akt] = (cnt_sum[akt*2]+cnt_sum[akt*2+1])%MOD;
    mul[akt] = (mul[akt*2]+mul[akt*2+1])%MOD;
}

pll get_seg(int akt, int p1, int p2, int s1, int s2)
{
    if(p2 < s1 || p1 > s2) return {0,0};
    if(p1 >= s1 && p2 <= s2)
    {
        return {val_sum[akt],cnt_sum[akt]};
    }
    upd(akt);
    pll w1 = get_seg(akt*2,p1,(p1+p2)/2,s1,s2);
    pll w2 = get_seg(akt*2+1,(p1+p2)/2+1,p2,s1,s2);
    return {(w1.ff+w2.ff),(w1.ss+w2.ss)};
}

ll setval;
ll setcnt;
ll setmul;

void set_val(int akt, int poz, int p1, int p2)
{
    while(p1 != p2)
    {
        upd(akt);
        if(poz <= (p1+p2)/2)
        {
            akt *= 2;
            p2 = (p1+p2)/2;
        }
        else 
        {
            akt = akt*2+1;
            p1 = (p1+p2)/2+1;
        }
    }
    tags[akt] = {0,0};
    val_sum[akt] = setval;
    cnt_sum[akt] = setcnt;
    mul[akt] = setmul;
    akt/=2;
    while(akt != 1)
    {
        val_sum[akt] = (val_sum[akt*2]+val_sum[akt*2+1])%MOD;
        cnt_sum[akt] = (cnt_sum[akt*2]+cnt_sum[akt*2+1])%MOD;
        mul[akt] = (mul[akt*2]+mul[akt*2+1])%MOD;
        akt /= 2;
    }
}

pii H2[500001];
ll rel_val[2000001];
pll left_dp[2][500001];
pll right_dp[2][500001];
int n;
int max_siz = 0;

void solve(pii* H, pll* ans0, pll* ans1, bool is = 0)
{
    for(int i = 1; i <= tree_siz; i++)
    {
        tags[i] = {0,0};
        cnt_sum[i] = 0;
        val_sum[i] = 0;
        mul[i] = 0;
    }
    setval = 0;
    setcnt = 1;
    setmul = 0;
    set_val(1,0,0,tree_siz/2);
    int zero_pref = -1;
    pll dp0;
    pll dp1;
    pll H1_val;
    pll H2_val;
    rep(i,n)
    {
        dp0 = get_seg(1,0,tree_siz/2,0,H[i].ff-1);
        dp1 = get_seg(1,0,tree_siz/2,0,H[i].ss-1);
        dp0.ff %= MOD;
        dp0.ss %= MOD;
        dp1.ff %= MOD;
        dp1.ss %= MOD;
        H1_val = get_seg(1,0,tree_siz/2,H[i].ff,H[i].ff);
        H2_val = get_seg(1,0,tree_siz/2,H[i].ss,H[i].ss);
        ans0[i] = dp0;
        if(is)
        {
            ans0[i].ff += H1_val.ff;
            ans0[i].ss += H1_val.ss;
            ans0[i].ff %= MOD;
            ans0[i].ss %= MOD;    
        }
        ans1[i] = dp1;
        if(is)
        {
            ans1[i].ff += H2_val.ff;
            ans1[i].ss += H2_val.ss;
            ans1[i].ff %= MOD;
            ans1[i].ss %= MOD;    
        }
        dp0.ff += H1_val.ff;
        dp0.ss += H1_val.ss;
        dp0.ff %= MOD;
        dp0.ss %= MOD;
        rep2(j,zero_pref+1,H[i].ff-1)
        {
            setval = 0;
            setcnt = 0;
            setmul = 0;
            set_val(1,j,0,tree_siz/2);
        }
        zero_pref = max(zero_pref,H[i].ff-1);
        if(H[i].ff > zero_pref)
        {
            setval = dp0.ff+(rel_val[H[i].ff]*dp0.ss)%MOD;
            setcnt = dp0.ss;
            setmul = (rel_val[H[i].ff]*dp0.ss)%MOD;
            set_val(1,H[i].ff,0,tree_siz/2);
        }
        if(H[i].ff+1 <= H[i].ss-1 && H[i].ss-1 > zero_pref)
        {
            add_tag(1,0,tree_siz/2,H[i].ff+1,H[i].ss-1,{1,0});
        }
        add_tag(1,0,tree_siz/2,H[i].ss+1,max_siz,{1,1});
        if(H[i].ss > zero_pref)
        {
            H2_val = {H2_val.ff*2+(2*rel_val[H[i].ss])*H2_val.ss,H2_val.ss*2};
            H2_val.ff += dp1.ff;
            H2_val.ss += dp1.ss;
            H2_val.ff %= MOD;
            H2_val.ss %= MOD;
            setval = H2_val.ff+(rel_val[H[i].ss]*dp1.ss)%MOD;
            setcnt = H2_val.ss;
            setmul = (rel_val[H[i].ss]*H2_val.ss)%MOD;
            set_val(1,H[i].ss,0,tree_siz/2);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    P[0] = 1;
    rep2(i,1,2000050)
    {
        P[i] = (P[i-1]*2)%MOD;
    }
    cin >> n;
    vl a(n);
    vl b(n);
    rep(i,n) cin >> a[i];
    rep(i,n) cin >> b[i];
    rep(i,n) if(a[i] > b[i]) swap(a[i],b[i]);
    map<ll,int> m;
    rep(i,n) m[a[i]] = 1;
    rep(i,n) m[b[i]] = 1;
    int cur = 1;
    forall(it,m)
    {
        rel_val[cur] = it.ff;
        m[it.ff] = cur++;
    }
    max_siz = cur;
    tree_siz = (1 << (__lg(max_siz)+2))-1;
    rep(i,n)
    {
        H2[i] = {m[a[i]],m[b[i]]};
    }
    solve(H2,left_dp[0],left_dp[1],1);
    reverse(H2,H2+n);
    solve(H2,right_dp[0],right_dp[1]);
    reverse(H2,H2+n);
    reverse(right_dp[0],right_dp[0]+n);
    reverse(right_dp[1],right_dp[1]+n);
    ll ans = 0;
    rep(i,n)
    {
        rep(d,2)
        {
            ans += left_dp[d][i].ff*right_dp[d][i].ss;
            ans %= MOD;
            ll val = a[i];
            if(d == 1) val = b[i];
            ans += left_dp[d][i].ss*(right_dp[d][i].ff + (right_dp[d][i].ss*val)%MOD);
            ans %= MOD;
        }
    }
    rep(i,n)
    {
        ans = (ans - (a[i]*P[n-1])%MOD + MOD)%MOD;
        ans = (ans - (b[i]*P[n-1])%MOD + MOD)%MOD;
    }
    cout << ans << "\n";
}

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