#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
struct SegmentTreeMin
{
vector<pair<int64_t, int64_t>> t;
vector<int64_t> z;
int64_t l, n;
SegmentTreeMin(vector<int> v)
{
n = v.size();
l = 1 << (32 - __builtin_clz(v.size()));
t = vector<pair<int64_t, int64_t>>(2 * l, make_pair(INT64_MAX, INT64_MAX));
z = vector<int64_t>(2 * l, 0);
for (int64_t i = l; i < l + n; i++)
t[i] = {v[i - l], i - l};
for (int64_t i = l - 1; i; i--)
t[i] = min(t[2 * i], t[2 * i + 1]);
}
void propagate(int64_t k)
{
t[2 * k].first -= z[k], t[2 * k + 1].first -= z[k];
z[2 * k] += z[k], z[2 * k + 1] += z[k];
z[k] = 0;
}
private:
void decrement(int64_t i, int64_t j, int64_t k, int64_t x, int64_t y)
{
if (y <= i || x >= j)
return;
if (i <= x && y <= j)
{
t[k].first--;
z[k]++;
}
else
{
propagate(k);
decrement(i, j, 2 * k, x, (x + y) / 2);
decrement(i, j, 2 * k + 1, (x + y) / 2, y);
t[k] = min(t[2 * k], t[2 * k + 1]);
}
}
pair<int64_t, int64_t> range_min(int64_t i, int64_t j, int64_t k, int64_t x, int64_t y)
{
if (y <= i || x >= j)
return make_pair(INT64_MAX, INT64_MAX);
if (i <= x && y <= j)
return t[k];
propagate(k);
return min(range_min(i, j, 2 * k, x, (x + y) / 2),
range_min(i, j, 2 * k + 1, (x + y) / 2, y));
}
public:
void decrement(int64_t i, int64_t j)
{
if (i < 0)
i += n;
if (j < 0)
j += n;
if (i > j)
{
decrement(0, j, 1, 0, l);
decrement(i, n, 1, 0, l);
}
else
decrement(i, j, 1, 0, l);
}
pair<int64_t, int64_t> range_min(int64_t i, int64_t j)
{
if (i < 0)
i += n;
if (j < 0)
j += n;
if (i > j)
{
return min(range_min(0, j, 1, 0, l),
range_min(i, n, 1, 0, l));
}
else
return range_min(i, j, 1, 0, l);
}
void set_inf(int64_t i, int64_t k, int64_t x, int64_t y)
{
if (y - x == 1)
{
t[k] = {INT64_MAX, INT64_MAX};
return;
}
if (i < (x + y) / 2)
set_inf(i, 2 * k, x, (x + y) / 2);
else
set_inf(i, 2 * k + 1, (x + y) / 2, y);
t[k] = min(t[2 * k], t[2 * k + 1]);
}
};
vector<int64_t> h;
vector<vector<int64_t>> left_anc, right_anc, left_d, right_d;
int64_t k_;
int64_t find_height(int64_t i, int64_t k, SegmentTreeMin &tree, int64_t p)
{
auto [pre, j] = tree.range_min(i - k + 1, i);
while (!pre)
{
p = find_height(j, k, tree, p);
tie(pre, j) = tree.range_min(i - k + 1, i);
}
h[i] = p++;
tree.decrement(i - k + 1, i);
tree.set_inf(i, 1, 0, tree.l);
return p;
}
void init(int k, std::vector<int> r)
{
k_ = k;
h = vector<int64_t>(r.size());
SegmentTreeMin tree(r);
int64_t p = 0;
while (p < r.size())
p = find_height(tree.range_min(0, r.size()).second, k, tree, p);
set<pair<int64_t, int64_t>> s;
left_anc = vector<vector<int64_t>>(r.size());
right_anc = vector<vector<int64_t>>(r.size());
left_d = vector<vector<int64_t>>(r.size());
right_d = vector<vector<int64_t>>(r.size());
for (size_t i = 0; i + 1 < k; i++)
s.emplace(h[i], i);
for (int64_t i = 0; i < r.size(); i++)
{
int64_t const j = (i + k - 1) % r.size();
auto it = s.upper_bound(make_pair(h[j], j));
if (it != s.end())
left_anc[j].push_back(it->second), left_d[j].push_back(abs(j - it->second));
s.emplace(h[j], j);
s.erase(make_pair(h[i], i));
it = s.upper_bound(make_pair(h[i], i));
if (it != s.end())
right_anc[i].push_back(it->second), right_d[i].push_back(abs(it->second - i));
}
for (int64_t j = 1; j <= 32 - __builtin_clz(r.size()); j++)
for (size_t i = 0; i < r.size(); i++)
{
if (left_anc[i].size() == j && left_anc[left_anc[i][j - 1]].size() == j)
{
left_anc[i][j] = left_anc[left_anc[i][j - 1]][j - 1];
left_d[i][j] = left_d[i][j - 1] + left_d[left_anc[i][j - 1]][j - 1];
}
if (right_anc[i].size() == j && right_anc[right_anc[i][j - 1]].size() == j)
{
right_anc[i][j] = right_anc[right_anc[i][j - 1]][j - 1];
right_d[i][j] = right_d[i][j - 1] + right_d[right_anc[i][j - 1]][j - 1];
}
}
}
bool plant_is_greater(
int64_t x, int64_t y, vector<vector<int64_t>> const &anc,
vector<vector<int64_t>> const &dis, bool dir)
{
int64_t d = (y - x) * (dir ? 1 : -1);
if (d < 0)
d += anc.size();
for (int64_t i = (int64_t)anc[x].size() - 1; i >= 0; i--)
if (dis[x][i] <= d)
{
d -= dis[x][i];
x = anc[x][i];
}
return abs(x - y) < k_ && h[x] <= h[y];
}
int compare_plants(int x, int y)
{
if (x == y)
return 0;
if (plant_is_greater(x, y, left_anc, left_d, 1))
return 1;
if (plant_is_greater(x, y, right_anc, right_d, 0))
return 1;
if (plant_is_greater(y, x, left_anc, left_d, 1))
return -1;
if (plant_is_greater(y, x, right_anc, right_d, 0))
return -1;
return 0;
}
Compilation message
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:133:14: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | while (p < r.size())
| ~~^~~~~~~~~~
plants.cpp:141:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
141 | for (size_t i = 0; i + 1 < k; i++)
| ~~~~~~^~~
plants.cpp:144:27: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for (int64_t i = 0; i < r.size(); i++)
| ~~^~~~~~~~~~
plants.cpp:160:36: warning: comparison of integer expressions of different signedness: 'std::vector<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
160 | if (left_anc[i].size() == j && left_anc[left_anc[i][j - 1]].size() == j)
| ~~~~~~~~~~~~~~~~~~~^~~~
plants.cpp:160:80: warning: comparison of integer expressions of different signedness: 'std::vector<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
160 | if (left_anc[i].size() == j && left_anc[left_anc[i][j - 1]].size() == j)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
plants.cpp:165:37: warning: comparison of integer expressions of different signedness: 'std::vector<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
165 | if (right_anc[i].size() == j && right_anc[right_anc[i][j - 1]].size() == j)
| ~~~~~~~~~~~~~~~~~~~~^~~~
plants.cpp:165:83: warning: comparison of integer expressions of different signedness: 'std::vector<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
165 | if (right_anc[i].size() == j && right_anc[right_anc[i][j - 1]].size() == j)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
224 KB |
Output is correct |
| 6 |
Incorrect |
49 ms |
3040 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
51 ms |
3548 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
224 KB |
Output is correct |
| 6 |
Incorrect |
49 ms |
3040 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
