test/library-checker/DataStructure/PredecessorProblem.test.cpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Problem: https://judge.yosupo.jp/problem/predecessor_problem

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/predecessor_problem"
#include <bits/stdc++.h>

#include "library/superstd/Set.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;
    Set<int> se;
    se.banpei();

    for (int i = 0; i < n; i++) {
        char c;
        std::cin >> c;
        if (c == '1')
            se.insert(i);
    }

    while (q--) {
        int c, k;
        std::cin >> c >> k;
        if (c == 0)
            se.insert(k);
        if (c == 1)
            se.erase(k);
        if (c == 2)
            std::cout << se.count(k) << "\n";
        if (c == 3) {
            int x = se.geq(k);
            std::cout << (x < n ? x : -1) << "\n";
        }
        if (c == 4) {
            int x = se.leq(k);
            std::cout << (x >= 0 ? x : -1) << "\n";
        }
    }
}

#line 1 "test/library-checker/DataStructure/PredecessorProblem.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/predecessor_problem"
#include <bits/stdc++.h>

#line 1 "library/superstd/Set.hpp"
template <typename T> struct Set : std::set<T> {
    using std::set<T>::size;
    using std::set<T>::begin;
    using std::set<T>::rbegin;
    using std::set<T>::insert;
    using std::set<T>::erase;
    using std::set<T>::lower_bound;
    using std::set<T>::upper_bound;

    T mn() const {
        assert(size());
        return *begin();
    }
    T mx() const {
        assert(size());
        return *rbegin();
    }

    T pop_front() {
        assert(size());
        T mn = *begin();
        erase(begin());
        return mn;
    }
    T pop_back() {
        assert(size());
        T mx = *rbegin();
        erase(mx);
        return mx;
    }

    T lt(const T &a) const {
        assert(mn() < a);
        if (mx() < a)
            return mx();
        return *--lower_bound(a);
    }
    T leq(const T &a) const {
        assert(mn() <= a);
        if (mx() <= a)
            return mx();
        return *--upper_bound(a);
    }
    T gt(const T &a) const {
        assert(mx() > a);
        return *upper_bound(a);
    }
    T geq(const T &a) {
        assert(mx() >= a);
        return *lower_bound(a);
    }

    Set() = default;
    Set(const std::vector<T> &v) {
        for (const auto &p : v)
            insert(p);
    }

    void scan(int n) {
        while (n--) {
            T a;
            std::cin >> a;
            insert(a);
        }
    }

    void banpei() {
        insert(std::numeric_limits<T>::max() / 2);
        insert(std::numeric_limits<T>::min() / 2);
    }
};
#line 5 "test/library-checker/DataStructure/PredecessorProblem.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;
    Set<int> se;
    se.banpei();

    for (int i = 0; i < n; i++) {
        char c;
        std::cin >> c;
        if (c == '1')
            se.insert(i);
    }

    while (q--) {
        int c, k;
        std::cin >> c >> k;
        if (c == 0)
            se.insert(k);
        if (c == 1)
            se.erase(k);
        if (c == 2)
            std::cout << se.count(k) << "\n";
        if (c == 3) {
            int x = se.geq(k);
            std::cout << (x < n ? x : -1) << "\n";
        }
        if (c == 4) {
            int x = se.leq(k);
            std::cout << (x >= 0 ? x : -1) << "\n";
        }
    }
}