Submission #1254022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254022		Zbyszek99	Flooding Wall (BOI24_wall)	C++20	58 / 100	5091 ms	31856 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;

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

void solve(pll* H, pll* ans0, pll* ans1, bool is = 0)
{
    rep(i,n*2+1)
    {
        dp[i] = {0,0};
    }
    dp[0] = {0,1};
    rep(i,n)
    {
        pll dp0 = {0,0};
        rep2(j,0,H[i].ff-1)
        {
            dp0.ff += dp[j].ff;
            dp0.ss += dp[j].ss;
            dp0.ff %= MOD;
            dp0.ss %= MOD;
        }
        ans0[i] = dp0;
        if(is)
        {
            ans0[i].ff += dp[H[i].ff].ff;
            ans0[i].ss += dp[H[i].ff].ss;
            ans0[i].ff %= MOD;
            ans0[i].ss %= MOD;    
        }
        pll dp1 = {0,0};
        rep2(j,0,H[i].ss-1)
        {
            dp1.ff += dp[j].ff;
            dp1.ss += dp[j].ss;
            dp1.ff %= MOD;
            dp1.ss %= MOD;
        }
        ans1[i] = dp1;
        if(is)
        {
            ans1[i].ff += dp[H[i].ss].ff;
            ans1[i].ss += dp[H[i].ss].ss;
            ans1[i].ff %= MOD;
            ans1[i].ss %= MOD;    
        }
        dp0.ff += dp[H[i].ff].ff;
        dp0.ss += dp[H[i].ff].ss;
        dp0.ff %= MOD;
        dp0.ss %= MOD;
        rep2(j,0,H[i].ff-1) dp[j] = {0,0};
        dp[H[i].ff] = dp0;
        rep2(j,H[i].ff+1,H[i].ss-1)
        {
            dp[j] = {dp[j].ff+(rel_val[j]-rel_val[H[i].ff])*dp[j].ss,dp[j].ss};
            dp[j].ff %= MOD;
        }
        rep2(j,H[i].ss,n*2)
        {
            dp[j] = {dp[j].ff*2+(2*rel_val[j]-rel_val[H[i].ff]-rel_val[H[i].ss])*dp[j].ss,dp[j].ss*2};
            dp[j].ff %= MOD;
            dp[j].ss %= MOD;
        }
        dp[H[i].ss].ff += dp1.ff;
        dp[H[i].ss].ss += dp1.ss;
        dp[H[i].ss].ff %= MOD;
        dp[H[i].ss].ss %= MOD;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    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: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 19 / 19
• Subtask 4: 14 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 30