QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#458570 | #8527. Power Divisions | ucup-team4361# | WA | 384ms | 153768kb | C++20 | 5.7kb | 2024-06-29 17:53:17 | 2024-06-29 17:58:23 |
Judging History
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'