#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
struct Node{
int subsz= 0, id = -1;
int l = -1, r = -1;
Node(){};
Node(int i, int sz):subsz(sz), id(i){};
};
const int INF = 1e6+1;
vector<int> ids;
struct pSet{
vector<pii> events;
vector<Node> tree;
pSet(){
tree.push_back(create(-1, -1));
events.push_back({0, 0});
}
void set(int t, int id, int v){
events.push_back({t, update(id, v, 0, INF, events.back().second)});
}
vector<int> get_inside_at(int t){
int cur= 0;
for(int step = (1<<22); step>=1; step/=2){
if(cur+step<events.size()){
if(events[cur+step].first<=t){
cur+=step;
}
}
}
get(0, INF, events[cur].second);
vector<int> res;
swap(res, ids);
return res;
}
Node create(int lid, int rid){
Node res;
res.subsz = 0;
res.l = lid;
res.r = rid;
if(res.l!=-1){
res.subsz += tree[res.l].subsz;
}
if(res.r!=-1){
res.subsz += tree[res.r].subsz;
}
return res;
}
int update(int id, int v, int lt, int rt, int t){
Node res;
if(lt==rt){
res = Node(id, v);
}
else{
int mid = (lt+rt)/2;
int lid= -1, rid= -1;
if(t!=-1){
lid= tree[t].l;
rid =tree[t].r;
}
if(id<=mid){
res = create(update(id, v, lt, mid, lid), rid);
}
else{
res = create(lid, update(id, v, mid+1, rt, rid));
}
}
if(res.subsz>0|| (lt==0 && rt==INF)){
tree.push_back(res);
return tree.size()-1;
}
else{
return -1;
}
}
void get( int lt, int rt, int t){
if(lt==rt){
if(tree[t].subsz == 1){
ids.push_back(tree[t].id);
}
}
else{
int mid =(lt+rt)/2;
if(tree[t].l!=-1){
get(lt, mid, tree[t].l);
}
if(tree[t].r!=-1){
get(mid+1, rt, tree[t].r);
}
}
}
};
vector<pSet> vs;
vector<int> h;
set<pii> cur;
vector<int> redir;
int n;
void init(int N, int D, int H[]) {
vs.resize(N);
h.resize(N);
redir.resize(N);
vector<int> order(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());
n= N;
for(int i = 0; i<n; i++){
redir[order[i]] = i;
}
}
void curseChanges(int U, int A[], int B[]) {
for(int i = 0; i<U; i++){
int a= redir[A[i]], b= redir[B[i]];
if((cur.find({a, b})!=cur.end()) || (cur.find({b, a})!=cur.end())){
cur.erase({a, b});
vs[a].set(i+1, b, 0);
vs[b].set(i+1, a, 0);
}
else{
cur.insert({a, b});
vs[a].set(i+1, b, 1);
vs[b].set(i+1, a, 1);
}
}
}
int dist(vector<int>& a, vector<int>& b){
if(a.size() == 0 || b.size() == 0){
return 1e9;
}
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;
}
int question(int x, int y, int v) {
auto vx = vs[redir[x]].get_inside_at(v);
for(int& e: vx){
e = h[e];
}
auto vy = vs[redir[y]].get_inside_at(v);
for(int& e: vy){
e = h[e];
}
return dist(vx, vy);
}
Compilation message
potion.cpp: In member function 'std::vector<int> pSet::get_inside_at(int)':
potion.cpp:31: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]
31 | if(cur+step<events.size()){
| ~~~~~~~~^~~~~~~~~~~~~~
potion.cpp: In function 'int dist(std::vector<int>&, std::vector<int>&)':
potion.cpp:161:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
161 | while(ia<a.size()-1 || ib<b.size()-1){
| ~~^~~~~~~~~~~
potion.cpp:161:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
161 | while(ia<a.size()-1 || ib<b.size()-1){
| ~~^~~~~~~~~~~
potion.cpp:162:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | if(ia==a.size()-1){
| ~~^~~~~~~~~~~~
potion.cpp:165:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
165 | else if(ib==b.size()-1){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1568 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1708 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1552 KB |
Output is correct |
| 4 |
Correct |
34 ms |
13604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1080 ms |
215828 KB |
Output is correct |
| 2 |
Correct |
1032 ms |
215528 KB |
Output is correct |
| 3 |
Incorrect |
254 ms |
105840 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
976 ms |
215312 KB |
Output is correct |
| 2 |
Incorrect |
390 ms |
122156 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
11480 KB |
Output is correct |
| 2 |
Incorrect |
17 ms |
8896 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1568 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1708 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1552 KB |
Output is correct |
| 5 |
Correct |
34 ms |
13604 KB |
Output is correct |
| 6 |
Correct |
1080 ms |
215828 KB |
Output is correct |
| 7 |
Correct |
1032 ms |
215528 KB |
Output is correct |
| 8 |
Incorrect |
254 ms |
105840 KB |
Incorrect |
| 9 |
Halted |
0 ms |
0 KB |
- |
