test/data_structures/ordered_set.test.cpp

• View this file on GitHub
• Last update: 2026-02-06 17:15:57+09:00
• Problem: https://judge.yosupo.jp/problem/ordered_set

Depends on

• data_structures/ordered_set.hpp

Code

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

#include "data_structures/ordered_set.hpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N, Q;
    std::cin >> N >> Q;
    ordered_set<int> s;
    for (auto i = 0; i < N; ++i) {
        int a;
        std::cin >> a;
        s.insert(a);
    }
    for (auto i = 0; i < Q; ++i) {
        int t, x;
        std::cin >> t >> x;
        if (t == 0) {
            s.insert(x);
        } else if (t == 1) {
            s.erase(x);
        } else if (t == 2) {
            auto it = s.find_by_order(x - 1);
            std::cout << (it != s.end() ? *it : -1) << "\n";
        } else if (t == 3) {
            std::cout << s.order_of_key(x + 1) << "\n";
        } else if (t == 4) {
            auto it = s.upper_bound(x);
            std::cout << (it != s.begin() ? *std::prev(it) : -1) << "\n";
        } else if (t == 5) {
            auto it = s.lower_bound(x);
            std::cout << (it != s.end() ? *it : -1) << "\n";
        }
    }
}

#line 1 "test/data_structures/ordered_set.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/ordered_set"

#line 1 "data_structures/ordered_set.hpp"



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

template <typename T>
using ordered_set =
    __gnu_pbds::tree<T, __gnu_pbds::null_type, std::less<T>, __gnu_pbds::rb_tree_tag,
                     __gnu_pbds::tree_order_statistics_node_update>;


#line 4 "test/data_structures/ordered_set.test.cpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N, Q;
    std::cin >> N >> Q;
    ordered_set<int> s;
    for (auto i = 0; i < N; ++i) {
        int a;
        std::cin >> a;
        s.insert(a);
    }
    for (auto i = 0; i < Q; ++i) {
        int t, x;
        std::cin >> t >> x;
        if (t == 0) {
            s.insert(x);
        } else if (t == 1) {
            s.erase(x);
        } else if (t == 2) {
            auto it = s.find_by_order(x - 1);
            std::cout << (it != s.end() ? *it : -1) << "\n";
        } else if (t == 3) {
            std::cout << s.order_of_key(x + 1) << "\n";
        } else if (t == 4) {
            auto it = s.upper_bound(x);
            std::cout << (it != s.begin() ? *std::prev(it) : -1) << "\n";
        } else if (t == 5) {
            auto it = s.lower_bound(x);
            std::cout << (it != s.end() ? *it : -1) << "\n";
        }
    }
}

Back to top page