64-ary tree (yoshi_likes_e4/predproblem.test.cpp)

• View this file on GitHub
• Last update: 2024-11-17 18:50:27+07:00
• Problem: https://judge.yosupo.jp/problem/predecessor_problem

Code

// @brief 64-ary tree
#define PROBLEM "https://judge.yosupo.jp/problem/predecessor_problem"
#include <bits/stdc++.h>
using namespace std;
#ifndef yoshi_likes_e4
#define endl '\n'
#endif
#define problem ""
#define multitest 0
#define debug(x) cerr << #x << " = " << x << endl;
void init()
{
}
void Yoshi()
{
    const int B = 64;
    vector<vector<uint64_t>> tree;
    int n, old_n;
    cin >> n;
    old_n = n;
    while (n > 1)
    {
        // n = ceil(n/B)
        tree.push_back(vector<uint64_t>(n = (n + B - 1) / B));
    }
    int h = tree.size();
    // remember: tree[i][k][j] means that at the jth subtree of tree[i][k] has sum > 0
    // This is copied from noimi
    auto insert = [&tree](int i) {
        // log_B(n)
        for (auto &v : tree)
        {
            v[i / B] |= 1ULL << (i % B);
            i /= B;
        }
    };
    auto erase = [&tree](int i) {
        // log_B(n)
        for (auto &v : tree)
        {
            v[i / B] &= ~(1ULL << (i % B));
            i /= B;
            // do not erase the above subtrees if v[i] is not empty
            if (v[i])
                break;
        }
    };
    auto get = [&tree](int i) { return (tree[0][i / B] >> (i % B)) & 1; };
    auto next = [&tree, h](int i) {
        // log_B(n)
        for (int j = 0; j < h; j++)
        {
            // get the position in the current subtree
            if (i / B >= tree[j].size())
                break;
            int pos = i % B;
            uint64_t c = tree[j][i / B];
            // mask off the first pos bits
            c &= ~((1ULL << pos) - 1);
            i /= B;
            if (!c)
            {
                // jump to the next tree
                i++;
            }
            else
            {
                // if we find the first bit set, try to go deeper
                int i2 = i * B + __builtin_ctzll(c);
                for (int k = j - 1; k >= 0; k--)
                {
                    i2 *= B;
                    i2 += __builtin_ctzll(tree[k][i2 / B]);
                }
                return i2;
            }
        }
        return -1;
    };
    auto prev = [&tree, h](int i) {
        // log_B(n)
        for (int j = 0; j < h; j++)
        {
            // get the position in the current subtree
            int pos = i % B;
            uint64_t c = tree[j][i / B];
            // keep only the first pos bits
            if (pos != B - 1)
                c %= (1ULL << (pos + 1));
            i /= B;
            if (!c)
            {
                // jump to the PREVIOUS tree
                if (!i)
                    break;
                i--;
            }
            else
            {
                // if we find the last bit set, try to go deeper
                int i2 = i * B + 63 - __builtin_clzll(c);
                for (int k = j - 1; k >= 0; k--)
                {
                    i2 *= B;
                    i2 += 63 - __builtin_clzll(tree[k][i2 / B]);
                }
                return i2;
            }
        }
        return -1;
    };
    int q;
    cin >> q;
    string s;
    cin >> s;
    for (int i = 0; i < old_n; i++)
        if (s[i] - 48)
            insert(i);
    while (q--)
    {
        int t, x;
        cin >> t >> x;
        switch (t)
        {
        case 0: {
            insert(x);
            break;
        }
        case 1: {
            erase(x);
            break;
        }
        case 2: {
            cout << get(x) << endl;
            break;
        }
        case 3: {
            cout << next(x) << endl;
            break;
        }
        default: {
            cout << prev(x) << endl;
        }
        }
    }
}
signed main()
{
#ifndef yoshi_likes_e4
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(problem ".inp", "r"))
    {
        freopen(problem ".inp", "r", stdin);
        freopen(problem ".out", "w", stdout);
    }
#endif
    init();
    int t = 1;
#if multitest
    cin >> t;
#endif
    while (t--)
        Yoshi();
}

#line 1 "yoshi_likes_e4/predproblem.test.cpp"
// @brief 64-ary tree
#define PROBLEM "https://judge.yosupo.jp/problem/predecessor_problem"
#include <bits/stdc++.h>
using namespace std;
#ifndef yoshi_likes_e4
#define endl '\n'
#endif
#define problem ""
#define multitest 0
#define debug(x) cerr << #x << " = " << x << endl;
void init()
{
}
void Yoshi()
{
    const int B = 64;
    vector<vector<uint64_t>> tree;
    int n, old_n;
    cin >> n;
    old_n = n;
    while (n > 1)
    {
        // n = ceil(n/B)
        tree.push_back(vector<uint64_t>(n = (n + B - 1) / B));
    }
    int h = tree.size();
    // remember: tree[i][k][j] means that at the jth subtree of tree[i][k] has sum > 0
    // This is copied from noimi
    auto insert = [&tree](int i) {
        // log_B(n)
        for (auto &v : tree)
        {
            v[i / B] |= 1ULL << (i % B);
            i /= B;
        }
    };
    auto erase = [&tree](int i) {
        // log_B(n)
        for (auto &v : tree)
        {
            v[i / B] &= ~(1ULL << (i % B));
            i /= B;
            // do not erase the above subtrees if v[i] is not empty
            if (v[i])
                break;
        }
    };
    auto get = [&tree](int i) { return (tree[0][i / B] >> (i % B)) & 1; };
    auto next = [&tree, h](int i) {
        // log_B(n)
        for (int j = 0; j < h; j++)
        {
            // get the position in the current subtree
            if (i / B >= tree[j].size())
                break;
            int pos = i % B;
            uint64_t c = tree[j][i / B];
            // mask off the first pos bits
            c &= ~((1ULL << pos) - 1);
            i /= B;
            if (!c)
            {
                // jump to the next tree
                i++;
            }
            else
            {
                // if we find the first bit set, try to go deeper
                int i2 = i * B + __builtin_ctzll(c);
                for (int k = j - 1; k >= 0; k--)
                {
                    i2 *= B;
                    i2 += __builtin_ctzll(tree[k][i2 / B]);
                }
                return i2;
            }
        }
        return -1;
    };
    auto prev = [&tree, h](int i) {
        // log_B(n)
        for (int j = 0; j < h; j++)
        {
            // get the position in the current subtree
            int pos = i % B;
            uint64_t c = tree[j][i / B];
            // keep only the first pos bits
            if (pos != B - 1)
                c %= (1ULL << (pos + 1));
            i /= B;
            if (!c)
            {
                // jump to the PREVIOUS tree
                if (!i)
                    break;
                i--;
            }
            else
            {
                // if we find the last bit set, try to go deeper
                int i2 = i * B + 63 - __builtin_clzll(c);
                for (int k = j - 1; k >= 0; k--)
                {
                    i2 *= B;
                    i2 += 63 - __builtin_clzll(tree[k][i2 / B]);
                }
                return i2;
            }
        }
        return -1;
    };
    int q;
    cin >> q;
    string s;
    cin >> s;
    for (int i = 0; i < old_n; i++)
        if (s[i] - 48)
            insert(i);
    while (q--)
    {
        int t, x;
        cin >> t >> x;
        switch (t)
        {
        case 0: {
            insert(x);
            break;
        }
        case 1: {
            erase(x);
            break;
        }
        case 2: {
            cout << get(x) << endl;
            break;
        }
        case 3: {
            cout << next(x) << endl;
            break;
        }
        default: {
            cout << prev(x) << endl;
        }
        }
    }
}
signed main()
{
#ifndef yoshi_likes_e4
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(problem ".inp", "r"))
    {
        freopen(problem ".inp", "r", stdin);
        freopen(problem ".out", "w", stdout);
    }
#endif
    init();
    int t = 1;
#if multitest
    cin >> t;
#endif
    while (t--)
        Yoshi();
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	hack_00	AC	6 ms	4 MB
g++	max_all0_00	AC	160 ms	21 MB
g++	max_all0_01	AC	167 ms	21 MB
g++	max_all1_00	AC	187 ms	21 MB
g++	max_all1_01	AC	182 ms	21 MB
g++	max_query0_1_2_00	AC	183 ms	21 MB
g++	max_query0_1_2_01	AC	183 ms	21 MB
g++	max_random_00	AC	203 ms	21 MB
g++	max_random_01	AC	205 ms	21 MB
g++	max_sparse_00	AC	185 ms	21 MB
g++	max_sparse_01	AC	179 ms	21 MB
g++	medium_00	AC	16 ms	4 MB
g++	medium_01	AC	16 ms	4 MB
g++	medium_02	AC	16 ms	4 MB
g++	medium_03	AC	16 ms	4 MB
g++	medium_04	AC	16 ms	4 MB
g++	small_00	AC	15 ms	4 MB
g++	small_01	AC	15 ms	4 MB
g++	small_02	AC	15 ms	4 MB
g++	small_03	AC	15 ms	4 MB
g++	small_04	AC	16 ms	4 MB

Back to top page