#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 3;
int r_arr[N], p[N], k, n;
struct Segment_Tree{
struct Node{
int mn;
array<int, 2> prev_zero;
Node(){}
Node(int mn, int i): mn(mn), prev_zero({i, 0}){}
friend Node merge(const Node &l, const Node &r){
Node ret;
ret.mn = min(l.mn, r.mn);
if(r.prev_zero[1] >= k - 1) ret.prev_zero = r.prev_zero;
else ret.prev_zero = l.prev_zero;
return ret;
}
};
Node nd[4 * N];
int lp[4 * N];
void init(int i = 0, int l = 0, int r = n - 1){
if(l == r){
nd[i] = Node(r_arr[l], l);
return;
}
int mid = (l + r) >> 1;
init(2 * i + 1, l, mid);
init(2 * i + 2, mid + 1, r);
nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]);
}
void push(int i, int l, int r){
nd[i].mn += lp[i];
if(l != r){
lp[2 * i + 1] += lp[i];
lp[2 * i + 2] += lp[i];
}
lp[i] = 0;
}
int query(int i = 0, int l = 0, int r = n - 1){
push(i, l, r);
return nd[i].prev_zero[0];
}
int get_next_zero(int s, int i = 0, int l = 0, int r = n - 1){
if(l > r) return n;
push(i, l, r);
if(r < s || nd[i].mn) return n;
if(l == r) return l;
int mid = (l + r) >> 1;
int l_val = get_next_zero(s, 2 * i + 1, l, mid);
if(l_val != n) return l_val;
return get_next_zero(s, 2 * i + 2, mid + 1, r);
}
int get_prev_zero(int s, int i = 0, int l = 0, int r = n - 1){
if(l > r) return -1;
push(i, l, r);
if(l > s || nd[i].mn) return -1;
if(l == r) return l;
int mid = (l + r) >> 1;
int r_val = get_prev_zero(s, 2 * i + 2, mid + 1, r);
if(r_val != -1) return r_val;
return get_prev_zero(s, 2 * i + 1, l, mid);
}
void update_prev_zero(int s, int i = 0, int l = 0, int r = n - 1){
if(l > r) return;
push(i, l, r);
if(l > s || r < s) return;
if(l == r){
nd[i].prev_zero = {s, s - get_prev_zero(s - 1, 0, 0, n - 1)};
return;
}
int mid = (l + r) >> 1;
update_prev_zero(s, 2 * i + 1, l, mid);
update_prev_zero(s, 2 * i + 2, mid + 1, r);
nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]);
}
void update_zeroes(int i, int l, int r){
if(l > r) return;
push(i, l, r);
if(nd[i].mn) return;
if(l == r){
update_prev_zero(l, i, l, r);
return;
}
int mid = (l + r) >> 1;
update_zeroes(2 * i + 1, l, mid);
update_zeroes(2 * i + 2, mid + 1, r);
nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]);
}
void change_value(int s, int val, int i = 0, int l = 0, int r = n - 1){
if(l > r) return;
push(i, l, r);
if(r < s || s < l) return;
if(l == r){
nd[i] = Node(val, s);
return;
}
int mid = (l + r) >> 1;
change_value(s, val, 2 * i + 1, l, mid);
change_value(s, val, 2 * i + 2, mid + 1, r);
nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]);
}
void update(int l2, int r2, int val, int i = 0, int l = 0, int r = n - 1){
if(l > r) return;
push(i, l, r);
if(r < l2 || r2 < l) return;
if(l2 <= l && r <= r2){
lp[i]+=val;
push(i, l, r);
update_zeroes(i, l, r);
return;
}
int mid = (l + r) >> 1;
update(l2, r2, val, 2 * i + 1, l, mid);
update(l2, r2, val, 2 * i + 2, mid + 1, r);
nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]);
}
} st;
void init(int _k, vector<int> _r) {
k = _k;
n = _r.size();
for(int i = 0; i < _r.size(); ++i)
r_arr[i] = _r[i];
st.init();
st.update_zeroes(0, 0, n - 1);
for(int i = n - 1; i >= 0; --i){
int idx = st.query();
p[idx] = i;
cout << idx << " - idx" << endl;
st.change_value(idx, n);
if(idx) st.update(max(idx - (k - 1), 0), idx - 1, -1);
if(idx < k - 1) st.update(n - ((k - 1) - idx), n - 1, -1);
int nxt = st.get_next_zero(idx + 1);
//cout << nxt << " nxt" << endl;
if(nxt != n) st.update_prev_zero(nxt);
}
}
int compare_plants(int x, int y) {
return (p[x] > p[y]) ? 1 : -1;
}
/*
4 3 2
0 1 1 2
0 2
1 2
*/
/*
4 2 2
0 1 0 1
0 3
1 3
*/
Compilation message
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:155:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | for(int i = 0; i < _r.size(); ++i)
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
