QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#669828#8226. 堆操作练习题2peaneval_kala10 20ms97780kbC++2312.6kb2024-10-23 19:47:142024-10-23 19:47:14

Judging History

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

  • [2024-10-23 19:47:14]
  • 评测
  • 测评结果：10
  • 用时：20ms
  • 内存：97780kb
查看
  • [2024-10-23 19:47:14]
  • 提交

answer

#pragma GCC optimize(3, "unroll-loops", "no-stack-protector")
#define atsum(l, r) accumulate(l, r, 0)
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
template <typename T>
inline void chkmin(T &x, T y) {
    x = min(x, y);
}
template <typename T>
inline void chkmax(T &x, T y) {
    x = max(x, y);
}
namespace FastIO {
// ------------------------------
#define IN_HAS_NEG
#define OUT_HAS_NEG
#define CHK_EOF
#define DISABLE_MMAP
// ------------------------------
#if __cplusplus < 201400
#error Please use C++14 or higher.
#endif
#if __cplusplus > 201700
#define INLINE_V inline
#else
#define INLINE_V
#endif
#if (defined(LOCAL) || defined(_WIN32)) && !defined(DISABLE_MMAP)
#define DISABLE_MMAP
#endif
#ifndef DISABLE_MMAP
#include <sys/mman.h>
#endif
#ifdef LOCAL
inline char gc() { return getchar(); }
inline void pc(char c) { putchar(c); }
#else
#ifdef DISABLE_MMAP
INLINE_V constexpr int _READ_SIZE = 1 << 18;
INLINE_V static char _read_buffer[_READ_SIZE], *_read_ptr = nullptr,
                                               *_read_ptr_end = nullptr;
inline char gc() {
    if (__builtin_expect(_read_ptr == _read_ptr_end, false)) {
        _read_ptr = _read_buffer;
        _read_ptr_end =
            _read_buffer + fread(_read_buffer, 1, _READ_SIZE, stdin);
#ifdef CHK_EOF
        if (__builtin_expect(_read_ptr == _read_ptr_end, false)) return EOF;
#endif
    }
    return *_read_ptr++;
}
#else
INLINE_V static const char *_read_ptr =
    (const char *)mmap(nullptr, INT_MAX, 1, 2, 0, 0);
inline char gc() { return *_read_ptr++; }
#endif
INLINE_V constexpr int _WRITE_SIZE = 1 << 18;
INLINE_V static char _write_buffer[_WRITE_SIZE], *_write_ptr = _write_buffer;
inline void pc(char c) {
    *_write_ptr++ = c;
    if (__builtin_expect(_write_buffer + _WRITE_SIZE == _write_ptr, false)) {
        fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout);
        _write_ptr = _write_buffer;
    }
}
INLINE_V struct _auto_flush {
    ~_auto_flush() {
        fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout);
    }
} _auto_flush;
#endif
#ifdef CHK_EOF
inline bool _isdigit(char c) { return (c & 16) && c != EOF; }
inline bool _isgraph(char c) { return c > 32 && c != EOF; }
#else
inline bool _isdigit(char c) { return c & 16; }
inline bool _isgraph(char c) { return c > 32; }
#endif
template <class T>
INLINE_V constexpr bool _is_integer = numeric_limits<T>::is_integer;
template <class T>
INLINE_V constexpr bool _is_signed = numeric_limits<T>::is_signed;
template <class T>
INLINE_V constexpr bool _is_unsigned = _is_integer<T> && !_is_signed<T>;
template <>
INLINE_V constexpr bool _is_integer<__int128> = true;
template <>
INLINE_V constexpr bool _is_integer<__uint128_t> = true;
template <>
INLINE_V constexpr bool _is_signed<__int128> = true;
template <>
INLINE_V constexpr bool _is_unsigned<__uint128_t> = true;
#undef INLINE_V
inline void read(char &c) {
    do c = gc();
    while (!_isgraph(c));
}
inline void read_cstr(char *s) {
    char c = gc();
    while (!_isgraph(c)) c = gc();
    while (_isgraph(c)) *s++ = c, c = gc();
    *s = 0;
}
inline void read(string &s) {
    char c = gc();
    s.clear();
    while (!_isgraph(c)) c = gc();
    while (_isgraph(c)) s.push_back(c), c = gc();
}
#ifdef IN_HAS_NEG
template <class T, enable_if_t<_is_signed<T>, int> = 0>
inline void read(T &x) {
    char c = gc();
    bool f = true;
    x = 0;
    while (!_isdigit(c)) {
        if (c == 45) f = false;
        c = gc();
    }
    if (f)
        while (_isdigit(c)) x = x * 10 + (c & 15), c = gc();
    else
        while (_isdigit(c)) x = x * 10 - (c & 15), c = gc();
}
template <class T, enable_if_t<_is_unsigned<T>, int> = 0>
#else
template <class T, enable_if_t<_is_integer<T>, int> = 0>
#endif
inline void read(T &x) {
    char c = gc();
    while (!_isdigit(c)) c = gc();
    x = 0;
    while (_isdigit(c)) x = x * 10 + (c & 15), c = gc();
}
inline void write(char c) { pc(c); }
inline void write_cstr(const char *s) {
    while (*s) pc(*s++);
}
inline void write(const string &s) {
    for (char c : s) pc(c);
}
#ifdef OUT_HAS_NEG
template <class T, enable_if_t<_is_signed<T>, int> = 0>
inline void write(T x) {
    char buffer[numeric_limits<T>::digits10 + 1];
    int digits = 0;
    if (x >= 0) do
            buffer[digits++] = (x % 10) | 48, x /= 10;
        while (x);
    else {
        pc(45);
        do buffer[digits++] = -(x % 10) | 48, x /= 10;
        while (x);
    }
    while (digits) pc(buffer[--digits]);
}
template <class T, enable_if_t<_is_unsigned<T>, int> = 0>
#else
template <class T, enable_if_t<_is_integer<T>, int> = 0>
#endif
inline void write(T x) {
    char buffer[numeric_limits<T>::digits10 + 1];
    int digits = 0;
    do buffer[digits++] = (x % 10) | 48, x /= 10;
    while (x);
    while (digits) pc(buffer[--digits]);
}
template <int N>
struct _tuple_io_helper {
    template <class... T>
    static inline void _read(tuple<T...> &x) {
        _tuple_io_helper<N - 1>::_read(x), read(get<N - 1>(x));
    }
    template <class... T>
    static inline void _write(const tuple<T...> &x) {
        _tuple_io_helper<N - 1>::_write(x), pc(32), write(get<N - 1>(x));
    }
};
template <>
struct _tuple_io_helper<1> {
    template <class... T>
    static inline void _read(tuple<T...> &x) {
        read(get<0>(x));
    }
    template <class... T>
    static inline void _write(const tuple<T...> &x) {
        write(get<0>(x));
    }
};
template <class... T>
inline void read(tuple<T...> &x) {
    _tuple_io_helper<sizeof...(T)>::_read(x);
}
template <class... T>
inline void write(const tuple<T...> &x) {
    _tuple_io_helper<sizeof...(T)>::_write(x);
}
template <class T1, class T2>
inline void read(pair<T1, T2> &x) {
    read(x.first), read(x.second);
}
template <class T1, class T2>
inline void write(const pair<T1, T2> &x) {
    write(x.first), pc(32), write(x.second);
}
template <class T1, class... T2>
inline void read(T1 &x, T2 &...y) {
    read(x), read(y...);
}
template <class... T>
inline void read_cstr(char *x, T *...y) {
    read_cstr(x), read_cstr(y...);
}
template <class T1, class... T2>
inline void write(const T1 &x, const T2 &...y) {
    write(x), write(y...);
}
template <class... T>
inline void write_cstr(const char *x, const T *...y) {
    write_cstr(x), write_cstr(y...);
}
template <class T>
inline void print(const T &x) {
    write(x);
}
inline void print_cstr(const char *x) { write_cstr(x); }
template <class T1, class... T2>
inline void print(const T1 &x, const T2 &...y) {
    print(x), pc(32), print(y...);
}
template <class... T>
inline void print_cstr(const char *x, const T *...y) {
    print_cstr(x), pc(32), print_cstr(y...);
}
inline void println() { pc(10); }
inline void println_cstr() { pc(10); }
template <class... T>
inline void println(const T &...x) {
    print(x...), pc(10);
}
template <class... T>
inline void println_cstr(const T *...x) {
    print_cstr(x...), pc(10);
}
}  // namespace FastIO
using namespace FastIO;
template <typename T>
inline void clear(T &x) {
    T y;
    swap(x, y);
}
template <uint32_t mod = 1000000007>
class Modint {
   private:
    static constexpr uint32_t get_r() {
        uint32_t ret = mod;
        for (int i = 0; i < 4; i++) ret *= 2 - mod * ret;
        return ret;
    }
    static constexpr uint32_t r = get_r();
    static constexpr uint32_t n2 = -uint64_t(mod) % mod;
    static_assert(r * mod == 1 && mod < (1 << 30) && mod & 1);
    uint32_t data;

   public:
    constexpr Modint() : data(0) {}
    template <class int_t>
    constexpr Modint(const int_t x)
        : data(reduce(
              uint64_t((sizeof(int_t) < sizeof(uint32_t) ? x : x % int_t(mod)) +
                       mod) *
              n2)){};
    static constexpr uint32_t reduce(const uint64_t x) {
        return (x + uint64_t(uint32_t(x) * (-r)) * mod) >> 32;
    }
    constexpr Modint &operator+=(const Modint &r) {
        if (int32_t(data += r.data - 2 * mod) < 0) {
            data += 2 * mod;
        }
        return *this;
    }
    constexpr Modint &operator-=(const Modint &r) {
        if (int32_t(data -= r.data) < 0) {
            data += 2 * mod;
        }
        return *this;
    }
    constexpr Modint &operator*=(const Modint &r) {
        return data = reduce((uint64_t)data * r.data), *this;
    }
    constexpr Modint &operator/=(const Modint &r) { return *this *= r.inv(); }
    constexpr friend Modint operator+(Modint l, const Modint &r) {
        return l += r;
    }
    constexpr friend Modint operator-(Modint l, const Modint &r) {
        return l -= r;
    }
    constexpr friend Modint operator*(Modint l, const Modint &r) {
        return l *= r;
    }
    constexpr friend Modint operator/(Modint l, const Modint &r) {
        return l /= r;
    }
    constexpr friend bool operator==(Modint l, const Modint &r) {
        return l.value() == r.value();
    }
    constexpr Modint operator-() const { return Modint() - Modint(*this); }
    template <class int_t>
    constexpr Modint pow(int_t r) const {
        Modint res(1), w(*this);
        for (; r; r >>= 1, w *= w)
            if (r & 1) res *= w;
        return res;
    }
    constexpr Modint inv() const { return pow(mod - 2); }
    constexpr uint32_t value() const {
        uint32_t res = reduce(data);
        return res >= mod ? res - mod : res;
    }
};
using modint = Modint<>;
const int N = 1 << 20;
struct Bit {
    int len;
    vector<int> f;
    inline void resize(int _len) { len = _len, f.resize(len); }
    inline void update(int u, int v) {
        ++u;
        while (u <= len) f[u - 1] += v, u += u & -u;
    }
    inline int query(int u) {
        int ans = 0;
        ++u;
        while (u) ans += f[u - 1], u -= u & -u;
        return ans;
    }
} f[N];

int n, posx[N], w[N], w2[N];
bool vis[N];
modint len = 1;
vector<int> vec[N], qwq[N], pos[N], pos2[N];
inline void cpy(int u, int dep) {
    if (!dep) return;
    w2[u] = w[u];
    cpy(u << 1, dep - 1), cpy(u << 1 | 1, dep - 1);
}
inline int pushup(int u) {
    if (!w2[u << 1] && !w2[u << 1 | 1]) return u;
    if (w2[u << 1] > w2[u << 1 | 1])
        return swap(w2[u], w2[u << 1]), pushup(u << 1);
    else
        return swap(w2[u], w2[u << 1 | 1]), pushup(u << 1 | 1);
}
multiset<int> s[N];
int mx[N];
vector<bool> used[N];
void build(int u, int dep) {
    if (!dep) return;
    mx[u] = u + (1 << dep) - 2;
    cpy(u, dep);
    int cc = 0;
    used[u].resize(1 << dep);
    pos[u].resize(1 << dep);
    f[u].resize(1 << dep);
    pos2[u].resize(1 << dep);
    while (w2[u]) {
        qwq[u].push_back(w2[u]);
        int t = 0;
        w2[u] = 0;
        vec[u].push_back(t = pushup(u));
        pos[u][t - u] = cc++;
    }
    pos2[u].resize(1 << dep);
    cc = 0;
    for (int v : qwq[u]) pos2[u][pos[u][posx[v] - u]] = cc++;
    s[u].insert(1 << dep);
    qwq[u].push_back(0);
    f[u].resize(1 << dep);
    build(u << 1, dep - 1), build(u << 1 | 1, dep - 1);
}
inline modint calc(int u, int val) {
    int pu = posx[val];
    if (pu < u || pu > mx[u]) return 0;
    int px = pos2[u][pos[u][pu - u]];
    if (px > *s[u].begin()) return 0;
    if (px != *s[u].begin() && !used[u][px]) return 0;
    modint ans = 0;
    return modint(2).pow(f[u].query(px)).inv() * len;
}
int main() {
    read(n);
    for (int i = 1; i < (1 << n); i++) read(w[i]), posx[w[i]] = i;
    build(1, n);
    int q;
    read(q);
    while (q--) {
        int op, x, y;
        read(op, x, y);
        if (op == 1) {
            // assert(y == 1);
            if (y == 1) {
                int px = x;
                while (x) ::s[x].insert(pos[x][px - x]), x >>= 1;
            } else {
                int px = x;
                len *= 2;
                while (x) f[x].update(pos[x][px - x], 1), used[x][pos[x][px - x]] = 1, x >>= 1;
            }
        } else if (op == 2) {
            // assert(y == 1);
            if (y == 1) {
                int px = x;
                while (x) ::s[x].erase(pos[x][px - x]), x >>= 1;
            } else {
                int px = x;
                len /= 2;
                while (x) f[x].update(pos[x][px - x], -1), used[x][pos[x][px - x]] = 0, x >>= 1;
            }
            vis[x] = 0;
        } else {
            println(calc(x, y).value());
        }
    }
    return 0;
}
/*
2
3 1 2
4
3 1 3
1 2 1
3 1 3
3 1 2
*/
源文件, 语言: C++23

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 20ms
memory: 97780kb

input:

2
3 2 1
50
3 3 1
1 1 2
1 2 1
2 2 1
1 2 2
2 1 2
1 1 1
1 3 2
2 1 1
2 2 2
3 1 2
3 1 3
2 3 2
1 3 2
1 2 2
2 2 2
1 2 1
1 1 2
3 1 1
2 1 2
1 1 1
2 1 1
3 1 2
3 1 3
2 3 2
1 3 2
2 2 1
1 2 1
1 1 1
3 1 2
2 1 1
1 1 1
3 3 1
2 1 1
2 3 2
1 3 1
2 3 1
1 1 2
3 1 3
2 1 2
3 3 1
3 1 3
3 1 1
3 1 1
1 3 2
1 1 1
2 1 1
3 1 1
2...

output:

0
1
0
0
0
2
0
1
2
0
1
0
0
0
0

result:

ok 15 numbers

Test #2:

score: 10
Accepted
time: 20ms
memory: 94864kb

input:

2
3 1 2
50
1 2 2
3 3 2
2 2 2
1 3 1
1 1 1
3 3 2
2 1 1
3 1 3
2 3 1
1 3 1
1 1 1
1 2 2
2 1 1
3 1 3
2 3 1
2 2 2
1 1 2
1 2 1
1 3 1
2 1 2
3 3 2
1 1 1
2 3 1
1 3 2
2 3 2
1 3 1
2 2 1
3 3 2
3 1 1
2 3 1
2 1 1
1 3 1
2 3 1
3 1 3
3 1 3
3 1 3
1 1 1
2 1 1
3 1 2
1 2 1
3 1 1
3 3 2
3 1 3
2 2 1
1 1 1
2 1 1
1 2 1
1 1 2
2...

output:

0
1
1
2
1
1
0
0
0
0
0
0
0
0
0

result:

ok 15 numbers

Subtask #2:

score: 0
Runtime Error

Dependency #1:

100%
Accepted

Test #3:

score: 0
Runtime Error

input:

4
15 14 13 9 10 11 12 2 7 4 5 1 6 8 3
500
3 1 15
3 1 13
1 9 1
1 6 2
1 15 2
1 14 1
1 10 2
1 5 2
3 12 1
1 1 1
1 4 1
3 6 6
3 10 4
1 3 1
3 13 6
1 11 2
2 4 1
2 14 1
3 6 6
3 1 11
3 1 14
3 2 4
2 6 2
2 15 2
3 1 9
3 7 12
1 13 2
2 9 1
2 5 2
3 14 8
1 15 2
1 12 1
3 11 5
1 5 2
3 1 15
3 5 10
3 1 11
1 14 1
2 13 2
...

output:

result:

Subtask #3:

score: 0
Runtime Error

Test #5:

score: 0
Runtime Error

input:

9
511 509 510 504 507 505 508 501 503 506 502 494 500 499 493 473 483 495 475 491 497 461 487 490 489 498 496 478 485 480 488 378 469 482 477 462 448 422 470 424 467 421 492 439 454 484 451 376 385 458 464 463 486 411 472 449 474 459 468 479 413 457 455 371 315 432 437 466 453 476 418 433 363 434 38...

output:

result:

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #3:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%
English 繁體中文 简体中文

服务器时间: 2024-12-11 21:37:56 | 开源项目