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 {
vi Cnt, L, R;
int nod_nou() {
Cnt.push_back(0);
L.push_back(-1);
R.push_back(-1);
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);
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);
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);
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) return 0;
if(st == dr) return Cnt[u];
int mij = (st + dr) / 2;
if(L[u] == -1) return 0;
if(p <= mij) return stare(L[u], p, st, mij);
return stare(R[u], p, mij + 1, dr);
}
void enumerate(int u, int st, int dr, vi &Re) {
if(u == -1 || !Cnt[u]) return;
if(st == dr) {
Re.push_back(st);
return;
}
enumerate(L[u], st, (st + dr) >> 1, Re);
enumerate(R[u], ((st + dr) >> 1) + 1, dr, Re);
}
}
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, 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:138: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]
138 | 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... |