| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 302393 | mieszko11b | The Potion of Great Power (CEOI20_potion) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
#define X first
#define Y second
mt19937 rng;
int rand(int a, int b) {
return uniform_int_distribution<int>(a, b)(rng);
}
struct node {
int val, p;
node *l, *r;
node(int v) {
val = v;
p = rand(INT_MIN, INT_MAX - 1);
}
node(node *n) {
val = n->val;
p = n->p;
l = n->l;
r = n->r;
}
node* attach(node *l, node *r) {
this->l = l;
this->r = r;
return this;
}
};
int pr(node *n) {
if(n == nullptr)
return INT_MAX;
return n->p;
}
node* clear(node *n) {
n->l = n->r = nullptr;
return n;
}
struct treap {
vector<node*> root;
vector<int> day;
treap() {
day.push_back(0);
root.push_back(nullptr);
}
void print(node *n) {
if(n == nullptr)
return ;
//~ cout << "[ ";
//~ print(n->l);
//~ cout << " ] (" << n->val << ") [ ";
//~ print(n->r);
//~ cout << " ]";
}
void print() {
print(root.back());
cout << endl;
}
void new_root(int d) {
day.push_back(d);
if(root.empty())
root.push_back(nullptr);
else
root.push_back(root.back());
}
node* merge(node *a, node *b) {
if(a == nullptr)
return b;
if(b == nullptr)
return a;
if(a->p > b->p)
swap(a, b);
a = new node(a);
if(b->val < a->val)
return a->attach(merge(a->l, b), a->r);
return a->attach(a->l, merge(a->r, b));
}
pair<node*, node*> split(node *n, int x) {
if(n == nullptr)
return {nullptr, nullptr};
n = new node(n);
if(n->val < x) {
auto p = split(n->r, x);
return {n->attach(n->l, p.X), p.Y};
}
auto p = split(n->l, x);
return {p.X, n->attach(p.Y, n->r)};
}
void insert(int x, int d) {
new_root(d);
auto p = split(root.back(), x);
root.back() = merge(merge(p.X, new node(x)), p.Y);
//~ print();
}
node* erase(node *n, node *x) {
if(n->val == x->val)
return merge(n->l, n->r);
if(x->val < n->val)
return (new node(n))->attach(erase(n->l, x), n->r);
else
return (new node(n))->attach(n->l, erase(n->r, x));
}
void erase(int x, int d) {
new_root(d);
root.back() = erase(root.back(), new node(x));
//~ print();
}
vector<int> hlp;
void dfs(node *n) {
if(n == nullptr)
return ;
dfs(n->l);
hlp.push_back(n->val);
dfs(n->r);
}
vector<int> get_all(int t) {
int r = prev(upper_bound(day.begin(), day.end(), t)) - day.begin();
hlp.clear();
dfs(root[r]);
return hlp;
}
};
treap T[100007];
int n, d, u, q;
int h[100007];
set<ii> S;
int closest(vector<int> A, vector<int> B) {
int res = 1e9;
int j = 0;
for(int i = 0 ; i < A.size() ; i++) {
while(j < B.size() && B[j] < A[i])
j++;
if(j < B.size())
res = min(res, abs(A[i] - B[j]));
if(j - 1 >= 0)
res = min(res, abs(A[i] - B[j - 1]));
}
return res;
}
void init(int N, int D, vector<int> H) {
int c = chrono::steady_clock().now().time_since_epoch().count();
//~ int c = -507409753;
//~ cout << c << endl;
rng = mt19937(c);
n = N;
d = D;
for(int i = 0 ; i < n ; i++)
h[i] = H[i];
}
void curseChanges(int U, vector<int> A, vector<int> B) {
for(int i = 0 ; i < U ; i++) {
int a, b;
a = A[i];
b = B[i];
if(a > b) swap(a, b);
if(S.count({a, b})) {
//~ cout << "erase " << a << " " << b << endl;
T[a].erase(h[b], i + 1);
//~ T[a].print();
T[b].erase(h[a], i + 1);
//~ T[b].print();
S.erase({a, b});
} else {
//~ cout << "insert " << a << " " << b << endl;
T[a].insert(h[b], i + 1);
//~ T[a].print();
T[b].insert(h[a], i + 1);
//~ T[b].print();
S.insert({a, b});
}
//~ cout << endl;
}
}
int question(int X, int Y, int V) {
return closest(T[X].get_all(V), T[Y].get_all(V));
}