#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
#define X first
#define Y second
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int rand(int a, int b) {
return uniform_int_distribution<int>(a, b)(rng);
}
struct node {
int val, p;
node *l, *r;
node(int v) {
val = v;
p = rand(INT_MIN, INT_MAX - 1);
}
node(node *n) {
val = n->val;
p = n->p;
l = n->l;
r = n->r;
}
node* attach(node *l, node *r) {
this->l = l;
this->r = r;
return this;
}
};
int pr(node *n) {
if(n == nullptr)
return INT_MAX;
return n->p;
}
node* clear(node *n) {
n->l = n->r = nullptr;
return n;
}
struct treap {
vector<node*> root;
vector<int> day;
treap() {
day.push_back(0);
root.push_back(nullptr);
}
void print(node *n) {
if(n == nullptr)
return ;
cout << "[ ";
print(n->l);
cout << " ] (" << n->val << ") [ ";
print(n->r);
cout << " ]";
}
void print() {
print(root.back());
cout << endl;
}
void new_root(int d) {
day.push_back(d);
if(root.empty())
root.push_back(nullptr);
else
root.push_back(root.back());
}
node* merge(node *a, node *b) {
if(a == nullptr)
return b;
if(b == nullptr)
return a;
if(a->p > b->p)
swap(a, b);
a = new node(a);
if(b->val < a->val)
return a->attach(merge(a->l, b), a->r);
return a->attach(a->l, merge(a->r, b));
}
void insert(int x, int d) {
new_root(d);
root.back() = merge(root.back(), new node(x));
//~ print();
}
node* erase(node *n, node *x) {
if(n->val == x->val)
return merge(n->l, n->r);
if(x->val < n->val)
return (new node(n))->attach(erase(n->l, x), n->r);
else
return (new node(n))->attach(n->l, erase(n->r, x));
}
void erase(int x, int d) {
new_root(d);
root.back() = erase(root.back(), new node(x));
//~ print();
}
vector<int> hlp;
void dfs(node *n) {
if(n == nullptr)
return ;
dfs(n->l);
hlp.push_back(n->val);
dfs(n->r);
}
vector<int> get_all(int t) {
int r = prev(upper_bound(day.begin(), day.end(), t)) - day.begin();
hlp.clear();
dfs(root[r]);
return hlp;
}
};
treap T[100007];
int n, d, u, q;
int h[100007];
set<ii> S;
int closest(vector<int> A, vector<int> B) {
int res = 1e9;
int j = 0;
for(int i = 0 ; i < A.size() ; i++) {
while(j < B.size() && B[j] < A[i])
j++;
if(j < B.size())
res = min(res, abs(A[i] - B[j]));
if(j - 1 >= 0)
res = min(res, abs(A[i] - B[j - 1]));
}
return res;
}
int main() {
scanf("%d%d%d%d", &n, &d, &u, &q);
for(int i = 0 ; i < n ; i++)
scanf("%d", &h[i]);
for(int i = 0 ; i < u ; i++) {
int a, b;
scanf("%d%d", &a, &b);
if(a > b) swap(a, b);
if(S.count({a, b})) {
T[a].erase(h[b], i + 1);
T[b].erase(h[a], i + 1);
S.erase({a, b});
} else {
T[a].insert(h[b], i + 1);
T[b].insert(h[a], i + 1);
S.insert({a, b});
}
}
while(q--) {
int x, y, v;
scanf("%d%d%d", &x, &y, &v);
printf("%d\n", closest(T[x].get_all(v), T[y].get_all(v)));
fflush(stdout);
}
return 0;
}
Compilation message
potion.cpp: In function 'int closest(std::vector<int>, std::vector<int>)':
potion.cpp:149:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for(int i = 0 ; i < A.size() ; i++) {
| ~~^~~~~~~~~~
potion.cpp:150:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | while(j < B.size() && B[j] < A[i])
| ~~^~~~~~~~~~
potion.cpp:152:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | if(j < B.size())
| ~~^~~~~~~~~~
potion.cpp: In function 'int main()':
potion.cpp:161:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
161 | scanf("%d%d%d%d", &n, &d, &u, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:163:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
163 | scanf("%d", &h[i]);
| ~~~~~^~~~~~~~~~~~~
potion.cpp:166:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
166 | scanf("%d%d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~
potion.cpp:182:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
182 | scanf("%d%d%d", &x, &y, &v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
/tmp/cc3BhLr7.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cciHjNoZ.o:potion.cpp:(.text.startup+0x0): first defined here
/tmp/cc3BhLr7.o: In function `main':
grader.cpp:(.text.startup+0xde): undefined reference to `init(int, int, int*)'
grader.cpp:(.text.startup+0x167): undefined reference to `curseChanges(int, int*, int*)'
grader.cpp:(.text.startup+0x1c1): undefined reference to `question(int, int, int)'
collect2: error: ld returned 1 exit status
