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

• View this file on GitHub
• Last update: 2025-03-18 20:36:59+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

#define 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"
#define 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;
}

Back to top page