Submission #1214446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214446		stefanneagu	Flooding Wall (BOI24_wall)	C++20	58 / 100	4398 ms	784732 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e4 + 2, Nmax = 5e5 + 1, mod = 1e9 + 7;

struct str {
    int a, b;
} v[Nmax];

int dps[nmax][nmax * 2];
int dpp[2][nmax * 2];
int sp[nmax * 2];
int bk[nmax * 2];
long long p2[Nmax];
int vmax;

void add(int &a, int b) {
    a += b;
    if (a >= mod) {
        a -= mod;
    }
}

void norm(int n) {
    map<int, int> N;
    for (int i = 1; i <= n; i++) {
        N[v[i].a];
        N[v[i].b];
    }
    for (auto &[a, b] : N) {
        b = ++vmax;
        bk[vmax] = a;
    }
    for (int i = 1; i <= n; i++) {
        v[i].a = N[v[i].a];
        v[i].b = N[v[i].b];
    }
}

void pre2() {
    p2[0] = 1;
    for (int i = 1; i < Nmax; i++) {
        p2[i] = p2[i - 1];
        p2[i] %= mod;
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i].a;
    }
    for (int i = 1; i <= n; i++) {
        cin >> v[i].b;
    }
    int ans = 0;
    if (n > nmax) {
        pre2();
        for (int i = 2; i < n; i++) {
            add(ans, ((p2[i - 1] - 1 + mod) * (p2[n - i] - 1 + mod)) % mod);
        }
        cout << ans;
        return 0;
    }
    norm(n);
    dps[n][v[n].a] = 1;
    dps[n][v[n].b] = 1;
    for (int i = n - 1; i >= 1; i--) {
        for (int val = 1; val <= v[i].a; val++) {
            add(dps[i][v[i].a], dps[i + 1][val]);
        }
        for (int val = v[i].a + 1; val <= vmax; val++) {
            add(dps[i][val], dps[i + 1][val]);
        }
        for (int val = 1; val <= v[i].b; val++) {
            add(dps[i][v[i].b], dps[i + 1][val]);
        }
        for (int val = v[i].b + 1; val <= vmax; val++) {
            add(dps[i][val], dps[i + 1][val]);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = vmax; j >= 1; j--) {
            add(dps[i][j], dps[i][j + 1]);
        }
    }
    dpp[1][v[1].a] = 1;
    dpp[1][v[1].b] = 1;
    for (int i = 2; i <= n; i++) {
        sp[vmax + 1] = 0;
        for (int val = vmax; val >= 1; val--) {
            sp[val] = sp[val + 1];
            add(sp[val], dpp[(i - 1) & 1][val]);
            dpp[i & 1][val] = 0;
        }
        // set v[i].a
        for (int val = v[i].a + 1; val <= vmax; val++) {
            add(ans, (1ll * ((1ll * (bk[val] - bk[v[i].a]) * dpp[(i - 1) & 1][val]) % mod) * dps[i + 1][val]) % mod);
            add(ans, (1ll * ((1ll * (bk[val] - bk[v[i].a]) * sp[val]) % mod) * ((dps[i + 1][val] - dps[i + 1][val + 1] + mod) % mod)) % mod);
            add(ans, (mod - ((1ll * ((1ll * (bk[val] - bk[v[i].a]) * dpp[(i - 1) & 1][val]) % mod) * ((dps[i + 1][val] - dps[i + 1][val + 1] + mod) % mod)) % mod)));
        }
        // set v[i].b
        for (int val = v[i].b + 1; val <= vmax; val++) {
            add(ans, (1ll * ((1ll * (bk[val] - bk[v[i].b]) * dpp[(i - 1) & 1][val]) % mod) * dps[i + 1][val]) % mod);
            add(ans, (1ll * ((1ll * (bk[val] - bk[v[i].b]) * sp[val]) % mod) * ((dps[i + 1][val] - dps[i + 1][val + 1] + mod) % mod)) % mod);
            add(ans, (mod - ((1ll * ((1ll * (bk[val] - bk[v[i].b]) * dpp[(i - 1) & 1][val]) % mod) * ((dps[i + 1][val] - dps[i + 1][val + 1] + mod) % mod)) % mod)));
        }
        for (int val = v[i].a + 1; val <= vmax; val++) {
            add(dpp[i & 1][val], dpp[(i - 1) & 1][val]);
        }
        for (int val = 1; val <= v[i].a; val++) {
            add(dpp[i & 1][v[i].a], dpp[(i - 1) & 1][val]);
        }
        for (int val = v[i].b + 1; val <= vmax; val++) {
            add(dpp[i & 1][val], dpp[(i - 1) & 1][val]);
        }
        for (int val = 1; val <= v[i].b; val++) {
            add(dpp[i & 1][v[i].b], dpp[(i - 1) & 1][val]);
        }
    }
    cout << ans;
    return 0;
}

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