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;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FOR(i, n, 0, 1)
#define pb push_back
#define ff first
#define ss second
vector<int> h;
const int INF = (int)2e9 + 15;
struct segtree{
vector<vector<array<int, 2>>> tree;
vector<int> lch, rch;
int n;
int create_new(){
tree.pb(vector<array<int, 2>>());
lch.pb(-1); rch.pb(-1);
return (int)tree.size() - 1;
}
segtree(){}
segtree(int sz){
n = 1;
while(n < sz) n *= 2;
create_new();
}
void upd(int l, int r, array<int, 2> val){upd0(l, r, 0, n, 0, val);}
void upd0(int l, int r, int beg, int end, int v, array<int, 2> val){
if(beg >= l && end <= r){
tree[v].pb(val);
return;
}
if(beg >= r || end <= l)
return;
int mid = (beg + end) >> 1;
if(lch[v] == -1 && !(beg >= r || mid <= l)){
int id = create_new();
lch[v] = id;
upd0(l, r, beg, mid, lch[v], val);
}
else if(!(beg >= r || mid <= l)){
upd0(l, r, beg, mid, lch[v], val);
}
if(rch[v] == -1 && !(mid >= r || end <= l)){
int id = create_new();
rch[v] = id;
upd0(l, r, mid, end, rch[v], val);
}
else if(!(mid >= r || end <= l)){
upd0(l, r, mid, end, rch[v], val);
}
}
void query0(int pos, int beg, int end, int v, vector<int> &res, int val){
if(beg > pos || end <= pos)
return;
array<int, 2> ts = {val, -INF};
int id = lower_bound(tree[v].begin(), tree[v].end(), ts) - tree[v].begin();
FOR(i, id, tree[v].size(), 1){
if(tree[v][i][0] != val)
break;
res.pb(h[tree[v][i][1]]);
}
if(beg == pos && end == pos + 1)
return;
int mid = (beg + end) >> 1;
if(lch[v] != -1)
query0(pos, beg, mid, lch[v], res, val);
if(rch[v] != -1)
query0(pos, mid, end, rch[v], res, val);
}
};
segtree st;
int n;
void init(int N, int d, int H[]) {
n = N;
REP(i, N)
h.pb(H[i]);
}
void curseChanges(int U, int A[], int B[]) {
st = segtree(U + 5);
map<array<int, 2>, int> edges;
FOR(i, 1, U + 1, 1){
array<int, 2> tm = {A[i - 1], B[i - 1]};
if(tm[0] > tm[1]) swap(tm[0], tm[1]);
if(edges.find(tm) != edges.end()){
st.upd(edges[tm], i, tm);
edges.erase(tm);
}
else{
edges[tm] = i;
}
}
for(auto x : edges){
auto tm = x.ff;
st.upd(x.ss, U + 1, tm);
}
REP(i, st.tree.size()){
int up = st.tree[i].size();
REP(j, up){
auto x = st.tree[i][j];
swap(x[0], x[1]);
st.tree[i].pb(x);
}
sort(st.tree[i].begin(), st.tree[i].end());
}
}
int question(int x, int y, int v) {
vector<int> f;
vector<int> s;
st.query0(v, 0, st.n, 0, f, x);
st.query0(v, 0, st.n, 0, s, y);
if(f.empty() || s.empty()){
return (int)1e9;
}
sort(f.begin(), f.end());
sort(s.begin(), s.end());
int ans = (int)1e9 + 5;
for(int x : f){
int id = lower_bound(s.begin(), s.end(), x) - s.begin();
if(id > 0){
ans = min(ans, abs(x - s[id - 1]));
}
if(id < (int)s.size()){
ans = min(ans, abs(x - s[id]));
}
}
return ans;
}
Compilation message (stderr)
potion.cpp: In member function 'void segtree::query0(int, int, int, int, std::vector<int>&, int)':
potion.cpp:3:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
| ^
potion.cpp:58:9: note: in expansion of macro 'FOR'
58 | FOR(i, id, tree[v].size(), 1){
| ^~~
potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:3:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::array<int, 2> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
| ^
potion.cpp:5:19: note: in expansion of macro 'FOR'
5 | #define REP(i, n) FOR(i, 0, n, 1)
| ^~~
potion.cpp:99:5: note: in expansion of macro 'REP'
99 | REP(i, st.tree.size()){
| ^~~
# | 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... |