QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#458570#8527. Power Divisionsucup-team4361#WA 384ms153768kbC++205.7kb2024-06-29 17:53:172024-06-29 17:58:23

Judging History

你现在查看的是最新测评结果

  • [2024-06-29 17:58:23]
  • 评测
  • 测评结果:WA
  • 用时:384ms
  • 内存:153768kb
  • [2024-06-29 17:53:17]
  • 提交

answer

#include <bits/stdc++.h>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>

using std::bitset;
using std::cin, std::cout, std::endl, std::flush, std::cerr;
using std::min, std::max;
using std::pair, std::tuple;
using std::set, std::map, std::multiset;
using std::vector, std::array, std::queue, std::deque;
using std::views::iota, std::views::reverse;

template <class A> constexpr int sz(A&& a) {
    return int(std::size(std::forward<A>(a)));
}

struct CustomHash {
    size_t operator()(uint64_t x) const {
        static const uint64_t
            z = std::chrono::steady_clock::now().time_since_epoch().count(),
            c = uint64_t(4e18 * acos(0)) + 71;
        return __builtin_bswap64((x ^ z) * c);
    }
};

template <class K, class V, class Hash = CustomHash>
using HashMap = __gnu_pbds::gp_hash_table<K, V, Hash>;

using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
using usize = size_t;

template <class T> using Vec = std::vector<T>;

auto mt = std::mt19937_64(
    std::chrono::steady_clock::now().time_since_epoch().count());

struct HashInt {
    using H = HashInt;
    using T = unsigned long long;
    using L = __uint128_t;
    static constexpr T m = (T(1) << 61) - 1;
    static constexpr T m8 = m * 8;

    T v;
    HashInt() : v(0) {}
    HashInt(T a) : v(a % m * 8) {}
    T get() const { return v == m8 ? 0 : v; }

    H& operator+=(const H& o) {
        if (__builtin_uaddll_overflow(v, o.v, &v)) v -= m8;
        return *this;
    }
    H& operator-=(const H& o) {
        if (__builtin_usubll_overflow(v, o.v, &v)) v += m8;
        return *this;
    }

    H& operator*=(const H& o) {
        L t = L(v) * o.v;
        T x = T(t >> 67 << 3);
        T y = T(t << 61 >> 64);
        if (__builtin_uaddll_overflow(x, y, &v)) v -= m8;
        return *this;
    }

    friend H operator+(const H& a, const H& b) { return H(a) += b; }
    friend H operator-(const H& a, const H& b) { return H(a) -= b; }
    friend H operator*(const H& a, const H& b) { return H(a) *= b; }
    friend bool operator==(const H& a, const H& b) {
        return a.get() == b.get();
    }
};

constexpr bool DEBUG = false;

int main() {
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << std::fixed << std::setprecision(20);

    int N;
    if constexpr (!DEBUG) {
        cin >> N;
    } else {
        N = 300000;
    }

    using H = HashInt;
    constexpr int N2 = int(2e6);
    auto pow2 = Vec<H>(N2 + 1);
    pow2[0] = 1;
    for (int i : iota(0, N2)) {
        pow2[i + 1] = pow2[i] * H(2);
    }

    auto A = Vec<int>(N);
    if constexpr (!DEBUG) {
        for (int& a : A) cin >> a;
    } else {
        for (int i : iota(0, N)) {
            A[i] = mt() % 1000001;
        }
    }

    auto pref = Vec<H>(N + 1);
    pref[0] = 0;
    for (int i : iota(0, N)) {
        pref[i + 1] = pref[i] + pow2[A[i]];
    }
    auto val_to_idx = HashMap<uint64_t, int>();
    for (int i : iota(0, N + 1)) {
        val_to_idx[pref[i].get()] = i;
    }

    const int S = std::bit_ceil<uint32_t>(N);
    auto seg = Vec<pair<int, int>>(2 * S, {-1, -1});
    for (int i : iota(0, N)) {
        seg[S + i] = {A[i], i};
    }
    for (int a : iota(1, S) | reverse) {
        seg[a] = max(seg[2 * a + 0], seg[2 * a + 1]);
    }
    auto query = [&](int l, int r) -> int {
        assert(0 <= l);
        assert(l < r);
        assert(r <= N);
        auto res = pair<int, int>(-1, -1);
        for (int a = S + l, b = S + r; a < b; a /= 2, b /= 2) {
            if (a & 1) res = max(res, seg[a++]);
            if (b & 1) res = max(res, seg[--b]);
        }
        return res.second;
    };

    auto interesting = Vec<Vec<int>>(N);
    auto add_intersting = [&](int l, int r) -> void {
        assert(0 <= l && l < r && r <= N);
        interesting[l].push_back(r);
        if constexpr (DEBUG) {
            cerr << "interesting: " << l << ' ' << r << endl;
        }
    };

    auto lookup = [&](const H& h) -> std::optional<int> {
        if (auto it = val_to_idx.find(h.get()); it != val_to_idx.end()) {
            return it->second;
        } else {
            return std::nullopt;
        }
    };

    auto rec = [&](auto&& self, int l, int r) -> void {
        if (l >= r) return;
        int m = query(l, r);
        int a = A[m];
        int w = std::bit_width<uint32_t>(r - l);
        assert(l <= m);
        assert(m < r);

        {
            // Do something with left in [l, m+1) or right in [m+1, r+1)
            bool do_left = ((m + 1) - l < (r + 1) - (m + 1));
            for (int k : iota(a, a + w)) {
                if (do_left) {
                    for (int left : iota(l, m + 1)) {
                        if (auto right = lookup(pref[left] + pow2[k]); right) {
                            add_intersting(left, *right);
                        }
                    }
                } else {
                    for (int right : iota(m + 1, r + 1)) {
                        if (auto left = lookup(pref[right] - pow2[k]); left) {
                            add_intersting(*left, right);
                        }
                    }
                }
            }
        }

        self(self, l, m);
        self(self, m + 1, r);
    };
    rec(rec, 0, N);

    auto dp = Vec<uint64_t>(N + 1);
    constexpr uint32_t MOD = uint32_t(1e9) + 7;
    dp[0] = 1;
    auto seen = Vec<bool>(N + 1);
    for (int l : iota(0, N)) {
        uint32_t v = uint32_t(dp[l] % MOD);
        for (int r : interesting[l]) {
            if (!seen[r]) {
                seen[r] = true;
                dp[r] += v;
            }
        }
        for (int r : interesting[l]) {
            seen[r] = false;
        }
    }
    uint32_t ans = uint32_t(dp[N] % MOD);
    cout << ans << '\n';

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 18880kb

input:

5
2 0 0 1 1

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 9ms
memory: 18764kb

input:

1
0

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 5ms
memory: 18940kb

input:

2
1 1

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: 0
Accepted
time: 4ms
memory: 18892kb

input:

3
2 1 1

output:

3

result:

ok 1 number(s): "3"

Test #5:

score: 0
Accepted
time: 10ms
memory: 18780kb

input:

4
3 2 2 3

output:

4

result:

ok 1 number(s): "4"

Test #6:

score: 0
Accepted
time: 4ms
memory: 18760kb

input:

5
3 4 4 2 4

output:

2

result:

ok 1 number(s): "2"

Test #7:

score: 0
Accepted
time: 3ms
memory: 18960kb

input:

7
3 4 3 5 6 3 4

output:

6

result:

ok 1 number(s): "6"

Test #8:

score: 0
Accepted
time: 4ms
memory: 18744kb

input:

10
8 6 5 6 7 8 6 8 9 9

output:

4

result:

ok 1 number(s): "4"

Test #9:

score: 0
Accepted
time: 8ms
memory: 18716kb

input:

96
5 1 0 2 5 5 2 4 2 4 4 2 3 4 0 2 1 4 3 1 2 0 2 2 3 2 4 5 3 5 2 0 2 2 5 3 0 4 5 3 5 4 4 3 1 2 0 5 4 5 0 2 3 2 4 0 0 4 2 0 2 5 3 3 1 5 5 1 1 1 0 5 0 3 0 2 1 1 0 5 0 3 3 4 4 5 3 0 2 2 0 5 4 5 0 5

output:

11332014

result:

ok 1 number(s): "11332014"

Test #10:

score: 0
Accepted
time: 5ms
memory: 19092kb

input:

480
2 0 4 4 1 0 0 3 1 1 4 2 5 5 4 2 1 2 4 4 1 3 4 3 0 5 2 0 2 5 1 0 5 0 0 5 5 0 2 5 2 2 3 1 4 3 5 4 5 2 4 4 4 4 1 4 0 3 4 3 4 1 0 4 3 4 5 4 3 5 0 2 2 0 1 5 4 4 2 0 3 3 3 4 3 0 5 5 3 1 5 1 0 1 0 4 3 0 5 1 4 1 4 3 0 1 3 5 0 3 3 1 0 4 1 1 2 0 1 2 0 3 5 2 0 5 5 5 5 3 5 1 0 2 5 2 2 0 2 0 2 3 5 1 2 1 5 4 ...

output:

506782981

result:

ok 1 number(s): "506782981"

Test #11:

score: 0
Accepted
time: 5ms
memory: 19380kb

input:

2400
0 2 2 0 5 4 3 2 3 2 5 4 5 4 4 5 2 2 4 2 2 0 1 0 5 0 4 4 0 0 5 0 4 0 1 3 4 5 0 3 1 0 4 0 2 5 0 3 3 3 3 1 0 5 5 3 1 3 5 2 4 0 5 0 4 5 4 2 2 1 5 2 2 4 1 0 5 1 5 0 1 2 0 0 3 5 4 0 0 1 1 1 4 2 0 5 1 3 3 5 0 4 4 1 5 5 3 4 4 4 0 2 4 0 5 1 3 1 5 0 5 5 1 3 0 3 1 2 0 1 1 3 5 2 3 4 0 3 0 5 4 0 4 3 5 0 5 2...

output:

586570528

result:

ok 1 number(s): "586570528"

Test #12:

score: 0
Accepted
time: 8ms
memory: 21008kb

input:

12000
2 2 1 2 0 2 5 3 2 0 1 3 2 5 4 0 0 5 3 2 0 2 3 4 3 2 1 4 3 0 3 5 4 1 0 2 4 1 3 2 3 5 0 3 0 0 4 0 4 5 1 0 4 1 1 1 5 4 3 0 3 5 4 5 2 5 0 1 2 3 5 5 2 5 4 2 0 4 4 3 0 0 2 5 0 3 4 2 5 4 2 1 4 5 1 1 2 3 0 3 3 3 3 4 0 5 3 4 0 3 0 2 0 0 2 0 3 4 2 2 0 1 0 5 3 0 2 0 2 2 1 0 5 3 5 4 5 5 0 4 0 4 1 4 4 3 2 ...

output:

201653965

result:

ok 1 number(s): "201653965"

Test #13:

score: 0
Accepted
time: 48ms
memory: 28904kb

input:

60000
2 5 0 3 2 3 5 3 5 5 4 1 1 5 3 0 1 1 2 5 5 5 0 3 2 0 3 2 3 3 0 0 1 4 3 1 4 2 3 3 0 5 1 0 1 1 5 5 4 0 5 4 1 3 1 3 5 3 2 4 4 4 5 4 3 2 3 2 4 5 2 0 4 5 1 2 0 4 0 5 1 3 4 1 2 4 1 1 3 3 0 1 1 3 0 0 2 3 3 2 1 4 1 2 4 3 3 5 2 5 3 4 3 0 2 1 1 1 5 1 2 4 2 3 1 2 1 0 2 0 1 1 5 5 3 4 2 5 2 4 5 3 0 5 1 4 2 ...

output:

592751350

result:

ok 1 number(s): "592751350"

Test #14:

score: 0
Accepted
time: 300ms
memory: 82596kb

input:

300000
0 5 1 5 5 4 5 3 0 5 0 5 1 4 1 2 2 2 3 0 1 5 4 0 3 1 4 5 2 1 0 3 2 1 2 5 0 2 4 5 0 1 2 1 1 0 0 5 3 0 0 3 4 5 0 2 1 1 1 2 5 1 4 3 1 0 2 0 0 4 3 3 2 5 3 3 1 5 2 0 2 4 3 1 0 3 4 1 3 3 1 0 0 1 1 1 3 1 2 3 5 3 3 2 0 3 0 0 5 5 0 0 0 0 1 4 3 3 4 3 4 5 3 3 5 1 1 4 2 2 1 3 2 1 1 0 0 5 5 0 0 3 2 4 5 5 2...

output:

842503795

result:

ok 1 number(s): "842503795"

Test #15:

score: 0
Accepted
time: 330ms
memory: 153688kb

input:

300000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

432100269

result:

ok 1 number(s): "432100269"

Test #16:

score: 0
Accepted
time: 327ms
memory: 153768kb

input:

300000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 10000...

output:

432100269

result:

ok 1 number(s): "432100269"

Test #17:

score: 0
Accepted
time: 384ms
memory: 113352kb

input:

299995
1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 0 1 1 1 0 1 1 0 0 1 0 0 1 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 1 0 1 1 1 0 0 1 1 0 1 0 1 1 0 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 1 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 0 0...

output:

261818019

result:

ok 1 number(s): "261818019"

Test #18:

score: 0
Accepted
time: 284ms
memory: 78132kb

input:

299997
2 2 0 9 4 4 2 3 8 9 3 9 1 6 4 0 1 5 1 0 7 9 3 3 8 9 3 8 3 6 9 3 9 5 9 1 4 4 7 5 9 0 7 3 7 2 0 3 3 8 2 1 7 6 8 1 6 1 8 4 7 6 3 6 1 6 8 9 3 8 1 5 0 8 1 10 0 3 4 5 8 5 6 9 2 4 5 0 9 0 9 5 1 0 3 7 5 8 8 10 10 3 3 10 5 8 9 9 7 4 4 1 1 6 5 7 2 5 8 3 3 9 6 4 1 0 2 6 2 8 7 7 10 5 7 8 3 8 5 1 6 6 6 1 ...

output:

999738318

result:

ok 1 number(s): "999738318"

Test #19:

score: -100
Wrong Answer
time: 332ms
memory: 74268kb

input:

299999
97 34 33 30 15 73 31 69 60 63 79 87 78 13 49 58 23 38 91 28 70 70 14 98 56 59 81 66 29 21 10 51 94 32 41 98 16 48 67 62 55 5 17 81 30 91 39 93 73 74 46 74 41 99 19 10 0 16 72 95 84 40 97 17 76 10 42 50 66 97 4 30 71 74 46 5 75 87 55 82 38 94 14 82 49 10 23 21 19 99 52 100 71 29 64 73 54 88 2 ...

output:

437215032

result:

wrong answer 1st numbers differ - expected: '799664563', found: '437215032'