This documentation is automatically generated by online-judge-tools/verification-helper
#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";
}