Submission #1254092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254092		Zbyszek99	Flooding Wall (BOI24_wall)	C++20	0 / 100	5103 ms	186076 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#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[2000001];
ll odwP[2000001];

ll odw(ll x)
{
    ll ans = 1;
    rep(bit,30)
    {
        if((MOD-2) & (1 << bit))
        {
            ans *= x;
            ans %= MOD;
        }
        x *= x;
        x %= MOD;
    }    
    return ans;
}

struct tag
{
    ll i=0,x=0,c=0,d=0;
    tag operator+(const tag& other)
    {
        tag res;
        res.i = (i+((other.i*P[d])%MOD)*odwP[c])%MOD;
        res.x = (x+((other.x*P[d])%MOD)*odwP[c])%MOD;
        res.c = c+other.c;
        res.d = d+other.d;
        return res;
    }
};

tag def;

struct node
{
    ll val_sum=0,cnt_sum=0,mul=0;
    void add_tag(const tag& other)
    {
        val_sum = (((val_sum+mul*other.i + cnt_sum*other.x)%MOD)*P[other.c])%MOD;
        mul = (mul*P[other.d])%MOD;
        cnt_sum = (cnt_sum*P[other.d])%MOD;
    }
    node operator+(const node& other)
    {
        node res;
        res.val_sum = (val_sum+other.val_sum)%MOD;
        res.cnt_sum = (cnt_sum+other.cnt_sum)%MOD;
        res.mul = (mul+other.mul)%MOD;
        return res;
    }
};

const int tree_siz = 1024*2048-1;
tag tags[tree_siz+1];
node nodes[tree_siz+1];

void upd(int v)
{
    tags[v*2] = (tags[v*2]+tags[v]);
    tags[v*2+1] = (tags[v*2+1]+tags[v]);
    nodes[v*2].add_tag(tags[v]);
    nodes[v*2+1].add_tag(tags[v]);
    tags[v] = def;
}

void add_tag(int akt, int p1, int p2, int s1, int s2, const tag& t)
{
    if(p2 < s1 || p1 > s2) return;
    if(p1 >= s1 && p2 <= s2)
    {
        tags[akt] = (tags[akt]+t);
        nodes[akt].add_tag(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);
    nodes[akt] = nodes[akt*2]+nodes[akt*2+1];
}

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 {nodes[akt].val_sum,nodes[akt].cnt_sum};
    }
    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)%MOD,(w1.ss+w2.ss)%MOD};
}

void set_val(int akt, int poz, int p1, int p2, const node& p)
{
    if(p1 == p2)
    {
        tags[akt] = def;
        nodes[akt] = p;
        return;
    }
    upd(akt);
    if(poz <= (p1+p2)/2) set_val(akt*2,poz,p1,(p1+p2)/2,p);
    else set_val(akt*2+1,poz,(p1+p2)/2+1,p2,p);
    nodes[akt] = nodes[akt*2]+nodes[akt*2+1];
}

pll H2[500001];
ll rel_val[2000001];
pll left_dp[2][500001];
pll right_dp[2][500001];
int n;

void solve(pll* H, pll* ans0, pll* ans1, bool is = 0)
{
    for(int i = tree_siz/2+1; i <= tree_siz; i++)
    {
        tags[i] = def;
        nodes[i].cnt_sum = 0;
        nodes[i].val_sum = 0;
        nodes[i].mul = 0;
    }
    for(int i = tree_siz/2; i >= 1; i--)
    {
        tags[i] = def;
        nodes[i] = nodes[i*2]+nodes[i*2+1];
    }
    set_val(1,0,0,tree_siz/2,{0,1,rel_val[0]});
    ll zero_pref = -1;
    rep(i,n)
    {
        pll dp0 = get_seg(1,0,tree_siz/2,0,H[i].ff-1);
        pll dp1 = get_seg(1,0,tree_siz/2,0,H[i].ss-1);
        pll H1_val = get_seg(1,0,tree_siz/2,H[i].ff,H[i].ff);
        pll 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)
        {
            set_val(1,j,0,tree_siz/2,{0,0,0});
        }
        zero_pref = max(zero_pref,H[i].ff-1);
        node new_dp0 = {dp0.ff,dp0.ss,(rel_val[H[i].ff]*dp0.ss)%MOD};
        set_val(1,H[i].ff,0,tree_siz/2,new_dp0);
        if(H[i].ff+1 <= H[i].ss-1)
        {
            tag t1 = {1,(-rel_val[H[i].ff]+MOD)%MOD,0,0};
            add_tag(1,0,tree_siz/2,H[i].ff+1,H[i].ss-1,t1);
        }
        tag t2 = {1,(((-rel_val[H[i].ff]-rel_val[H[i].ss]+2*MOD)%MOD)*odwP[1])%MOD,1,1};
        add_tag(1,0,tree_siz/2,H[i].ss+1,n*2,t2);
        node new_dp1 = {H2_val.ff,H2_val.ss,(rel_val[H[i].ss]*H2_val.ss)%MOD}; 
        new_dp1.add_tag(t2);
        new_dp1.val_sum += dp1.ff;
        new_dp1.cnt_sum += dp1.ss;
        new_dp1.val_sum %= MOD;
        new_dp1.cnt_sum %= MOD;
        set_val(1,H[i].ss,0,tree_siz/2,new_dp1);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    P[0] = 1;
    odwP[0] = 1;
    rep2(i,1,2000000)
    {
        P[i] = (P[i-1]*2)%MOD;
        odwP[i] = odw(P[i]);
    }
    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++;
    }
    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;
            ans += left_dp[d][i].ss*right_dp[d][i].ff;
            ans %= MOD;
        }
    }
    cout << ans << "\n";
}

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