test/data_structure/Predecessor_Problem.test.cpp

• View this file on GitHub
• Last update: 2023-07-17 14:12:40+09:00
• Problem: https://judge.yosupo.jp/problem/predecessor_problem

Depends on

• data_structure/predecessor_set.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/predecessor_problem"

#include <iostream>
#include <string>

#include "../../data_structure/predecessor_set.hpp"

int main() {
    int n, q;
    std::cin >> n >> q;
    std::string t;
    std::cin >> t;
    ebi::predecessor_set set;
    for (int i = 0; i < n; i++) {
        if (t[i] == '1') {
            set.insert(i);
        }
    }
    while (q--) {
        int flag, k;
        std::cin >> flag >> k;
        if (flag == 0) {
            set.insert(k);
        } else if (flag == 1) {
            set.erase(k);
        } else if (flag == 2) {
            std::cout << (set.find(k) ? 1 : 0) << '\n';
        } else if (flag == 3) {
            std::cout << set.find_next(k) << '\n';
        } else {
            std::cout << set.find_prev(k) << '\n';
        }
    }
}

#line 1 "test/data_structure/Predecessor_Problem.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/predecessor_problem"

#include <iostream>
#include <string>

#line 2 "data_structure/predecessor_set.hpp"

#include <set>

namespace ebi {

struct predecessor_set {
  public:
    predecessor_set() = default;

    void insert(int k) {
        set.insert(k);
    }

    void erase(int k) {
        set.erase(k);
    }

    bool find(int k) const {
        return set.find(k) != set.end();
    }

    int find_next(int k) const {
        auto itr = set.lower_bound(k);
        return itr == set.end() ? -1 : *itr;
    }

    int find_prev(int k) const {
        auto itr = set.upper_bound(k);
        return itr == set.begin() ? -1 : *(--itr);
    }

  private:
    std::set<int> set;
};

}  // namespace ebi
#line 7 "test/data_structure/Predecessor_Problem.test.cpp"

int main() {
    int n, q;
    std::cin >> n >> q;
    std::string t;
    std::cin >> t;
    ebi::predecessor_set set;
    for (int i = 0; i < n; i++) {
        if (t[i] == '1') {
            set.insert(i);
        }
    }
    while (q--) {
        int flag, k;
        std::cin >> flag >> k;
        if (flag == 0) {
            set.insert(k);
        } else if (flag == 1) {
            set.erase(k);
        } else if (flag == 2) {
            std::cout << (set.find(k) ? 1 : 0) << '\n';
        } else if (flag == 3) {
            std::cout << set.find_next(k) << '\n';
        } else {
            std::cout << set.find_prev(k) << '\n';
        }
    }
}

Back to top page