Submission #1268628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268628		MisterReaper	Flooding Wall (BOI24_wall)	C++20	100 / 100	1536 ms	100016 KiB

Main

// File A.cpp created on 10.09.2025 at 12:56:52
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

template<typename T>
T power(T a, i64 b) {
    T res {1};
    while (b) {
        if (b & 1) {
            res *= a;
        }
        a *= a;
        b >>= 1;
    }
    return res;
}

constexpr int md = int(1E9) + 7;
struct MInt {
    int val;
    MInt() : val(0) {}
    template<typename T>
    MInt(T x) {
        if (-md <= x && x < md) {
            val = x; 
        } else {
            val = x % md;
        }
        if (val < 0) {
            val += md;
        }
    }
    int operator()() { return val; }
    MInt& operator+= (MInt rhs) {
        if ((val += rhs.val) >= md) {
            val -= md;
        }
        return *this;
    }
    MInt& operator-= (MInt rhs) {
        if ((val -= rhs.val) < 0) {
            val += md;
        }
        return *this;
    }
    MInt& operator*= (MInt rhs) {
        val = int(1LL * val * rhs.val % md);
        return *this;
    }
    MInt inv() {
        return power(*this, md - 2);
    }
    MInt& operator/= (MInt rhs) {
        return *this *= rhs.inv();
    }
    bool operator== (MInt rhs) const {
        return val == rhs.val;
    }
    bool operator!= (MInt rhs) const {
        return val != rhs.val;
    }
};
MInt operator+ (MInt lhs, MInt rhs) {
    return lhs += rhs;
}
MInt operator- (MInt lhs, MInt rhs) {
    return lhs -= rhs;
}
MInt operator* (MInt lhs, MInt rhs) {
    return lhs *= rhs;
}
MInt operator/ (MInt lhs, MInt rhs) {
    return lhs /= rhs;
}
std::ostream& operator<< (std::ostream& os, MInt x) {
    return os << x.val;
}
std::string to_string(MInt x) {
    return to_string(x.val);
}

using Z = MInt;

std::vector<Z> pow2;

struct node1 {
    int len;
    Z sum, suf;
    node1() {}
    node1(int x) : len(1), sum(x), suf(x) {
        assert(0 <= x && x <= 2);
    }
    void modify() {
        sum += 1;
        suf += 1;
    }
};
node1 operator+ (node1 lhs, node1 rhs) {
    node1 res;
    res.len = lhs.len + rhs.len;
    res.sum = lhs.sum * rhs.suf + pow2[lhs.len] * rhs.sum;
    res.suf = lhs.suf * rhs.suf;
    return res;
}

struct node2 {
    int len;
    Z sum, pre;
    node2() {}
    node2(int x) : len(1), sum(x), pre(x) {
        assert(0 <= x && x <= 2);
    }
    void modify() {
        sum += 1;
        pre += 1;
    }
};
node2 operator+ (node2 lhs, node2 rhs) {
    node2 res;
    res.len = lhs.len + rhs.len;
    res.sum = lhs.sum * pow2[rhs.len] + lhs.pre * rhs.sum;
    res.pre = lhs.pre * rhs.pre;
    return res;
}

struct node3 {
    int len;
    Z sum, val;
    node3() {}
    node3(int x) : len(1), sum(x), val(x) {
        assert(0 <= x && x <= 2);
    }
    void modify() {
        sum += 1;
        val += 1;
    }
};
node3 operator+ (node3 lhs, node3 rhs) {
    node3 res;
    res.len = lhs.len + rhs.len;
    res.sum = lhs.sum * rhs.val + lhs.val * rhs.sum;
    res.val = lhs.val * rhs.val;
    return res;
}

#define def int mid = (l + r) >> 1, lv = v + 1, rv = v + ((mid - l + 1) << 1)
template<typename T>
struct segtree {
    int n;
    std::vector<T> tree;
    segtree(int n_) : n(n_), tree(n << 1) {
        auto dfs = [&](auto&& self, int v, int l, int r) -> void {
            if (l == r) {
                tree[v] = 0;
                return;
            }
            def;
            self(self, lv, l, mid);
            self(self, rv, mid + 1, r);
            tree[v] = tree[lv] + tree[rv];
        };
        dfs(dfs, 0, 0, n - 1);
    }
    void modify(int v, int l, int r, int p) {
        if (l == r) {
            tree[v].modify();
            return;
        }
        def;
        if (p <= mid) {
            modify(lv, l, mid, p);
        } else {
            modify(rv, mid + 1, r, p);
        }
        tree[v] = tree[lv] + tree[rv];
    }
    void modify(int p) {
        modify(0, 0, n - 1, p);
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    std::cin >> N;

    std::vector<int> A(N), B(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }
    for (int i = 0; i < N; ++i) {
        std::cin >> B[i];
    }

    pow2.assign(N + 1, 0);
    pow2[0] = 1;
    for (int i = 1; i <= N; ++i) {
        pow2[i] = pow2[i - 1] * 2;
    }

    std::vector<int> nums {0};
    nums.insert(nums.end(), A.begin(), A.end());
    nums.insert(nums.end(), B.begin(), B.end());
    std::sort(nums.begin(), nums.end());
    nums.erase(std::unique(nums.begin(), nums.end()), nums.end());

    int n = int(nums.size());

    std::vector<std::vector<int>> ids(n);
    for (int i = 0; i < N; ++i) {
        ids[std::lower_bound(nums.begin(), nums.end(), A[i]) - nums.begin()].emplace_back(i);
        ids[std::lower_bound(nums.begin(), nums.end(), B[i]) - nums.begin()].emplace_back(i);
    }

    Z ans = 0;

    segtree<node1> seg1(N);
    for (int _ = 1; _ < n; ++_) {
        int x = nums[_];
        int dif = nums[_] - nums[_ - 1];
        for (auto i : ids[_ - 1]) {
            seg1.modify(i);
        }
        ans -= dif * seg1.tree[0].sum;
    }

    segtree<node2> seg2(N);
    for (int _ = 1; _ < n; ++_) {
        int x = nums[_];
        int dif = nums[_] - nums[_ - 1];
        for (auto i : ids[_ - 1]) {
            seg2.modify(i);
        }
        ans -= dif * seg2.tree[0].sum;
    }

    segtree<node3> seg3(N);
    for (int _ = 1; _ < n; ++_) {
        int x = nums[_];
        int dif = nums[_] - nums[_ - 1];
        for (auto i : ids[_ - 1]) {
            seg3.modify(i);
        }
        ans += dif * seg3.tree[0].sum;
    }

    // for (int _ = 1; _ < n; ++_) {
    //     int x = nums[_];
    //     int dif = nums[_] - nums[_ - 1];
    //     std::vector<Z> pre(N + 1), suf(N + 1);
    //     pre[0] = 1;
    //     for (int i = 0; i < N; ++i) {
    //         pre[i + 1] = pre[i] * ((A[i] < x) + (B[i] < x));
    //     }
    //     suf[N] = 1;
    //     for (int i = N - 1; i >= 0; --i) {
    //         suf[i] = suf[i + 1] * ((A[i] < x) + (B[i] < x));
    //     }
    //     Z res = 0;
    //     for (int i = 0; i < N; ++i) {
    //         res -= pow2[i] * suf[i];
    //         res -= pow2[N - i - 1] * pre[i + 1];
    //         res += pre[i] * suf[i];
    //         // res += pow2[N - 1] * ((A[i] < x) + (B[i] < x));
    //     }
    //     debug(x, res);
    //     ans += dif * res;
    // }

    for (int i = 0; i < N; ++i) {
        ans += pow2[N - 1] * (nums.back() - A[i]);
        ans += pow2[N - 1] * (nums.back() - B[i]);
    }

    std::cout << ans << '\n';

    return 0;
}

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