test/library_checker/data_structure/associative_array.test.cpp

• View this file on GitHub
• Last update: 2025-01-09 22:07:23+09:00
• Problem: https://judge.yosupo.jp/problem/associative_array

Depends on

• Compression (座標圧縮) (lib/others/compression.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/associative_array"
#include <bits/stdc++.h>
using namespace std;

#include "../../../lib/others/compression.hpp"

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q; cin >> q;
    using T = tuple<int, long long, long long>;
    vector<T> query(q);
    vector<long long> x(q);
    for(int i = 0; i < q; i++){
        int t; cin >> t;
        long long k = -1, v = -1;
        if(t == 0){
            cin >> k >> v;
        }else{
            cin >> k;
        }
        query[i] = {t, k, v};
        x[i] = k;
    }
    compress<long long> cp(x);
    vector<long long> a(cp.size(), 0);
    for(int i = 0; i < q; i++){
        auto [t, k, v] = query[i];
        if(t == 0){
            a[cp.get(k)] = v;
        }else{
            cout << a[cp.get(k)] << "\n";
        }
    }
}

#line 1 "test/library_checker/data_structure/associative_array.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/associative_array"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/others/compression.hpp"

/**
 * @brief Compression (座標圧縮)
 * @docs docs/others/compression.md
 */

#line 10 "lib/others/compression.hpp"

template <typename T>
struct compress{
    std::vector<T> sorted;
    std::vector<int> compressed;

    compress(const std::vector<T> &vec){
        int n = vec.size();
        compressed.resize(n);
        for(T x : vec){
            sorted.emplace_back(x);
        }
        std::sort(sorted.begin(), sorted.end());
        sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());
        for(int i = 0; i < n; ++i){
            compressed[i] = std::lower_bound(sorted.begin(), sorted.end(), vec[i]) - sorted.begin();
        }
    }

    int get(const T &x) const{
        return std::lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();
    }

    T inv(const int x) const{
        return sorted[x];
    }

    size_t size() const{
        return sorted.size();
    }

    std::vector<int> getCompressed() const{
        return compressed;
    }
};
#line 6 "test/library_checker/data_structure/associative_array.test.cpp"

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q; cin >> q;
    using T = tuple<int, long long, long long>;
    vector<T> query(q);
    vector<long long> x(q);
    for(int i = 0; i < q; i++){
        int t; cin >> t;
        long long k = -1, v = -1;
        if(t == 0){
            cin >> k >> v;
        }else{
            cin >> k;
        }
        query[i] = {t, k, v};
        x[i] = k;
    }
    compress<long long> cp(x);
    vector<long long> a(cp.size(), 0);
    for(int i = 0; i < q; i++){
        auto [t, k, v] = query[i];
        if(t == 0){
            a[cp.get(k)] = v;
        }else{
            cout << a[cp.get(k)] << "\n";
        }
    }
}

Back to top page