QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#458601#8527. Power Divisionsucup-team4361#WA 335ms154024kbC++205.7kb2024-06-29 17:58:152024-06-29 18:01:09

Judging History

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

  • [2024-06-29 18:01:09]
  • 评测
  • 测评结果:WA
  • 用时:335ms
  • 内存:154024kb
  • [2024-06-29 17:58:15]
  • 提交

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;
}

详细

Test #1:

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

input:

5
2 0 0 1 1

output:

6

result:

ok 1 number(s): "6"

Test #2:

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

input:

1
0

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

2
1 1

output:

2

result:

ok 1 number(s): "2"

Test #4:

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

input:

3
2 1 1

output:

3

result:

ok 1 number(s): "3"

Test #5:

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

input:

4
3 2 2 3

output:

4

result:

ok 1 number(s): "4"

Test #6:

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

input:

5
3 4 4 2 4

output:

2

result:

ok 1 number(s): "2"

Test #7:

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

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: 18964kb

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: 4ms
memory: 18896kb

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: 4ms
memory: 18856kb

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: 4ms
memory: 19496kb

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: 12ms
memory: 21132kb

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: 42ms
memory: 28980kb

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: 277ms
memory: 82620kb

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: 262ms
memory: 153756kb

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: 287ms
memory: 154024kb

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: 335ms
memory: 113460kb

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: 212ms
memory: 78104kb

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: 250ms
memory: 74416kb

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'