This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5 + 7;
template < const int L, const int R >
struct DynPersSegTreeSet {
struct Node {
int val;
Node *left, *right;
Node(int _val, Node *_left, Node *_right) { val = _val; left = _left; right = _right; }
Node(const Node &oth) { val = oth.val; left = oth.left; right = oth.right; }
Node() { val = 0; left = right = nullptr; }
};
inline static Node nullish;
Node* _update(Node *cnt, int l, int r, int poz, bool to_insert) {
if(l == r) return (to_insert ? (new Node(1, &nullish, &nullish)) : &nullish);
Node *ret_node = new Node(*cnt);
int mid = (l + r) / 2;
if(poz <= mid) ret_node->left = _update(ret_node->left, l, mid, poz, to_insert);
else ret_node->right = _update(ret_node->right, mid + 1, r, poz, to_insert);
ret_node->val = ret_node->left->val + ret_node->right->val;
return ret_node;
}
int _query(Node *cnt, int l, int r, int poz) {
if(l == r) return cnt->val != 0;
int mid = (l + r) / 2;
if(poz <= mid) return _query(cnt->left, l, mid, poz);
else return _query(cnt->right, mid + 1, r, poz);
}
Node *head;
DynPersSegTreeSet() {
nullish = Node(0, &nullish, &nullish);
head = &nullish;
}
void change(int x) {
bool is_friend = _query(head, L, R, x);
head = _update(head, L, R, x, !is_friend);
}
void put_all(Node *cnt, int l, int r, vector<int>& v) {
if(cnt->val == 0) return;
if(l == r) { v.push_back(l); return; }
int mid = (l + r) / 2;
put_all(cnt->left, l, mid, v);
put_all(cnt->right, mid + 1, r, v);
return;
}
vector<int> get_all() {
vector<int> ret; ret.reserve(head->val);
put_all(head, L, R, ret);
return ret;
}
};
using PersSet = DynPersSegTreeSet<0, NMAX>;
struct Shaman {
vector<pair<int, PersSet>> friends;
Shaman() {
friends.push_back({0, PersSet()});
}
void change(int day, int oth) {
PersSet next_friends = friends.back().second;
next_friends.change(oth);
friends.push_back({day, next_friends});
}
vector<int> get_friends(int day) {
int ans = 0, step = 1;
while(step < friends.size()) step *= 2;
for(; step > 0; step /= 2) {
if(ans + step < friends.size() && friends[ans + step].first <= day) ans += step;
}
return friends[ans].second.get_all();
}
} shamans[NMAX];
int heights[NMAX];
void init(int n, int d, int h[]) {
for(auto &s : shamans) s = Shaman();
for(int i = 0; i < n; i++) heights[i] = h[i];
}
void curseChanges(int u, int a[], int b[]) {
for(int day = 1; day <= u; day++) {
int x, y; x = a[day - 1]; y = b[day - 1];
shamans[x].change(day, y);
shamans[y].change(day, x);
}
}
int question(int x, int y, int day) {
auto vecx = shamans[x].get_friends(day);
for(auto &e : vecx) e = heights[e];
sort(vecx.begin(), vecx.end());
auto vecy = shamans[y].get_friends(day);
for(auto &e : vecy) e = heights[e];
sort(vecy.begin(), vecy.end());
#ifdef DEBUG
cerr << "VECX: "; for(auto e : vecx) cerr << e << " "; cerr << endl;
cerr << "VECY: "; for(auto e : vecy) cerr << e << " "; cerr << endl;
cerr << endl << endl;
#endif // DEBUG
int min_dist = 1e9;
for(auto xf : vecx) {
int yind = static_cast<int>(lower_bound(vecy.begin(), vecy.end(), xf) - vecy.begin());
if(yind < vecy.size()) min_dist = min(min_dist, vecy[yind] - xf);
if(yind - 1 >= 0) min_dist = min(min_dist, xf - vecy[yind - 1]);
}
return min_dist;
}
Compilation message (stderr)
potion.cpp: In member function 'std::vector<int> Shaman::get_friends(int)':
potion.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, DynPersSegTreeSet<0, 100007> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | while(step < friends.size()) step *= 2;
| ~~~~~^~~~~~~~~~~~~~~~
potion.cpp:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, DynPersSegTreeSet<0, 100007> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | if(ans + step < friends.size() && friends[ans + step].first <= day) ans += step;
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:134:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | if(yind < vecy.size()) min_dist = min(min_dist, vecy[yind] - xf);
| ~~~~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |