Ordered Set (verify/structures/fenwick/ordered_set.test.cpp)

• View this file on GitHub
• Last update: 2026-04-22 09:17:08-07:00
• Problem: https://judge.yosupo.jp/problem/ordered_set

Depends on

• cp-algo/structures/bit_array.hpp
• cp-algo/structures/fenwick.hpp
• cp-algo/structures/fenwick_set.hpp
• cp-algo/util/big_alloc.hpp
• cp-algo/util/bit.hpp
• cp-algo/util/compress_coords.hpp
• cp-algo/util/simd.hpp
• cp-algo/util/sort.hpp

Code

// @brief Ordered Set
#define PROBLEM "https://judge.yosupo.jp/problem/ordered_set"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
//#include "blazingio/blazingio.min.hpp"
#include "cp-algo/structures/fenwick_set.hpp"
#include "cp-algo/util/compress_coords.hpp"

using namespace std;
using cp_algo::structures::fenwick_set;

void solve() {
    int n, q;
    cin >> n >> q;
    cp_algo::big_vector<int> a(n, 0);
    cp_algo::big_vector<reference_wrapper<int>> coords;
    for(auto &it: a) {
        cin >> it;
        coords.push_back(ref(it));
    }
    cp_algo::big_vector<pair<int, int>> queries(q, pair{0, 0});
    for(auto &[t, x]: queries) {
        cin >> t >> x;
        if(t != 2) {
            coords.push_back(ref(x));
        }
    }
    auto values = cp_algo::compress_coords(coords);
    const int maxc = 1e6;
    fenwick_set<maxc> me(a);
    for(auto [t, x]: queries) {
        if(t == 0) {
            me.insert(x);
        } else if(t == 1) {
            me.erase(x);
        } else if(t == 2) {
            auto res = (int)me.find_by_order(x-1);
            cout << (res == -1 ? -1 : values[res]) << '\n';
        } else if(t == 3) {
            cout << me.order_of_key(x+1) << '\n';
        } else if(t == 4) {
            auto res = (int)me.pre_upper_bound(x);
            cout << (res == -1 ? -1 : values[res]) << '\n';
        } else if(t == 5) {
            auto res = (int)me.lower_bound(x);
            cout << (res == -1 ? -1 : values[res]) << '\n';
        }
    }
}

signed main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    while(t--) {
        solve();
    }
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 290, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/languages/cplusplus.py", line 243, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/languages/cplusplus_bundle.py", line 322, in update
    assert len(lines) == len(uncommented_lines)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
AssertionError

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	2 ms	4 MB
g++	example_01	AC	2 ms	4 MB
g++	max_random_00	AC	81 ms	17 MB
g++	max_random_01	AC	84 ms	17 MB
g++	max_random_02	AC	59 ms	18 MB
g++	max_random_03	AC	57 ms	18 MB
g++	max_random_04	AC	74 ms	8 MB
g++	max_random_05	AC	79 ms	18 MB
g++	max_random_06	AC	87 ms	18 MB
g++	max_random_07	AC	87 ms	18 MB
g++	max_random_08	AC	88 ms	17 MB
g++	max_random_09	AC	90 ms	17 MB
g++	max_random_10	AC	59 ms	18 MB
g++	max_random_11	AC	56 ms	18 MB
g++	max_random_12	AC	74 ms	8 MB
g++	max_random_13	AC	83 ms	18 MB
g++	max_random_14	AC	98 ms	18 MB
g++	max_random_15	AC	99 ms	18 MB
g++	max_random_16	AC	131 ms	29 MB
g++	max_random_17	AC	133 ms	29 MB
g++	max_random_18	AC	105 ms	30 MB
g++	max_random_19	AC	106 ms	30 MB
g++	max_random_20	AC	128 ms	20 MB
g++	max_random_21	AC	124 ms	30 MB
g++	max_random_22	AC	137 ms	30 MB
g++	max_random_23	AC	134 ms	30 MB
g++	max_random_24	AC	134 ms	29 MB
g++	max_random_25	AC	143 ms	29 MB
g++	max_random_26	AC	106 ms	30 MB
g++	max_random_27	AC	103 ms	30 MB
g++	max_random_28	AC	133 ms	20 MB
g++	max_random_29	AC	127 ms	30 MB
g++	max_random_30	AC	155 ms	30 MB
g++	max_random_31	AC	151 ms	30 MB
g++	small_00	AC	56 ms	14 MB
g++	small_01	AC	64 ms	17 MB
g++	small_02	AC	62 ms	17 MB

Back to top page