#include <bits/stdc++.h>
#include "plants.h"
using namespace std;
#define MAXN 200005
#define debug(...) fprintf(stderr, __VA_ARGS__); fflush(stderr);
const int TS = 1<<19, ST = TS/2-1;
int N, K, R[MAXN];
int A[MAXN], B[MAXN];
template <typename T>
struct SegTree{
struct Value{
T value, lazysum;
};
vector<Value> tree;
SegTree(int arr[]){
tree.resize(TS, {0, 0});
for (int i=ST+1;i<TS;i++) tree[i].value = i-ST <= N ? arr[i-ST] : 1e9;
for (int i=ST;i;i--) tree[i].value = min(tree[i*2].value, tree[i*2+1].value);
}
void propagate(int n){
if (n <= ST){
tree[n*2].value += tree[n].lazysum, tree[n*2+1].value += tree[n].lazysum;
tree[n*2].lazysum += tree[n].lazysum, tree[n*2+1].lazysum += tree[n].lazysum;
}
tree[n].lazysum = 0;
}
void update(int n, int s, int e, int l, int r, const int &v){
if (l > r || e < l || r < s) return;
if (l <= s && e <= r){
tree[n].value += v, tree[n].lazysum += v;
return;
}
propagate(n);
int m = s+e >> 1;
update(n*2, s, m, l, r, v);
update(n*2+1, m+1, e, l, r, v);
tree[n].value = min(tree[n*2].value, tree[n*2+1].value);
}
int findzero(int n){
if (tree[n].value != 0) return 0;
propagate(n);
if (n > ST) return n-ST;
if (!tree[n*2].value) return findzero(n*2);
else if (!tree[n*2+1].value) return findzero(n*2+1);
else assert(0);
}
};
struct ZeroContainer{
set<int> pos, non_covered;
set<int>::iterator left(set<int>::iterator it){
auto ret = it;
if (ret == pos.begin()) ret = pos.end();
return --ret;
}
set<int>::iterator right(set<int>::iterator it){
auto ret = it; ret++;
if (ret == pos.end()) return pos.begin();
return ret;
}
void insert(int p){
auto it = pos.insert(p).first;
auto l = left(it), r = right(it);
if (l == it || (*it-*l+N)%N >= K) non_covered.insert(p);
if (r != it && (*r-*it+N)%N < K) non_covered.erase(*r);
}
void remove(int p){
auto it = pos.find(p);
auto l = left(it), r = right(it);
if (l != it && r != it && (l == r || (*r-*l+N)%N >= K)) non_covered.insert(*r);
pos.erase(it);
}
int pop_smallest(){
int ret = *non_covered.begin(); non_covered.erase(ret);
remove(ret);
return ret;
}
int pop_largest(){
int ret = *non_covered.rbegin(); non_covered.erase(ret);
remove(ret);
return ret;
}
};
void get(int pos[], bool desc)
{
SegTree<int> segtree(R);
ZeroContainer zc;
for (int ord=1;ord<=N;ord++){
for (;;){
int p = segtree.findzero(1);
if (!p) break;
zc.insert(p);
segtree.update(1, 1, TS/2, p, p, 1e9);
}
int x = desc ? zc.pop_largest() : zc.pop_smallest();
pos[x] = ord; // perm[ord] = x
segtree.update(1, 1, TS/2, max(1, x-K+1), x-1, -1);
if (x-K+1 < 1) segtree.update(1, 1, TS/2, N-(1-(x-K+1))+1, N, -1);
}
}
void init(int K, vector<int> r)
{
::K = K;
N = r.size();
for (int i=1;i<=N;i++) R[i] = r[i-1];
get(A, 0);
get(B, 1);
}
int compare_plants(int x, int y)
{
if (A[x+1] > A[y+1]) return -compare_plants(y, x);
x++; y++;
if ((A[x] < A[y]) != (B[x] < B[y])) return 1;
return 0;
}
Compilation message
plants.cpp: In instantiation of 'void SegTree<T>::update(int, int, int, int, int, const int&) [with T = int]':
plants.cpp:97:40: required from here
plants.cpp:37:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
37 | int m = s+e >> 1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
4480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
4480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
