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>
#define pii pair<int,int>
#define pb push_back
#define s second
#define f first
using namespace std;
const int N = 1e5 + 5;
const int BL = 50;
vector <pii> v[N];
int h[N],n;
vector <vector <int>> vec[N];
void init(int N, int D, int H[]) {
n = N;
for (int i=1;i<=n;i++)
h[i] = H[i - 1];
}
void curseChanges(int U, int A[], int B[]) {
for (int i = 1; i <= U; i++){
int a = A[i - 1],b = B[i - 1];
a+=1; b+=1;
v[a].pb({i,b});
v[b].pb({i,a});
}
set <int> st;
for (int i = 1; i <= n; i++){
st.clear();
for (int j = 0; j < v[i].size(); j++){
int y = v[i][j].s;
if (st.count(y)){
st.erase(y);
}else {
st.insert(y);
}
if (j % BL == 0){
vector <int> vv;
for (int t: st) vv.pb(t);
vec[i].pb(vv);
}
}
}
}
void getneighbours(vector <int> &vv,int x,int D){
int l = 0,r = v[x].size() - 1,res=-1;
while (l <= r){
int mid = (l + r) >> 1;
if (v[x][mid].f <= D){
res=mid;
l=mid+1;
}else{
r=mid-1;
}
}
if (res==-1) return;
int id = res/BL;
set <int> st;
for (int j = id * BL + 1; j <= res; j++){
int y = v[x][j].s;
if (st.count(y)){
st.erase(y);
}else {
st.insert(y);
}
}
for (int k: vec[x][id]){
if (st.count(k)){
st.erase(k);
}else{
vv.pb(h[k]);
}
}
for (int y: st)
vv.pb(h[y]);
sort(vv.begin(),vv.end());
}
int question(int x, int y, int days) {
x += 1; y += 1;
int ans = 1e9,l1 = 0,l2 = 0;
vector <int> nx,ny;
getneighbours(nx,x,days);
getneighbours(ny,y,days);
while (l1 < nx.size() && l2 < ny.size()){
ans = min(ans,abs(nx[l1] - ny[l2]));
if (nx[l1] < ny[l2]) ++l1;
else ++l2;
}
return ans;
}
Compilation message (stderr)
potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:32:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (int j = 0; j < v[i].size(); j++){
| ~~^~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:93:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | while (l1 < nx.size() && l2 < ny.size()){
| ~~~^~~~~~~~~~~
potion.cpp:93:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | while (l1 < nx.size() && l2 < ny.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... |