#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
typedef complex<int> point;
const int INF = 1e9;
int dist(vector<int>& a, vector<int>& b){
if(a.size() == 0 || b.size() == 0){
return INF;
}
int ia =0, ib = 0;
int res= abs(a[0]-b[0]);
while(ia<a.size()-1 || ib<b.size()-1){
if(ia==a.size()-1){
ib++;
}
else if(ib==b.size()-1){
ia++;
}
else if(a[ia]<=b[ib]){
ia++;
}
else{
ib++;
}
res = min(res, abs(a[ia]-b[ib]));
}
return res;
}
struct Event{
int date;
vector<int> list;
int change;
Event(int t,int v): date(t), change(v){};
Event(int t, vector<int> v): date(t){
list =v;
};
};
vector<int> apply(vector<int>& a, vector<int>&ev){
sort(ev.begin(), ev.end());
vector<int> res;
auto add =[&](int v){
if(res.size()>0 && res.back() == v){
res.pop_back();
}
else{
res.push_back(v);
}
};
int aid = 0;
int eid = 0;
while(aid<a.size() || eid<ev.size()){
if(eid>=ev.size()){
add(a[aid]);
aid++;
}
else if(aid>=a.size()){
add(ev[eid]);
eid++;
}
else{
if(a[aid]<=ev[eid]){
add(a[aid]);
aid++;
}
else{
add(ev[eid]);
eid++;
}
}
}
return res;
}
vector<vector<int>> vs;
vector<int> h;
set<pii> cur;
vector<vector<Event>> events;
vector<vector<int>> backed_up;
vector<int> order;
vector<int> redir;
int n;
const int TR = 10;
void init(int N, int D, int H[]) {
n = N;
vs.resize(N);
h.resize(N);
events.resize(N);
backed_up.resize(N);
redir.resize(n);
order.resize(n);
for(int i = 0; i<N; i++){
h[i] = H[i];
order[i] = i;
}
auto cmp =[&](int a, int b){
return h[a]<h[b];
};
sort(order.begin(),order.end(), cmp);
sort(h.begin(), h.end());
for(int i = 0; i<n; i++){
redir[order[i]] = i;
}
}
void curseChanges(int U, int A[], int B[]) {
for(int i = 0; i<n; i++){
events[i].push_back(Event(0, vector<int>()));
}
auto p_event = [&](int id,int t, int ev){
backed_up[id].push_back(ev);
if(backed_up[id].size()==TR){
events[id].push_back(Event(t, apply(events[id][events[id].size()-TR].list,backed_up[id])));
backed_up[id].clear();
}
else{
events[id].push_back(Event(t, ev));
}
};
for(int i = 0; i<U; i++){
int a= A[i], b= B[i];
if(cur.find({a, b})!=cur.end()){
cur.erase({a, b});
}
else if(cur.find({b, a})!=cur.end()){
cur.erase({b, a});
}
else{
cur.insert({a, b});
}
p_event(a, i+1, b);
p_event(b, i+1, a);
}
}
int get_last(int id, int t){
int cur= 0;
for(int step = (1<<18); step>=1; step/=2){
if(cur+step<events[id].size()){
if(events[id][cur+step].date<=t){
cur+=step;
}
}
}
return cur;
}
vector<int> reconstruct(int id, int eid){
Event base = events[id][(eid/TR) * TR];
vector<int> others;
for(int i = 1; i<=eid%TR; i++){
others.push_back(events[id][(eid/TR) * TR + i].change);
}
return apply(base.list, others);
}
int question(int x, int y, int v) {
x= redir[x];
y= redir[y];
auto xm =reconstruct(x, get_last(x, v));
auto ym = reconstruct(y, get_last(y, v));
for(int& e: xm){
e= h[e];
}
for(int& e: ym){
e= h[e];
}
return dist(xm, ym);
}
Compilation message
potion.cpp: In function 'int dist(std::vector<int>&, std::vector<int>&)':
potion.cpp:17:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | while(ia<a.size()-1 || ib<b.size()-1){
| ~~^~~~~~~~~~~
potion.cpp:17:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | while(ia<a.size()-1 || ib<b.size()-1){
| ~~^~~~~~~~~~~
potion.cpp:18:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | if(ia==a.size()-1){
| ~~^~~~~~~~~~~~
potion.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | else if(ib==b.size()-1){
| ~~^~~~~~~~~~~~
potion.cpp: In function 'std::vector<int> apply(std::vector<int>&, std::vector<int>&)':
potion.cpp:61:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | while(aid<a.size() || eid<ev.size()){
| ~~~^~~~~~~~~
potion.cpp:61:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | while(aid<a.size() || eid<ev.size()){
| ~~~^~~~~~~~~~
potion.cpp:63:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | if(eid>=ev.size()){
| ~~~^~~~~~~~~~~
potion.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | else if(aid>=a.size()){
| ~~~^~~~~~~~~~
potion.cpp: In function 'int get_last(int, int)':
potion.cpp:155:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | if(cur+step<events[id].size()){
| ~~~~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
792 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
396 ms |
51932 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
413 ms |
51556 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
4012 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
