#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
#define REP(i,n) for (int i = 0; i < n; i++)
#define trav(a,x) for (auto &a : x)
#define all(x) (x).begin(), (x).end()
#define submit(a,b) cout << a << " " << b << endl
#define D(x) //cerr << #x << ": " << x << endl;
int n,d;
vi alln;
struct Treap {
int num;
int prio;
Treap *left = nullptr, *right = nullptr;
Treap(Treap *t) {
num = t->num;
prio = t->prio;
}
Treap(int nm, int pr) {
num = nm;
prio = pr;
}
Treap(int nm) {
num = nm;
prio = rand();
}
void check_depth(int depth = 0) {
//assert(depth < 50);
if (left != nullptr) {
assert(prio <= left->prio);
left->check_depth(depth+1);
}
if (right != nullptr) {
assert(prio <= right->prio);
right->check_depth(depth+1);
}
}
void gather_all() {
alln.push_back(num);
if (left != nullptr) left->gather_all();
if (right != nullptr) right->gather_all();
}
};
Treap* merge(Treap* left, Treap* right) {
if (left == nullptr) return right;
if (right == nullptr) return left;
if (left->prio <= right->prio) {
Treap *t = new Treap(left);
t->left = left->left;
t->right = merge(left->right, right);
return t;
} else {
Treap *t = new Treap(right);
t->right = right->right;
t->left = merge(left, right->left);
return t;
}
}
pair<Treap*, Treap*> split(Treap* tr, int num) {
if (tr == nullptr) return {tr, tr};
if (tr->num < num) {
Treap *t = new Treap(tr);
t->left = tr->left;
auto p = split(tr->right, num);
t->right = p.first;
return {t, p.second};
} else {
Treap *t = new Treap(tr);
t->right = tr->right;
auto p = split(tr->left, num);
t->left = p.second;
return {p.first, t};
}
}
const int MAX_N = 1e5+2;
Treap* smol[MAX_N];
Treap* flipp(Treap* tr, int num) {
Treap *lower, *exact, *bigger;
auto p = split(tr, num);
lower = p.first;
auto p2 = split(p.second, num+1);
exact = p2.first;
bigger = p2.second;
if (exact == nullptr) exact = new Treap(num, rand()); //exact = smol[num];
else exact = nullptr;
Treap* t = merge(lower, exact);
return merge(t, bigger);
}
struct TimeTraveller {
vector<pair<int, Treap*>> history;
TimeTraveller() {
history.push_back({-1, nullptr});
}
void flip(int i, int time) {
Treap* c = flipp(history.back().second, i);
if (rand() % 100 == 0) c->check_depth();
history.push_back({time, c});
}
vi get_all(int time) {
auto p = lower_bound(all(history), pair<int, Treap*>(time+1, nullptr));
p--;
alln = vi();
if (p->second == nullptr) return vi();
p->second->gather_all();
assert(alln.size() <= d);
return alln;
}
};
vi hs;
TimeTraveller fr[MAX_N];
int get_ans(vi a, vi b) {
int best = 1e9;
vi h1, h2;
trav(aa, a) {
h1.push_back(hs[aa]);
}
sort(all(h1));
trav(bb, b) {
h2.push_back(hs[bb]);
}
sort(all(h2));
if (h1.size() == 0) return best;
int i = 0;
trav(hb, h2) {
while (h1[i] < hb && i != h1.size()-1) i++;
best = min(best, abs(hb - h1[i]));
if (i!=0) best = min(best, abs(hb - h1[i-1]));
}
return best;
}
bool called = false;
void init(int N, int D, int H[]) {
srand(899852);
n = N; d = D;
REP(i,n) hs.push_back(H[i]);
REP(i,n) smol[i] = new Treap(i, rand());
}
void curseChanges(int U, int A[], int B[]) {
assert(!called);
called = 1;
REP(uu, U) {
int a = A[uu];
int b = B[uu];
fr[a].flip(b, uu+1);
fr[b].flip(a, uu+1);
}
}
int question(int x, int y, int v) {
return get_ans(fr[x].get_all(v), fr[y].get_all(v));
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from potion.cpp:1:
potion.cpp: In member function 'vi TimeTraveller::get_all(int)':
potion.cpp:124:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
124 | assert(alln.size() <= d);
| ~~~~~~~~~~~~^~~~
potion.cpp: In function 'int get_ans(vi, vi)':
potion.cpp:150:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | while (h1[i] < hb && i != h1.size()-1) i++;
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6232 KB |
Output is correct |
| 2 |
Correct |
5 ms |
6232 KB |
Output is correct |
| 3 |
Correct |
5 ms |
6232 KB |
Output is correct |
| 4 |
Correct |
22 ms |
10968 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
324 ms |
78292 KB |
Output is correct |
| 2 |
Correct |
261 ms |
78264 KB |
Output is correct |
| 3 |
Runtime error |
58 ms |
24508 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
276 ms |
78644 KB |
Output is correct |
| 2 |
Runtime error |
66 ms |
28352 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
8636 KB |
Output is correct |
| 2 |
Runtime error |
10 ms |
14680 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5716 KB |
Output is correct |
| 2 |
Correct |
5 ms |
6232 KB |
Output is correct |
| 3 |
Correct |
5 ms |
6232 KB |
Output is correct |
| 4 |
Correct |
5 ms |
6232 KB |
Output is correct |
| 5 |
Correct |
22 ms |
10968 KB |
Output is correct |
| 6 |
Correct |
324 ms |
78292 KB |
Output is correct |
| 7 |
Correct |
261 ms |
78264 KB |
Output is correct |
| 8 |
Runtime error |
58 ms |
24508 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
