#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
namespace {
using namespace std;
}
typedef pair<int,int> pii;
struct Node {
vector<int> lz;
int lft,rt;
Node():lft(0),rt(0) {}
};
namespace {
vector<Node> tree;
vector<vector<int>> lst;
int n,d,u;
vector<int> h;
int *AA=nullptr,*BB=nullptr;
}
int add() {
tree.push_back(Node());
return tree.size()-1;
}
void update(int L,int R,int val,int l,int r,int id) {
if (L<=l and r<=R) {
tree[id].lz.push_back(val);
return;
}
int mid=l+r>>1;
if (L<=mid) {
if (!tree[id].lft) tree[id].lft = add();
update(L,R,val,l,mid,tree[id].lft);
}
if (mid<R) {
if (!tree[id].rt) tree[id].rt = add();
update(L,R,val,mid+1,r,tree[id].rt);
}
}
void query(int t,vector<int> &h,int l,int r,int id) {
for (int i:tree[id].lz) h.push_back(i);
int mid=l+r>>1;
if (t<=mid) {
if (tree[id].lft) query(t,h,l,mid,tree[id].lft);
} else {
if (tree[id].rt) query(t,h,mid+1,r,tree[id].rt);
}
}
void init(int N, int D, int H[]) {
n=N;d=D;
h.resize(n);
lst.resize(n);
for (int i=0;i<n;i++) h[i]=H[i];
}
void curseChanges(int U, int A[], int B[]) {
AA=A;BB=B;
u=U;
tree.resize(n,Node());
map<pii,int> tm;
for (int i=0;i<u;i++) {
if (A[i]>B[i]) swap(A[i],B[i]);
if (tm[pair(A[i],B[i])]==0) tm[pair(A[i],B[i])]=i+1;
else {
update(tm[pair(A[i],B[i])],i,h[B[i]],1,u,A[i]);
update(tm[pair(A[i],B[i])],i,h[A[i]],1,u,B[i]);
tm[pair(A[i],B[i])]=0;
}
}
for (auto [p,t]:tm) {
if (t==0) continue;
lst[p.F].push_back(t);
lst[p.S].push_back(t);
}
for (int i=0;i<n;i++) {
sort(all(lst[i]));
// cout<<i<<" :\n";
// for (auto [a,b]:lst[i]) cout<<a<<" "<<b<<"\n";
}
}
int question(int x, int y, int v) {
vector<int> a,b;
query(v,a,1,u,x);
query(v,b,1,u,y);
// for (int i:a) cout<<i<<" ";
// cout<<"a\n";
// for (int i:b) cout<<i<<" ";
// cout<<"b\n"<<flush;
auto it = upper_bound(all(lst[x]),v);
for (auto i=lst[x].begin();i!=it;i++) a.push_back((AA[*i-1]==x?h[BB[*i-1]]:h[AA[*i-1]]));
it = upper_bound(all(lst[y]),v);
for (auto i=lst[y].begin();i!=it;i++) b.push_back((AA[*i-1]==y?h[BB[*i-1]]:h[AA[*i-1]]));
sort(all(a));
sort(all(b));
// for (int i:a) cout<<i<<" ";
// cout<<"a\n";
// for (int i:b) cout<<i<<" ";
// cout<<"b\n"<<flush;
int ans=1e9;
for (int i:a) {
auto ptr = lower_bound(all(b),i);
if (ptr!=b.end()) ans=min(ans,abs(*ptr-i));
if (ptr!=b.begin()) ans=min(ans,abs(*prev(ptr)-i));
}
return ans;
}
/*
6 5 11 4
2 42 1000 54 68 234
0 1
2 0
3 4
3 5
3 5
1 3
5 3
0 5
3 0
1 3
3 5
0 3 4 26
3 0 8 0
0 5 5 1000000000
3 0 11 14
*/
Compilation message
potion.cpp: In function 'void update(int, int, int, int, int, int)':
potion.cpp:34:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
34 | int mid=l+r>>1;
| ~^~
potion.cpp: In function 'void query(int, std::vector<int>&, int, int, int)':
potion.cpp:47:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | int mid=l+r>>1;
| ~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
592 KB |
Output is correct |
2 |
Correct |
2 ms |
764 KB |
Output is correct |
3 |
Correct |
2 ms |
592 KB |
Output is correct |
4 |
Correct |
13 ms |
6736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
271 ms |
25796 KB |
Output is correct |
2 |
Correct |
260 ms |
25800 KB |
Output is correct |
3 |
Correct |
343 ms |
151064 KB |
Output is correct |
4 |
Correct |
1306 ms |
166956 KB |
Output is correct |
5 |
Correct |
373 ms |
22744 KB |
Output is correct |
6 |
Correct |
2516 ms |
248344 KB |
Output is correct |
7 |
Correct |
729 ms |
246636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
252 ms |
24876 KB |
Output is correct |
2 |
Correct |
1031 ms |
246160 KB |
Output is correct |
3 |
Correct |
956 ms |
247480 KB |
Output is correct |
4 |
Correct |
1244 ms |
248224 KB |
Output is correct |
5 |
Correct |
307 ms |
33804 KB |
Output is correct |
6 |
Correct |
1326 ms |
248192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
2068 KB |
Output is correct |
2 |
Correct |
76 ms |
14488 KB |
Output is correct |
3 |
Correct |
104 ms |
8380 KB |
Output is correct |
4 |
Correct |
588 ms |
8804 KB |
Output is correct |
5 |
Correct |
606 ms |
4936 KB |
Output is correct |
6 |
Correct |
92 ms |
1876 KB |
Output is correct |
7 |
Correct |
455 ms |
13812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
2 ms |
592 KB |
Output is correct |
3 |
Correct |
2 ms |
764 KB |
Output is correct |
4 |
Correct |
2 ms |
592 KB |
Output is correct |
5 |
Correct |
13 ms |
6736 KB |
Output is correct |
6 |
Correct |
271 ms |
25796 KB |
Output is correct |
7 |
Correct |
260 ms |
25800 KB |
Output is correct |
8 |
Correct |
343 ms |
151064 KB |
Output is correct |
9 |
Correct |
1306 ms |
166956 KB |
Output is correct |
10 |
Correct |
373 ms |
22744 KB |
Output is correct |
11 |
Correct |
2516 ms |
248344 KB |
Output is correct |
12 |
Correct |
729 ms |
246636 KB |
Output is correct |
13 |
Correct |
252 ms |
24876 KB |
Output is correct |
14 |
Correct |
1031 ms |
246160 KB |
Output is correct |
15 |
Correct |
956 ms |
247480 KB |
Output is correct |
16 |
Correct |
1244 ms |
248224 KB |
Output is correct |
17 |
Correct |
307 ms |
33804 KB |
Output is correct |
18 |
Correct |
1326 ms |
248192 KB |
Output is correct |
19 |
Correct |
36 ms |
2068 KB |
Output is correct |
20 |
Correct |
76 ms |
14488 KB |
Output is correct |
21 |
Correct |
104 ms |
8380 KB |
Output is correct |
22 |
Correct |
588 ms |
8804 KB |
Output is correct |
23 |
Correct |
606 ms |
4936 KB |
Output is correct |
24 |
Correct |
92 ms |
1876 KB |
Output is correct |
25 |
Correct |
455 ms |
13812 KB |
Output is correct |
26 |
Correct |
843 ms |
245744 KB |
Output is correct |
27 |
Correct |
1288 ms |
247540 KB |
Output is correct |
28 |
Correct |
1271 ms |
133016 KB |
Output is correct |
29 |
Correct |
1218 ms |
166916 KB |
Output is correct |
30 |
Correct |
2351 ms |
248292 KB |
Output is correct |
31 |
Correct |
1956 ms |
245884 KB |
Output is correct |
32 |
Correct |
2143 ms |
248244 KB |
Output is correct |