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>;
using vi = vector<int>;
namespace AINTpers {
struct nod {
int st, dr, cnt;
int l, r; /// indici pt fii in V
};
vector<nod> V;
int nod_nou(int n) {
V.push_back(nod{0, n - 1, 0, -1, -1});
return int(V.size()) - 1;
}
int nod_nou(int st, int dr) {
V.push_back(nod{st, dr, 0, -1, -1});
return int(V.size()) - 1;
}
int join(int u, int v) {
assert(V[u].dr == V[v].st - 1);
int re = V.size();
V.push_back(V[u]);
V[re].dr = V[v].dr;
V[re].cnt = V[u].cnt + V[v].cnt;
V[re].l = u; V[re].r = v;
return re;
}
int enable(int u, int p) {
if(u == -1) return -1;
if(p < V[u].st || V[u].dr < p) return u;
if(V[u].st == V[u].dr) {
int v = V.size();
V.push_back(V[u]);
V[v].cnt = 1;
return v;
}
int mij = (V[u].st + V[u].dr) / 2;
if(V[u].l == -1) {
V[u].l = nod_nou(V[u].st, mij);
V[u].r = nod_nou(mij + 1, V[u].dr);
}
return join(enable(V[u].l, p), enable(V[u].r, p));
}
int disable(int u, int p) {
if(u == -1) return -1;
if(p < V[u].st || V[u].dr < p) return u;
if(V[u].st == V[u].dr) {
int v = V.size();
V.push_back(V[u]);
V[v].cnt = 0;
return v;
}
int mij = (V[u].st + V[u].dr) / 2;
if(V[u].l == -1) { /// uhhh, nu ar trebuii sa ajungi aici
assert(0);
V[u].l = nod_nou(V[u].st, mij);
V[u].r = nod_nou(mij + 1, V[u].dr);
}
return join(disable(V[u].l, p), disable(V[u].r, p));
}
void enumerate(int u, vi &Re) {
if(u == -1 || !V[u].cnt) return;
if(V[u].st == V[u].dr) {
Re.push_back(V[u].st);
return;
}
enumerate(V[u].l, Re);
enumerate(V[u].r, Re);
}
}
struct SetPers {
int n;
vector<ii> Rad;
set<int> S;
SetPers(int N) : n(N) {
Rad.emplace_back(0, AINTpers::nod_nou(N));
}
void update(int t, int p) {
int r = Rad.back().second;
if(!S.count(p)) {
Rad.push_back({t, AINTpers::enable(r, p)});
S.insert(p);
} else {
Rad.push_back({t, AINTpers::disable(r, p)});
S.erase(p);
}
}
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, Re);
return Re;
}
};
int n;
vi H0;
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]);
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[a].update(i, b);
S[b].update(i, a);
}
}
const int INF = 1e9;
int question(int x, int y, int v) {
vi A = S[x].list(v), B = S[y].list(v);
vector<ii> V;
for(auto it : A)
V.push_back(ii{H0[it], -1});
for(auto it : B)
V.push_back(ii{H0[it], 1});
sort(V.begin(), V.end());
int re = INF;
for(int i = 1; i < V.size(); ++i) {
if(V[i].second != V[i - 1].second)
re = min(re, V[i].first - V[i - 1].first);
}
return re;
}
Compilation message (stderr)
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:144:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for(int i = 1; i < V.size(); ++i) {
| ~~^~~~~~~~~~
# | 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... |