#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
using ii = pair<int, int>;
using vi = vector<int>;
namespace AINTpers {
vi Cnt, L, R;
vector<bool> Calc;
vector<vi> Idk;
int nod_nou() {
Cnt.push_back(0);
L.push_back(-1);
R.push_back(-1);
Calc.push_back(false);
Idk.push_back({});
return int(Cnt.size()) - 1;
}
int join(int u, int v) {
int re = L.size();
int c = 0;
if(u != -1) c += Cnt[u];
if(v != -1) c += Cnt[v];
Cnt.push_back(c);
L.push_back(u);
R.push_back(v);
Calc.push_back(false);
Idk.push_back({});
return re;
}
int enable(int u, int p, int st, int dr) {
if(p < st || dr < p) return u;
if(st == dr) {
int v = L.size();
Cnt.push_back(1);
L.push_back(-1); R.push_back(-1);
Calc.push_back(false);
Idk.push_back({});
return v;
}
int l = -1, r = -1;
if(u != -1) l = L[u];
if(u != -1) r = R[u];
return join(enable(l, p, st, (st + dr) >> 1),
enable(r, p, ((st + dr) >> 1) + 1, dr));
}
int disable(int u, int p, int st, int dr) {
if(p < st || dr < p) return u;
if(st == dr) {
int v = L.size();
Cnt.push_back(0);
L.push_back(-1); R.push_back(-1);
Calc.push_back(false);
Idk.push_back({});
return v;
}
int l = -1, r = -1;
if(u != -1) l = L[u];
if(u != -1) r = R[u];
return join(disable(l, p, st, (st + dr) >> 1),
disable(r, p, ((st + dr) >> 1) + 1, dr));
}
int stare(int u, int p, int st, int dr) {
if(u == -1 || !Cnt[u]) return 0;
if(st == dr) return Cnt[u];
int mij = (st + dr) / 2;
if(p <= mij) {
return stare(L[u], p, st, mij);
}
return stare(R[u], p, mij + 1, dr);
}
vi enumerate(int u, int st, int dr) {
if(u == -1 || !Cnt[u]) return vi{};
if(Calc[u]) return Idk[u];
Calc[u] = true;
if(st == dr) {
Idk[u] = {st};
} else {
vi A = enumerate(L[u], st, (st + dr) >> 1);
vi B = enumerate(R[u], ((st + dr) >> 1) + 1, dr);
for(auto it : B) A.push_back(it);
Idk[u] = A;
}
return Idk[u];
}
}
struct SetPers {
int n;
vector<ii> Rad;
SetPers(int N) : n(N) {
Rad.emplace_back(0, AINTpers::nod_nou());
}
void update(int t, int p) {
int r = Rad.back().second;
int a = AINTpers::stare(r, p, 0, n - 1);
if(!a) {
Rad.push_back({t, AINTpers::enable(r, p, 0, n - 1)});
} else {
Rad.push_back({t, AINTpers::disable(r, p, 0, n - 1)});
}
}
vi list(int t) {
auto it = upper_bound(Rad.begin(), Rad.end(), ii{t, 1e9});
--it;
int r = it->second;
vi Re = AINTpers::enumerate(r, 0, n - 1);
return Re;
}
};
int n;
vector<ii> H0;
vi Perm;
vector<SetPers> S;
void init(int N, int D, int H[]) {
n = N;
for(int i = 0; i < n; ++i) H0.push_back({H[i], i});
sort(H0.begin(), H0.end());
Perm.resize(n);
for(int i = 0; i < n; ++i)
Perm[H0[i].second] = i;
for(int i = 0; i < n; ++i)
S.push_back(SetPers(N));
}
void curseChanges(int U, int A[], int B[]) {
for(int i = 1; i <= U; ++i) {
int a = A[i - 1], b = B[i - 1];
S[Perm[a]].update(i, Perm[b]);
S[Perm[b]].update(i, Perm[a]);
}
}
const int INF = 1e9;
int question(int x, int y, int v) {
vi A = S[Perm[x]].list(v), B = S[Perm[y]].list(v);
vi VA, VB;
for(auto it : A)
VA.push_back(H0[it].first);
for(auto it : B)
VB.push_back(H0[it].first);
int p1 = 0, p2 = 0;
int re = INF;
while(p1 < VA.size() && p2 < VB.size()) {
re = min(re, abs(VB[p2] - VA[p1]));
if(VA[p1] < VB[p2]) ++p1;
else ++p2;
}
return re;
}
Compilation message
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:161:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
161 | while(p1 < VA.size() && p2 < VB.size()) {
| ~~~^~~~~~~~~~~
potion.cpp:161:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
161 | while(p1 < VA.size() && p2 < VB.size()) {
| ~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1848 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2116 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1840 KB |
Output is correct |
| 4 |
Correct |
33 ms |
17276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
331 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
352 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
23868 KB |
Output is correct |
| 2 |
Correct |
98 ms |
22608 KB |
Output is correct |
| 3 |
Correct |
99 ms |
20380 KB |
Output is correct |
| 4 |
Correct |
196 ms |
29696 KB |
Output is correct |
| 5 |
Correct |
200 ms |
29840 KB |
Output is correct |
| 6 |
Correct |
98 ms |
16932 KB |
Output is correct |
| 7 |
Correct |
191 ms |
27316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1848 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2116 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1840 KB |
Output is correct |
| 5 |
Correct |
33 ms |
17276 KB |
Output is correct |
| 6 |
Runtime error |
331 ms |
262144 KB |
Execution killed with signal 9 |
| 7 |
Halted |
0 ms |
0 KB |
- |
