verify/Datastructure_pbds_set.test.cpp

View this file on GitHub
Last update: 2025-01-10 00:00:54+09:00
Problem: https://judge.yosupo.jp/problem/predecessor_problem

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/predecessor_problem"
#include "../Utility/template.hpp"
#include "../Datastructure/pbds_set.hpp"

int main () {


    TR<int> cnt;

    int N, Q;
    cin >> N >> Q;
    string T;
    cin >> T;

    rep(t, 0, N) if(T[t] == '1') cnt.insert(t);
    

    while(Q--) {
        int t, k;
        cin >> t >> k;
        if(t == 0) {
            cnt.insert(k);
        }
        else if(t==1) {
		  cnt.erase(k);
        }
        else if(t==2) {
            int it = cnt.order_of_key(k);
            if(it < cnt.size() && *cnt.find_by_order(it) == k) cout << 1 << '\n';
            else cout << 0 << "\n";
        }
        else if(t==3) {
            int it = cnt.order_of_key(k);
            if(it < cnt.size()) cout << *cnt.find_by_order(it) << '\n';
            else cout << -1 << '\n';
        }
        else {
            int it = cnt.order_of_key(k);
            if(it < cnt.size() && *cnt.find_by_order(it) == k) cout << k << '\n';
            else {
                it--;
                if(it >= 0) cout << *cnt.find_by_order(it) << '\n';
                else cout << -1 << '\n';
            }

        }
    }

}

#line 1 "verify/Datastructure_pbds_set.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/predecessor_problem"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Datastructure/pbds_set.hpp"
//ここから
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
TT using TR = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
TT using MTR = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

// set
// insert, erase, find, find_by_order, order_of_key, size

/*
--set--
insert(要素)
erase(find(要素)), erase(要素)
find(要素)
find_by_order(数字)
order_of_key(要素)
size()
*/

/* 
--multiset--
insert(要素)
erase(find_by_order(order_of_key(要素)))
  注:  erase(要素), erase(find(要素))は意味がなかった
find(要素)
find_by_order(数字)
order_of_key(要素)
size()
*/

/*
@brief pdbsのテンプレート
*/
#line 4 "verify/Datastructure_pbds_set.test.cpp"

int main () {


    TR<int> cnt;

    int N, Q;
    cin >> N >> Q;
    string T;
    cin >> T;

    rep(t, 0, N) if(T[t] == '1') cnt.insert(t);
    

    while(Q--) {
        int t, k;
        cin >> t >> k;
        if(t == 0) {
            cnt.insert(k);
        }
        else if(t==1) {
		  cnt.erase(k);
        }
        else if(t==2) {
            int it = cnt.order_of_key(k);
            if(it < cnt.size() && *cnt.find_by_order(it) == k) cout << 1 << '\n';
            else cout << 0 << "\n";
        }
        else if(t==3) {
            int it = cnt.order_of_key(k);
            if(it < cnt.size()) cout << *cnt.find_by_order(it) << '\n';
            else cout << -1 << '\n';
        }
        else {
            int it = cnt.order_of_key(k);
            if(it < cnt.size() && *cnt.find_by_order(it) == k) cout << k << '\n';
            else {
                it--;
                if(it >= 0) cout << *cnt.find_by_order(it) << '\n';
                else cout << -1 << '\n';
            }

        }
    }

}