cp-library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub pt13762104/cp-library

:heavy_check_mark: Memory efficient sqrt set (yoshi_likes_e4/mem_efficient_set.test.cpp)

Code

// @brief Memory efficient sqrt set
#define PROBLEM "https://judge.yosupo.jp/problem/ordered_set"
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#ifndef yoshi_likes_e4
#define endl '\n'
#endif
#define problem ""
#define multitest 0
#define debug(x) cerr << #x << " = " << x << endl;
void init()
{
}
const int B = 4096;
template <int sz> struct Circular_Buffer_Deque
{
    int elems[sz];
    int start = 0, length = 0;
    void insert(int p, int x)
    {
        assert(size() < sz);
        int v[length - p];
        if (start + length <= sz)
            copy(elems + start + p, elems + start + length, v);
        else if (start + p < sz)
        {
            copy(elems + start + p, elems + sz, v);
            copy(elems, elems + start + length - sz, v + sz - start - p);
        }
        else
        {
            start -= sz;
            if (start + length <= sz)
                copy(elems + start + p, elems + start + length, v);
            else if (start + p < sz)
            {
                copy(elems + start + p, elems + sz, v);
                copy(elems, elems + start + length - sz, v + sz - start - p);
            }
            start += sz;
        }
        elems[(start + p) % sz] = x;
        start++;
        if (start + length <= sz)
            copy(v, v + length - p, elems + start + p);
        else if (start + p < sz)
        {
            copy(v, v + sz - start - p, elems + start + p);
            copy(v + sz - start - p, v + length - p, elems);
        }
        else
        {
            start -= sz;
            if (start + length <= sz)
                copy(v, v + length - p, elems + start + p);
            else if (start + p < sz)
            {
                copy(v, v + sz - start - p, elems + start + p);
                copy(v + sz - start - p, v + length - p, elems);
            }
            start += sz;
        }
        start--;
        length++;
    }
    void erase(int p)
    {
        assert(size());
        int v[length - p - 1];
        length--;
        start++;
        if (start + length <= sz)
            copy(elems + start + p, elems + start + length, v);
        else if (start + p < sz)
        {
            copy(elems + start + p, elems + sz, v);
            copy(elems, elems + start + length - sz, v + sz - start - p);
        }
        else
        {
            start -= sz;
            if (start + length <= sz)
                copy(elems + start + p, elems + start + length, v);
            else if (start + p < sz)
            {
                copy(elems + start + p, elems + sz, v);
                copy(elems, elems + start + length - sz, v + sz - start - p);
            }
            start += sz;
        }
        start--;
        if (start + length <= sz)
            copy(v, v + length - p, elems + start + p);
        else if (start + p < sz)
        {
            copy(v, v + sz - start - p, elems + start + p);
            copy(v + sz - start - p, v + length - p, elems);
        }
        else
        {
            start -= sz;
            if (start + length <= sz)
                copy(v, v + length - p, elems + start + p);
            else if (start + p < sz)
            {
                copy(v, v + sz - start - p, elems + start + p);
                copy(v + sz - start - p, v + length - p, elems);
            }
            start += sz;
        }
    }
    void push_back(int x)
    {
        assert(size() < sz);
        length++;
        elems[(start + length - 1) % sz] = x;
    }
    void push_front(int x)
    {
        assert(size() < sz);
        length++, start += sz - 1, start %= sz;
        elems[start] = x;
    }
    void pop_back()
    {
        assert(size());
        length--;
    }
    void pop_front()
    {
        assert(size());
        length--, start++, start %= sz;
    }
    int &operator[](int x)
    {
        return elems[(start + x) % sz];
    }
    int &front()
    {
        return elems[start];
    }
    int &back()
    {
        return elems[(start + length - 1) % sz];
    }
    int size()
    {
        return length;
    }
};
struct SQRT_set
{
    vector<Circular_Buffer_Deque<B + 1>> deques;
    int n = 0;
    int get_kth(int x)
    {
        return deques[x / B][x % B];
    }
    int order(int x)
    {
        // equal to --upper_bound
        int l = -1;
        if (n)
            for (int R = 1 << __lg(n); R; R >>= 1)
            {
                if (l + R < n && get_kth(l + R) <= x)
                    l += R;
            }
        return l;
    }
    void insert(int x)
    {
        int pos = order(x);
        if (pos != -1 && get_kth(pos) == x)
            return;
        pos++;
        if (!deques.size() || deques.back().size() == B)
            deques.push_back({});
        deques[pos / B].insert(pos % B, x);
        if (deques[pos / B].size() > B)
        {
            int i = pos / B + 1;
            while (i < deques.size() && deques[i - 1].size() > B)
            {
                auto v = deques[i - 1].back();
                deques[i - 1].pop_back();
                deques[i].push_front(v);
                i++;
            }
        }
        if (!deques.back().size())
            deques.pop_back();
        n++;
    }
    void erase(int x)
    {
        int pos = order(x);
        if (pos == -1 || (pos != -1 && get_kth(pos) != x))
            return;
        deques[pos / B].erase(pos % B);
        int i = pos / B + 1;
        while (i < deques.size())
        {
            auto v = deques[i].front();
            deques[i].pop_front();
            deques[i - 1].push_back(v);
            i++;
        }
        if (!deques.back().size())
            deques.pop_back();
        n--;
    }
};
void Yoshi()
{
    SQRT_set s;
    int q;
    cin >> s.n >> q;
    for (int i = 0; i < s.n; i++)
    {
        int x;
        cin >> x;
        if (i % B == 0)
            s.deques.push_back({});
        s.deques.back().push_back(x);
    }
    while (q--)
    {
        int t, x;
        cin >> t >> x;
        if (t == 0)
        {
            s.insert(x);
        }
        else if (t == 1)
        {
            s.erase(x);
        }
        else if (t == 2)
        {
            if (x > s.n)
                cout << -1 << endl;
            else
                cout << s.get_kth(x - 1) << endl;
        }
        else if (t == 3)
        {
            cout << s.order(x) + 1 << endl;
        }
        else if (t == 4)
        {
            int v = s.order(x);
            if (v == -1)
                cout << -1 << endl;
            else
                cout << s.get_kth(v) << endl;
        }
        else
        {
            int v = s.order(x);
            if (v == -1 || s.get_kth(v) != x)
                v++;
            if (v == s.n)
                cout << -1 << endl;
            else
                cout << s.get_kth(v) << endl;
        }
    }
}
signed main()
{
#ifndef yoshi_likes_e4
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(problem ".inp", "r"))
    {
        freopen(problem ".inp", "r", stdin);
        freopen(problem ".out", "w", stdout);
    }
#endif
    init();
    int t = 1;
#if multitest
    cin >> t;
#endif
    while (t--)
        Yoshi();
}
#line 1 "yoshi_likes_e4/mem_efficient_set.test.cpp"
// @brief Memory efficient sqrt set
#define PROBLEM "https://judge.yosupo.jp/problem/ordered_set"
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#ifndef yoshi_likes_e4
#define endl '\n'
#endif
#define problem ""
#define multitest 0
#define debug(x) cerr << #x << " = " << x << endl;
void init()
{
}
const int B = 4096;
template <int sz> struct Circular_Buffer_Deque
{
    int elems[sz];
    int start = 0, length = 0;
    void insert(int p, int x)
    {
        assert(size() < sz);
        int v[length - p];
        if (start + length <= sz)
            copy(elems + start + p, elems + start + length, v);
        else if (start + p < sz)
        {
            copy(elems + start + p, elems + sz, v);
            copy(elems, elems + start + length - sz, v + sz - start - p);
        }
        else
        {
            start -= sz;
            if (start + length <= sz)
                copy(elems + start + p, elems + start + length, v);
            else if (start + p < sz)
            {
                copy(elems + start + p, elems + sz, v);
                copy(elems, elems + start + length - sz, v + sz - start - p);
            }
            start += sz;
        }
        elems[(start + p) % sz] = x;
        start++;
        if (start + length <= sz)
            copy(v, v + length - p, elems + start + p);
        else if (start + p < sz)
        {
            copy(v, v + sz - start - p, elems + start + p);
            copy(v + sz - start - p, v + length - p, elems);
        }
        else
        {
            start -= sz;
            if (start + length <= sz)
                copy(v, v + length - p, elems + start + p);
            else if (start + p < sz)
            {
                copy(v, v + sz - start - p, elems + start + p);
                copy(v + sz - start - p, v + length - p, elems);
            }
            start += sz;
        }
        start--;
        length++;
    }
    void erase(int p)
    {
        assert(size());
        int v[length - p - 1];
        length--;
        start++;
        if (start + length <= sz)
            copy(elems + start + p, elems + start + length, v);
        else if (start + p < sz)
        {
            copy(elems + start + p, elems + sz, v);
            copy(elems, elems + start + length - sz, v + sz - start - p);
        }
        else
        {
            start -= sz;
            if (start + length <= sz)
                copy(elems + start + p, elems + start + length, v);
            else if (start + p < sz)
            {
                copy(elems + start + p, elems + sz, v);
                copy(elems, elems + start + length - sz, v + sz - start - p);
            }
            start += sz;
        }
        start--;
        if (start + length <= sz)
            copy(v, v + length - p, elems + start + p);
        else if (start + p < sz)
        {
            copy(v, v + sz - start - p, elems + start + p);
            copy(v + sz - start - p, v + length - p, elems);
        }
        else
        {
            start -= sz;
            if (start + length <= sz)
                copy(v, v + length - p, elems + start + p);
            else if (start + p < sz)
            {
                copy(v, v + sz - start - p, elems + start + p);
                copy(v + sz - start - p, v + length - p, elems);
            }
            start += sz;
        }
    }
    void push_back(int x)
    {
        assert(size() < sz);
        length++;
        elems[(start + length - 1) % sz] = x;
    }
    void push_front(int x)
    {
        assert(size() < sz);
        length++, start += sz - 1, start %= sz;
        elems[start] = x;
    }
    void pop_back()
    {
        assert(size());
        length--;
    }
    void pop_front()
    {
        assert(size());
        length--, start++, start %= sz;
    }
    int &operator[](int x)
    {
        return elems[(start + x) % sz];
    }
    int &front()
    {
        return elems[start];
    }
    int &back()
    {
        return elems[(start + length - 1) % sz];
    }
    int size()
    {
        return length;
    }
};
struct SQRT_set
{
    vector<Circular_Buffer_Deque<B + 1>> deques;
    int n = 0;
    int get_kth(int x)
    {
        return deques[x / B][x % B];
    }
    int order(int x)
    {
        // equal to --upper_bound
        int l = -1;
        if (n)
            for (int R = 1 << __lg(n); R; R >>= 1)
            {
                if (l + R < n && get_kth(l + R) <= x)
                    l += R;
            }
        return l;
    }
    void insert(int x)
    {
        int pos = order(x);
        if (pos != -1 && get_kth(pos) == x)
            return;
        pos++;
        if (!deques.size() || deques.back().size() == B)
            deques.push_back({});
        deques[pos / B].insert(pos % B, x);
        if (deques[pos / B].size() > B)
        {
            int i = pos / B + 1;
            while (i < deques.size() && deques[i - 1].size() > B)
            {
                auto v = deques[i - 1].back();
                deques[i - 1].pop_back();
                deques[i].push_front(v);
                i++;
            }
        }
        if (!deques.back().size())
            deques.pop_back();
        n++;
    }
    void erase(int x)
    {
        int pos = order(x);
        if (pos == -1 || (pos != -1 && get_kth(pos) != x))
            return;
        deques[pos / B].erase(pos % B);
        int i = pos / B + 1;
        while (i < deques.size())
        {
            auto v = deques[i].front();
            deques[i].pop_front();
            deques[i - 1].push_back(v);
            i++;
        }
        if (!deques.back().size())
            deques.pop_back();
        n--;
    }
};
void Yoshi()
{
    SQRT_set s;
    int q;
    cin >> s.n >> q;
    for (int i = 0; i < s.n; i++)
    {
        int x;
        cin >> x;
        if (i % B == 0)
            s.deques.push_back({});
        s.deques.back().push_back(x);
    }
    while (q--)
    {
        int t, x;
        cin >> t >> x;
        if (t == 0)
        {
            s.insert(x);
        }
        else if (t == 1)
        {
            s.erase(x);
        }
        else if (t == 2)
        {
            if (x > s.n)
                cout << -1 << endl;
            else
                cout << s.get_kth(x - 1) << endl;
        }
        else if (t == 3)
        {
            cout << s.order(x) + 1 << endl;
        }
        else if (t == 4)
        {
            int v = s.order(x);
            if (v == -1)
                cout << -1 << endl;
            else
                cout << s.get_kth(v) << endl;
        }
        else
        {
            int v = s.order(x);
            if (v == -1 || s.get_kth(v) != x)
                v++;
            if (v == s.n)
                cout << -1 << endl;
            else
                cout << s.get_kth(v) << endl;
        }
    }
}
signed main()
{
#ifndef yoshi_likes_e4
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(problem ".inp", "r"))
    {
        freopen(problem ".inp", "r", stdin);
        freopen(problem ".out", "w", stdout);
    }
#endif
    init();
    int t = 1;
#if multitest
    cin >> t;
#endif
    while (t--)
        Yoshi();
}

Test cases

Env Name Status Elapsed Memory
g++ example_00 :heavy_check_mark: AC 5 ms 4 MB
g++ example_01 :heavy_check_mark: AC 4 ms 4 MB
g++ max_random_00 :heavy_check_mark: AC 110 ms 4 MB
g++ max_random_01 :heavy_check_mark: AC 109 ms 4 MB
g++ max_random_02 :heavy_check_mark: AC 106 ms 4 MB
g++ max_random_03 :heavy_check_mark: AC 72 ms 4 MB
g++ max_random_04 :heavy_check_mark: AC 77 ms 4 MB
g++ max_random_05 :heavy_check_mark: AC 109 ms 4 MB
g++ max_random_06 :heavy_check_mark: AC 122 ms 4 MB
g++ max_random_07 :heavy_check_mark: AC 116 ms 4 MB
g++ max_random_08 :heavy_check_mark: AC 116 ms 4 MB
g++ max_random_09 :heavy_check_mark: AC 115 ms 4 MB
g++ max_random_10 :heavy_check_mark: AC 107 ms 4 MB
g++ max_random_11 :heavy_check_mark: AC 71 ms 4 MB
g++ max_random_12 :heavy_check_mark: AC 71 ms 4 MB
g++ max_random_13 :heavy_check_mark: AC 110 ms 4 MB
g++ max_random_14 :heavy_check_mark: AC 124 ms 4 MB
g++ max_random_15 :heavy_check_mark: AC 123 ms 4 MB
g++ max_random_16 :heavy_check_mark: AC 269 ms 7 MB
g++ max_random_17 :heavy_check_mark: AC 243 ms 10 MB
g++ max_random_18 :heavy_check_mark: AC 391 ms 10 MB
g++ max_random_19 :heavy_check_mark: AC 363 ms 6 MB
g++ max_random_20 :heavy_check_mark: AC 116 ms 7 MB
g++ max_random_21 :heavy_check_mark: AC 211 ms 7 MB
g++ max_random_22 :heavy_check_mark: AC 209 ms 6 MB
g++ max_random_23 :heavy_check_mark: AC 216 ms 7 MB
g++ max_random_24 :heavy_check_mark: AC 302 ms 7 MB
g++ max_random_25 :heavy_check_mark: AC 262 ms 10 MB
g++ max_random_26 :heavy_check_mark: AC 390 ms 10 MB
g++ max_random_27 :heavy_check_mark: AC 362 ms 7 MB
g++ max_random_28 :heavy_check_mark: AC 127 ms 7 MB
g++ max_random_29 :heavy_check_mark: AC 239 ms 7 MB
g++ max_random_30 :heavy_check_mark: AC 247 ms 7 MB
g++ max_random_31 :heavy_check_mark: AC 241 ms 6 MB
g++ small_00 :heavy_check_mark: AC 85 ms 4 MB
g++ small_01 :heavy_check_mark: AC 73 ms 4 MB
g++ small_02 :heavy_check_mark: AC 69 ms 4 MB
Back to top page