#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int n, h[maxn];
void init(int N, int D, int H[])
{
n = N;
for (int i = 0; i < N; i ++)
{
h[i] = H[i];
}
}
vector < pair < int, int > > tree[4 * maxn];
void update_range(int root, int left, int right, int qleft, int qright, pair < int, int > tie)
{
//if (root == 1)
// cout << qleft << " " << qright << " " << tie.first << " " << tie.second << endl;
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
tree[root].push_back(tie);
return;
}
int mid = (left + right) / 2;
update_range(root * 2, left, mid, qleft, qright, tie);
update_range(root * 2 + 1, mid + 1, right, qleft, qright, tie);
}
unordered_map < int, int > st[4 * maxn];
void build_tree(int root, int left, int right)
{
sort(tree[root].begin(), tree[root].end());
for (int i = 0; i < tree[root].size(); i ++)
{
if (i == 0 || tree[root][i].first != tree[root][i - 1].first)
st[root][tree[root][i].first] = i;
}
if (left == right)
return;
int mid = (left + right) / 2;
build_tree(root * 2, left, mid);
build_tree(root * 2 + 1, mid + 1, right);
}
pair < int, int > edge[maxn];
int u;
map < pair < int, int >, int > act;
void curseChanges(int U, int A[], int B[])
{
u = U;
for (int i = 0; i < U; i ++)
{
edge[i] = {A[i], B[i]};
}
exit(0);
for (int j = 0; j < U; j ++)
{
int a = edge[j].first, b = edge[j].second;
pair < int, int > lf = {a, b}, rf = {b, a};
if (act[lf] == 0)
{
act[lf] = j + 1;
}
else
{
update_range(1, 0, U, act[lf], j, lf);
act[lf] = 0;
}
if (act[rf] == 0)
{
act[rf] = j + 1;
}
else
{
update_range(1, 0, U, act[rf], j, rf);
act[rf] = 0;
}
}
for (auto it : act)
{
if (it.second == 0)
continue;
update_range(1, 0, U, it.second, U, it.first);
}
build_tree(1, 0, U);
///exit(0);
}
vector < int > my_set;
void query(int root, int left, int right, int pos, int val)
{
///cout << root << " " << left << " " << right << " " << pos << " " << val << endl;
int pt = st[root][val];
while(pt < tree[root].size() && tree[root][pt].first == val)
{
my_set.push_back(tree[root][pt].second);
pt ++;
}
if (left == right)
return;
int mid = (left + right) / 2;
if (pos <= mid)
query(root * 2, left, mid, pos, val);
else
query(root * 2 + 1, mid + 1, right, pos, val);
}
int question(int x, int y, int v)
{
vector < int > hx, hy;
my_set.clear();
query(1, 0, u, v, x);
for (int cur : my_set)
hx.push_back(h[cur]);
my_set.clear();
query(1, 0, u, v, y);
for (int cur : my_set)
hy.push_back(h[cur]);
///cout << hx.size() << " : " << hy.size() << endl;
sort(hx.begin(), hx.end());
sort(hy.begin(), hy.end());
int ans = 1e9;
int pt = 0;
for (int i = 0; i < hx.size(); i ++)
{
while(pt < hy.size() && hy[pt] <= hx[i])
pt ++;
if (pt != 0)
ans = min(ans, abs(hx[i] - hy[pt - 1]));
if (pt != hy.size())
ans = min(ans, abs(hx[i] - hy[pt]));
}
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 5 5
*/
Compilation message
potion.cpp: In function 'void build_tree(int, int, int)':
potion.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int i = 0; i < tree[root].size(); i ++)
| ~~^~~~~~~~~~~~~~~~~~~
potion.cpp: In function 'void query(int, int, int, int, int)':
potion.cpp:121:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | while(pt < tree[root].size() && tree[root][pt].first == val)
| ~~~^~~~~~~~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:154:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | for (int i = 0; i < hx.size(); i ++)
| ~~^~~~~~~~~~~
potion.cpp:156:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
156 | while(pt < hy.size() && hy[pt] <= hx[i])
| ~~~^~~~~~~~~~~
potion.cpp:161:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
161 | if (pt != hy.size())
| ~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
64344 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
64344 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
67120 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
67688 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
65108 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
64344 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
