verify/verify-yosupo-ds/yosupo-pbds.test.cpp

• View this file on GitHub
• Last update: 2025-03-29 17:57:48+08:00
• Problem: https://judge.yosupo.jp/problem/predecessor_problem

Depends on

• src/alfred/config/io-sync-off.hpp
• src/alfred/data_structure/pbds-balance-tree.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/predecessor_problem

#include "../../src/alfred/config/io-sync-off.hpp"
#include "../../src/alfred/data_structure/pbds-balance-tree.hpp"
#include <iostream>

std::string T;
int n, q, opt, x;
BalanceTree<int, std::less<int>> tr;

int main(int argc, char const *argv[]) {
    optimizeIO();
    std::cin >> n >> q >> T;
    for (int i = 0; i < n; i++) {
        if (T[i] == '1') tr.insert(i);
    }

    while (q--) {
        std::cin >> opt >> x;
        if (opt == 0) {
            tr.insert(x);
        } else if (opt == 1) {
            if (tr.find(x) != tr.end()) {
                tr.erase(x);
            }
        } else if (opt == 2) {
            std::cout << (tr.find(x) != tr.end()) << '\n';
        } else if (opt == 3) {
            auto it = tr.lower_bound(x);
            std::cout << (it == tr.end() ? -1 : *it) << '\n';
        } else {
            auto it = tr.upper_bound(x);
            std::cout << (it == tr.begin() ? -1 : *(--it)) << '\n';
        }
    }

    return 0;
}

#line 1 "verify/verify-yosupo-ds/yosupo-pbds.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/predecessor_problem

#line 1 "src/alfred/config/io-sync-off.hpp"
#include <bits/stdc++.h>

inline void optimizeIO(void) {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL), std::cout.tie(NULL);
}
#line 1 "src/alfred/data_structure/pbds-balance-tree.hpp"



#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// TreeTag can also be __gnu_pbds::splay_tree_tag
template <class T, class Cmp = std::less_equal<int>, class TreeTag = __gnu_pbds::rb_tree_tag>
using BalanceTree = __gnu_pbds::tree<T, __gnu_pbds::null_type, Cmp, TreeTag, __gnu_pbds::tree_order_statistics_node_update>;


#line 6 "verify/verify-yosupo-ds/yosupo-pbds.test.cpp"

std::string T;
int n, q, opt, x;
BalanceTree<int, std::less<int>> tr;

int main(int argc, char const *argv[]) {
    optimizeIO();
    std::cin >> n >> q >> T;
    for (int i = 0; i < n; i++) {
        if (T[i] == '1') tr.insert(i);
    }

    while (q--) {
        std::cin >> opt >> x;
        if (opt == 0) {
            tr.insert(x);
        } else if (opt == 1) {
            if (tr.find(x) != tr.end()) {
                tr.erase(x);
            }
        } else if (opt == 2) {
            std::cout << (tr.find(x) != tr.end()) << '\n';
        } else if (opt == 3) {
            auto it = tr.lower_bound(x);
            std::cout << (it == tr.end() ? -1 : *it) << '\n';
        } else {
            auto it = tr.upper_bound(x);
            std::cout << (it == tr.begin() ? -1 : *(--it)) << '\n';
        }
    }

    return 0;
}

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	157 ms	20 MB
g++	max_all0_01	AC	160 ms	20 MB
g++	max_all1_00	AC	10394 ms	482 MB
g++	max_all1_01	AC	10304 ms	482 MB
g++	max_query0_1_2_00	AC	5197 ms	248 MB
g++	max_query0_1_2_01	AC	5128 ms	248 MB
g++	max_random_00	AC	5152 ms	248 MB
g++	max_random_01	AC	5181 ms	248 MB
g++	max_sparse_00	AC	171 ms	20 MB
g++	max_sparse_01	AC	176 ms	20 MB
g++	medium_00	AC	25 ms	4 MB
g++	medium_01	AC	24 ms	4 MB
g++	medium_02	AC	25 ms	4 MB
g++	medium_03	AC	25 ms	4 MB
g++	medium_04	AC	25 ms	4 MB
g++	small_00	AC	19 ms	4 MB
g++	small_01	AC	19 ms	4 MB
g++	small_02	AC	19 ms	4 MB
g++	small_03	AC	19 ms	4 MB
g++	small_04	AC	19 ms	4 MB

Back to top page