#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
struct segment_tree{
int n;
vector <int> tree, flag;
void build(int i, int L, int R, const vector <int>& v){
if(L == R){
tree[i] = v[L];
return;
}
int mid = (L + R) / 2;
build(2 * i, L, mid, v);
build(2 * i + 1, mid + 1, R, v);
tree[i] = min(tree[2 * i], tree[2 * i + 1]);
}
segment_tree(const vector <int>& v){
n = v.size();
tree.resize(4 * n);
flag.resize(4 * n, 0);
build(1, 0, n - 1, v);
}
void push(int i, int L, int R){
if(L < R){
flag[2 * i] += flag[i];
flag[2 * i + 1] += flag[i];
}
tree[i] += flag[i];
flag[i] = 0;
}
void update(int i, int L, int R, int u, int v, int val){
push(i, L, R);
if(R < u || v < L)return;
if(u <= L && R <= v){
flag[i] += val;
push(i, L, R);
return;
}
int mid = (L + R) / 2;
update(2 * i, L, mid, u, v, val);
update(2 * i + 1, mid + 1, R, u, v, val);
tree[i] = min(tree[2 * i], tree[2 * i + 1]);
}
void update(int u, int v, int val){
update(1, 0, n - 1, u, v, val);
}
int extract_zero(int i, int L, int R){
push(i, L, R);
if(tree[i] != 0)return -1;
if(L == R){
tree[i] = 1 << 30;
return L;
}
int mid = (L + R) / 2;
push(2 * i, L, mid);
push(2 * i + 1, mid + 1, R);
int r;
if(tree[2 * i] == 0){
r = extract_zero(2 * i, L, mid);
}else{
r = extract_zero(2 * i + 1, mid + 1, R);
}
tree[i] = min(tree[2 * i], tree[2 * i + 1]);
return r;
}
int extract_zero(){
return extract_zero(1, 0, n - 1);
}
};
const int LOG = 20;
vector < vector <int> > next_greater, next_smaller;
vector <int> v;
int n, k;
void init(int pk, vector <int> r){
n = r.size();
k = pk;
for(int i = 0; i < n; i++)
r[i] = k - 1 - r[i];
segment_tree tree(r);
set <int> s;
set < pair <int, int> > d;
auto dist = [&](int x, int y){
if(x > y)return x - y;
return x - y + n;
};
auto add = [&](int i){
if(s.empty()){
s.insert(i);
d.insert({n, i});
return;
}
auto ptr = s.insert(i).first;
auto r = (next(ptr) == s.end() ? s.begin() : next(ptr)), l = (ptr == s.begin() ? prev(s.end()) : prev(ptr));
d.erase({dist(*r, *l), *r});
d.insert({dist(*r, i), *r});
d.insert({dist(i, *l), i});
};
auto del = [&](int i){
if(s.size() == 1){
s.clear();
d.clear();
return;
}
auto ptr = s.find(i);
auto r = (next(ptr) == s.end() ? s.begin() : next(ptr)), l = (ptr == s.begin() ? prev(s.end()) : prev(ptr));
d.insert({dist(*r, *l), *r});
d.erase({dist(*r, i), *r});
d.erase({dist(i, *l), i});
s.erase(ptr);
};
v.resize(2 * n);
for(int i = 0; i < n; i++){
while(true){
int r = tree.extract_zero();
if(r == -1)break;
add(r);
}
int x = d.rbegin()->second;
del(x);
if(x - (k - 1) >= 0){
tree.update(x - (k - 1), x - 1, -1);
}else{
if(x > 0)tree.update(0, x - 1, -1);
tree.update(x - (k - 1) + n, n - 1, -1);
}
v[i] = x;
}
for(int i = n; i < 2 * n; i++)
v[i] = v[i - n];
next_greater.resize(LOG, vector <int>(2 * n));
next_smaller.resize(LOG, vector <int>(2 * n));
set < pair <int, int> > q;
for(int i = 2 * n - 1; i >= 0; i--){
if(i + k < 2 * n){
q.erase({v[i + k], i + k});
}
auto x = q.lower_bound(make_pair(v[i], 0));
if(x != q.end())next_greater[0][i] = x->second;
else next_greater[0][i] = -1;
if(x != q.begin())next_smaller[0][i] = prev(x)->second;
else next_smaller[0][i] = -1;
for(int j = 1; j < LOG; j++){
if(next_greater[j - 1][i] == -1)next_greater[j][i] = -1;
else next_greater[j][i] = next_greater[j - 1][next_greater[j - 1][i]];
if(next_smaller[j - 1][i] == -1)next_smaller[j][i] = -1;
else next_smaller[j][i] = next_smaller[j - 1][next_smaller[j - 1][i]];
}
q.insert({v[i], i});
}
}
int compare_plants(int x, int y){
auto go_greater = [&](int x, int y){
for(int l = LOG - 1; l >= 0; l--){
if(next_greater[l][x] != -1 && next_greater[l][x] <= y){
x = next_greater[l][x];
}
}
if(v[x] > v[y] || x + k <= y)return false;
return true;
};
auto go_smaller = [&](int x, int y){
for(int l = LOG - 1; l >= 0; l--){
if(next_smaller[l][x] != -1 && next_smaller[l][x] <= y){
x = next_smaller[l][x];
}
}
if(v[x] < v[y] || x + k <= y)return false;
return true;
};
if(v[x] < v[y]){
if(go_greater(x, y) || go_smaller(y, x + n))return -1;
return 0;
}else{
if(go_smaller(x, y) || go_greater(y, x + n))return 1;
return 0;
}
}
/*
int main(){
init(3, {0, 1, 1, 2});
cout << compare_plants(0, 2) << endl;
cout << compare_plants(1, 2) << endl;
init(2, {0, 1, 0, 1});
cout << compare_plants(0, 3) << endl;
cout << compare_plants(1, 3) << endl;
return 0;
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
288 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
