library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: test/unit/persistent_array.test.cpp

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>

#include "datastructure/persistent_array.hpp"
int main() {
    std::mt19937_64 rng(20261027);
    for (int iter = 0; iter < 300; iter++) {
        int n = 1 + rng() % 20;
        std::vector<long long> init(n);
        for (auto& x : init) x = rng() % 100;
        persistent_array<long long> a(init);
        std::vector<std::vector<long long>> versions{init};
        std::vector<int> roots{0};
        assert(a.size() == n);
        for (int t = 0; t < 60; t++) {
            int k = rng() % roots.size();
            int p = rng() % n;
            long long x = rng() % 100;
            roots.push_back(a.set(roots[k], p, x));
            std::vector<long long> v = versions[k];
            v[p] = x;
            versions.push_back(v);
            int c = rng() % roots.size();
            for (int i = 0; i < n; i++) assert(a.get(roots[c], i) == versions[c][i]);
        }
    }
    {
        persistent_array<int> a(5);
        for (int i = 0; i < 5; i++) assert(a.get(0, i) == 0);
        int r1 = a.set(0, 2, 7);
        int r2 = a.set(r1, 2, 9);
        assert(a.get(0, 2) == 0 && a.get(r1, 2) == 7 && a.get(r2, 2) == 9);
    }
    {
        int n = 200000, q = 200000;
        auto start = std::chrono::steady_clock::now();
        persistent_array<int> a(n);
        std::vector<int> roots{0};
        long long acc = 0;
        for (int i = 0; i < q; i++) {
            int k = rng() % roots.size();
            roots.push_back(a.set(roots[k], rng() % n, int(rng() % 1000)));
            acc += a.get(roots[rng() % roots.size()], rng() % n);
        }
        auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start).count();
        std::cerr << "perf n=q=" << n << ": " << ms << " ms (" << acc % 1000 << ")\n";
    }
    std::cout << "Hello World\n";
}
#line 1 "test/unit/persistent_array.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>

#line 4 "datastructure/persistent_array.hpp"
template <class T> struct persistent_array {
public:
    explicit persistent_array(int n) : persistent_array(std::vector<T>(n)) {
    }
    explicit persistent_array(const std::vector<T>& v) : _n(int(v.size())) {
        nodes.reserve(2 * _n);
        if (_n > 0) build(v, 0, _n);
    }
    int size() const {
        return _n;
    }
    T get(int root, int p) const {
        assert(0 <= p && p < _n);
        int cur = root, l = 0, r = _n;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (p < mid) {
                cur = nodes[cur].l, r = mid;
            } else {
                cur = nodes[cur].r, l = mid;
            }
        }
        return nodes[cur].val;
    }
    int set(int root, int p, const T& x) {
        assert(0 <= p && p < _n);
        int res = copy(root);
        int cur = res, l = 0, r = _n;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (p < mid) {
                int nxt = copy(nodes[cur].l);
                nodes[cur].l = nxt;
                cur = nxt, r = mid;
            } else {
                int nxt = copy(nodes[cur].r);
                nodes[cur].r = nxt;
                cur = nxt, l = mid;
            }
        }
        nodes[cur].val = x;
        return res;
    }

private:
    struct node {
        int l, r;
        T val;
    };
    int _n;
    std::vector<node> nodes;
    int copy(int v) {
        nodes.push_back(nodes[v]);
        return int(nodes.size()) - 1;
    }
    int build(const std::vector<T>& v, int l, int r) {
        if (r - l == 1) {
            nodes.push_back({-1, -1, v[l]});
            return int(nodes.size()) - 1;
        }
        int mid = (l + r) / 2;
        int res = int(nodes.size());
        nodes.push_back({-1, -1, T()});
        int lc = build(v, l, mid);
        int rc = build(v, mid, r);
        nodes[res].l = lc, nodes[res].r = rc;
        return res;
    }
};
#line 9 "test/unit/persistent_array.test.cpp"
int main() {
    std::mt19937_64 rng(20261027);
    for (int iter = 0; iter < 300; iter++) {
        int n = 1 + rng() % 20;
        std::vector<long long> init(n);
        for (auto& x : init) x = rng() % 100;
        persistent_array<long long> a(init);
        std::vector<std::vector<long long>> versions{init};
        std::vector<int> roots{0};
        assert(a.size() == n);
        for (int t = 0; t < 60; t++) {
            int k = rng() % roots.size();
            int p = rng() % n;
            long long x = rng() % 100;
            roots.push_back(a.set(roots[k], p, x));
            std::vector<long long> v = versions[k];
            v[p] = x;
            versions.push_back(v);
            int c = rng() % roots.size();
            for (int i = 0; i < n; i++) assert(a.get(roots[c], i) == versions[c][i]);
        }
    }
    {
        persistent_array<int> a(5);
        for (int i = 0; i < 5; i++) assert(a.get(0, i) == 0);
        int r1 = a.set(0, 2, 7);
        int r2 = a.set(r1, 2, 9);
        assert(a.get(0, 2) == 0 && a.get(r1, 2) == 7 && a.get(r2, 2) == 9);
    }
    {
        int n = 200000, q = 200000;
        auto start = std::chrono::steady_clock::now();
        persistent_array<int> a(n);
        std::vector<int> roots{0};
        long long acc = 0;
        for (int i = 0; i < q; i++) {
            int k = rng() % roots.size();
            roots.push_back(a.set(roots[k], rng() % n, int(rng() % 1000)));
            acc += a.get(roots[rng() % roots.size()], rng() % n);
        }
        auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start).count();
        std::cerr << "perf n=q=" << n << ": " << ms << " ms (" << acc % 1000 << ")\n";
    }
    std::cout << "Hello World\n";
}
Back to top page