#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
struct segment_tree{
int hmin[800008], lazy[800008], hmax[800008], heights[200002];
vector<long long> left_child[200002], right_child[200002];
vector<int> m, H;
int n, h, k;
void init(int K, vector<int> M){
n = M.size();
h = n-1;
k = K;
m.clear();
for(int i = 0; i < 800008; i++){
hmin[i] = 0;
lazy[i] = 0;
hmax[i] = -1;
}
for(int i = 0; i < M.size(); i++){
m.push_back(M[i]);
H.push_back(-1);
}
init_heights(1, 1, n);
}
void lazy_update(int N){
lazy[2*N] += lazy[N];
lazy[2*N+1] += lazy[N];
hmin[2*N] += lazy[N];
hmin[2*N+1] += lazy[N];
lazy[N] = 0;
}
void update(int N, int l, int r, int s, int t){
if(l > t || r < s)return;
if(l <= s && r >= t){
lazy[N]--;
hmin[N]--;
return;
}
lazy_update(N);
update(2*N, l, r, s, (s+t)/2);
update(2*N+1, l, r, (s+t)/2+1, t);
hmin[N] = min(hmin[2*N], hmin[2*N+1]);
}
void init_heights(int N, int l, int r){
if(l == r){
hmin[N] = m[r-1];
return;
}
init_heights(2*N, l, (l+r)/2);
init_heights(2*N+1, (l+r)/2+1, r);
hmin[N] = min(hmin[2*N], hmin[2*N+1]);
}
int get_min(int N, int l, int r, int s, int t){
if(l > t || r < s)return 1000000000;
if(l <= s && r >= t)return hmin[N];
lazy_update(N);
return min(get_min(2*N, l, r, s, (s+t)/2), get_min(2*N+1, l, r, (s+t)/2+1, t));
}
int get_max(int N, int l, int r, int s, int t){
if(l > t || r < s)return -1;
if(l <= s && r >= t)return hmax[N];
return max(get_max(2*N, l, r, s, (s+t)/2), get_max(2*N+1, l, r, (s+t)/2+1, t));
}
int left_zero(int N, int l, int r, int s, int t){
if(l > t || r < s)return -1;
if(s == t)return hmin[N] == 0 ? s : -1;
lazy_update(N);
if(l <= s && r >= t){
if(hmin[N]>0)return -1;
if(hmin[2*N+1]>0)return left_zero(2*N, l, r, s, (s+t)/2);
return left_zero(2*N+1, l, r, (s+t)/2+1, t);
}
int z = left_zero(2*N+1, l, r, (s+t)/2+1, t);
return z == -1 ? left_zero(2*N, l, r, s, (s+t)/2) : z;
}
int right_zero(int N, int l, int r, int s, int t){
if(l > t || r < s)return -1;
if(s == t)return hmin[N] == 0 ? t : -1;
lazy_update(N);
if(l <= s && r >= t){
if(hmin[N]>0)return -1;
if(hmin[2*N]>0)return right_zero(2*N+1, l, r, (s+t)/2+1, t);
return right_zero(2*N, l, r, s, (s+t)/2);
}
int z = right_zero(2*N, l, r, s, (s+t)/2);
return z == -1 ? right_zero(2*N+1, l, r, (s+t)/2+1, t) : z;
}
void point_update(int N, int M, int l, int r){
if(l > M || r < M)return;
if(l == r){
hmin[N] = 1000000;
return;
}
lazy_update(N);
point_update(2*N, M, l, (l+r)/2);
point_update(2*N+1, M, (l+r)/2+1, r);
hmin[N] = min(hmin[2*N], hmin[2*N+1]);
}
void extract(int N, int M, int l, int r){
if(l > M || r < M)return;
if(l == r){
while(true)
if(M > 1 && left_zero(1, max(1, M-k), M-1, 1, n) != -1){
extract(1, left_zero(1, max(1, M-k), M-1, 1, n), 1, n);
}
else if(M-k < 1 && left_zero(1, n+M-k, n, 1, n) != -1){
extract(1, left_zero(1, n+M-k, n, 1, n), 1, n);
}
else break;
if(k*2+2<=n){
heights[M-1] = h;
H[h--] = M-1;
}
else H[M-1] = H[h--];
point_update(1, M, 1, n);
if(M > 1)update(1, max(1, M-k), M-1, 1, n);
if(M-k < 1)update(1, n+M-k, n, 1, n);
return;
}
lazy_update(N);
extract(2*N, M, l, (l+r)/2);
extract(2*N+1, M, (l+r)/2+1, r);
hmin[N] = min(hmin[2*N], hmin[2*N+1]);
}
void insert_plant(int N, int M, int z, int l, int r){
if(l > M || r < M)return;
if(l == r){
hmax[N] = z;
return;
}
insert_plant(2*N, M, z, l, (l+r)/2);
insert_plant(2*N+1, M, z, (l+r)/2+1, r);
hmax[N] = max(hmax[2*N], hmax[2*N+1]);
}
void create_child(){
for(int i = 0; i < H.size(); i++){
int M = H[i]+1;
insert_plant(1, M, i, 1, n);
int z;
z = max(M>1?get_max(1, max(1, M-k), M-1, 1, n):-1, M-k<1?get_max(1, n+M-k, n, 1, n):-1);
if(z>-1){
left_child[M-1].push_back(M-1-H[z]>0?M-1-H[z]:n+M-1-H[z]);
while(left_child[M-1].size()<=left_child[(M-1+n-left_child[M-1][left_child[M-1].size()-1])%n].size())
left_child[M-1].push_back(left_child[M-1][left_child[M-1].size()-1]+
left_child[(M-1+n-left_child[M-1][left_child[M-1].size()-1])%n][left_child[M-1].size()-1]);
}
z = max(M<n?get_max(1, M+1, min(M+k, n), 1, n):-1, M+k>n?get_max(1, 1, M+k-n, 1, n):-1);
if(z>-1){
right_child[M-1].push_back(H[z]-M+1>0?H[z]-M+1:n-M+1+H[z]);
while(right_child[M-1].size()<=right_child[(M-1+right_child[M-1][right_child[M-1].size()-1])%n].size())
right_child[M-1].push_back(right_child[M-1][right_child[M-1].size()-1]+
right_child[(M-1+right_child[M-1][right_child[M-1].size()-1])%n][right_child[M-1].size()-1]);
}
}
}
bool reach_left(long long x, long long y, int z){
if(z > left_child[x].size())return reach_left(x, y, left_child[x].size());
while(z && left_child[x][z-1] > y)z--;
if(z == 0)return heights[x] > heights[(x+n-y)%n];
return reach_left((x+n-left_child[x][z-1])%n, y-left_child[x][z-1], z-1);
}
bool reach_right(long long x, long long y, int z){
if(z > right_child[x].size())return reach_right(x, y, right_child[x].size());
while(z && right_child[x][z-1] > y)z--;
if(z == 0)return heights[x] > heights[(x+y)%n];
return reach_right((x+right_child[x][z-1])%n, y-right_child[x][z-1], z-1);
}
} A;
void init(int k, vector<int> r) {
A.init(k-1, r);
int n = r.size();
while(A.h >= 0){
A.extract(1, A.right_zero(1, 1, n, 1, n), 1, n);
}
if(k*2<=A.n)A.create_child();
return;
}
int compare_plants(int x, int y) {
if(A.k*2+2>A.n)return A.H[x] > A.H[y] ? 1 : -1;
if(A.reach_left(x, (x+A.n-y)%A.n, 30) || A.reach_right(x, (y+A.n-x)%A.n, 30))return 1;
if(A.reach_left(y, (y+A.n-x)%A.n, 30) || A.reach_right(y, (x+A.n-y)%A.n, 30))return -1;
return 0;
}
Compilation message
plants.cpp: In member function 'void segment_tree::init(int, std::vector<int>)':
plants.cpp:20:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i = 0; i < M.size(); i++){
| ~~^~~~~~~~~~
plants.cpp: In member function 'void segment_tree::create_child()':
plants.cpp:137:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for(int i = 0; i < H.size(); i++){
| ~~^~~~~~~~~~
plants.cpp: In member function 'bool segment_tree::reach_left(long long int, long long int, int)':
plants.cpp:158:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | if(z > left_child[x].size())return reach_left(x, y, left_child[x].size());
| ~~^~~~~~~~~~~~~~~~~~~~~~
plants.cpp: In member function 'bool segment_tree::reach_right(long long int, long long int, int)':
plants.cpp:164:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | if(z > right_child[x].size())return reach_right(x, y, right_child[x].size());
| ~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
19844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
19804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
19804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
19800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
19804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
19804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
19844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
