#include "plants.h"
#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef long long ll;
//~ #define int ll
const int inf = 1e9;
const int N = 2e5 + 5;
const int M = 20;
struct ST{
ar<ll, 2> tree[N << 2];
ll f[N << 2];
void build(int lx, int rx, int x){
if(lx == rx) { tree[x][1] = lx; return; };
int m = (lx + rx) >> 1;
build(lx, m, x << 1), build(m + 1, rx, x << 1 | 1);
tree[x][1] = lx;
}
ST(){
build(0, N, 1);
}
void push(int x, int lx, int rx){
if(lx == rx) return;
tree[x << 1][0] += f[x];
tree[x << 1 | 1][0] += f[x];
f[x << 1] += f[x], f[x << 1 | 1] += f[x];
f[x] = 0;
}
void add(int l, int r, int v, int lx, int rx, int x){
if(lx > r || rx < l) return;
if(lx >= l && rx <= r){
tree[x][0] += v;
f[x] += v;
return;
}
push(x, lx, rx);
int m = (lx + rx) >> 1;
add(l, r, v, lx, m, x << 1), add(l, r, v, m + 1, rx, x << 1 | 1);
tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
}
void add(int l, int r, int v) { return add(l, r, v, 0, N, 1); }
ar<ll, 2> get(int l, int r, int lx, int rx, int x){
if(lx > r || rx < l) return {inf, inf};
if(lx >= l && rx <= r) return tree[x];
push(x, lx, rx);
int m = (lx + rx) >> 1;
return min(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
}
ar<ll, 2> get(int l, int r){
return get(l, r, 0, N, 1);
}
}tree, R, builder, buildel;
vector<int> a;
vector<vector<int>> l_, r_;
int n;
void init(int k, vector<int> r) {
n = r.size();
a.resize(n);
l_.resize(n, vector<ll>(M, -1));
r_.resize(n, vector<ll>(M, -1));
{
int cnt = 0;
for(int i=0;i<k - 1;i++) cnt += (r[i] == 0);
for(int i=k - 1;;){
tree.add(i, i, r[i] + cnt);
buildel.add(i, i, 1);
builder.add(i, i, 1);
if(r[i]){
R.add(i, i, r[i]);
} else {
R.add(i, i, inf);
}
cnt -= (r[(i + n - k + 1) % n] == 0);
cnt += (r[i] == 0);
i = (i + 1) % n;
if(i == k - 1) break;
}
}
auto to_r = [&](int p){
int l = p, r = p + k - 1;
ar<ll, 2> pp = buildel.get(l, min(r, n - 1));
if(!pp[0] || r < n) return pp;
return buildel.get(0, r - n);
};
auto to_l = [&](int p){
int l = p - k + 1, r = p;
ar<ll, 2> pp = builder.get(max(l, 0), r);
if(!pp[0] || 0 <= l) return pp;
return builder.get(n + l, n - 1);
};
for(int j=n;j>0;j--){
//~ for(int i=0;i<n;i++) cout<<tree.get(i, i)[0]<<" ";
//~ cout<<"\n";
auto [v, p] = tree.get(0, n - 1);
{
ar<ll, 2> pp = to_r(p);
while(pp[0] == 0){
l_[pp[1]][0] = p;
buildel.add(pp[1], pp[1], 1);
pp = to_r(p);
}
pp = to_l(p);
while(pp[0] == 0){
r_[pp[1]][0] = p;
builder.add(pp[1], pp[1], 1);
pp = to_l(p);
}
}
assert(v == 0);
buildel.add(p, p, -1);
builder.add(p, p, -1);
a[p] = j;
R.add(p, p, inf);
tree.add(p, p, inf);
{
int l = p - k + 1, r = p;
tree.add(max(l, 0), r, -1);
R.add(max(l, 0), r, -1);
if(l < 0) tree.add(n + l, n - 1, -1);
if(l < 0) R.add(n + l, n - 1, -1);
ar<ll, 2> pp = R.get(0, n - 1);
while(pp[0] == 0){
R.add(pp[1], pp[1], inf);
{
int l = pp[1] + 1, r = pp[1] + k - 1;
tree.add(l, min(r, n - 1), 1);
if(n <= r) tree.add(0, r - n, 1);
}
pp = R.get(0, n - 1);
}
}
{
int l = p, r = p + k - 1;
tree.add(l, min(r, n - 1), -1);
if(n <= r) tree.add(0, r - n, -1);
}
}
for(int i=0;i<n;i++){
if(~l_[i][0]) l_[i][0] = (i - l_[i][0] + n) % n;
else l_[i][0] = 0;
if(~r_[i][0]) r_[i][0] = (r_[i][0] - i + n) % n;
else r_[i][0] = 0;
}
for(int j=1;j<M;j++){
for(int i=0;i<n;i++){
if(l_[i][j - 1] >= n) l_[i][j] = l_[i][j - 1];
else l_[i][j] = l_[i][j - 1] + l_[(i - l_[i][j - 1] + n) % n][j - 1];
if(r_[i][j - 1] >= n) r_[i][j] = r_[i][j - 1];
else r_[i][j] = r_[i][j - 1] + r_[(i + r_[i][j - 1]) % n][j - 1];
}
}
return;
}
bool check(int x, int y){
{
int cur = x, dis = (x - y + n) % n;
for(int j=19;~j;j--){
if(dis > l_[cur][j]){
dis -= l_[cur][j];
cur -= l_[cur][j];
while(cur < 0) cur += n;
}
}
if(l_[cur][0] && a[(y + dis) % n] > a[y]) return true;
}
{
int cur = x, dis = (y - x + n) % n;
for(int j=19;~j;j--){
if(dis > r_[cur][j]){
dis -= r_[cur][j];
cur += r_[cur][j];
while(cur >= n) cur -= n;
}
}
if(r_[cur][0] && a[(y - dis + n) % n] > a[y]) return true;
}
return false;
}
int compare_plants(int x, int y) {
if(check(x, y)) return 1;
if(check(y, x)) return -1;
return 0;
}
Compilation message
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:74:32: error: no matching function for call to 'std::vector<std::vector<int> >::resize(int&, std::vector<long long int>)'
74 | l_.resize(n, vector<ll>(M, -1));
| ^
In file included from /usr/include/c++/10/vector:67,
from plants.h:1,
from plants.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:937:7: note: candidate: 'void std::vector<_Tp, _Alloc>::resize(std::vector<_Tp, _Alloc>::size_type) [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
937 | resize(size_type __new_size)
| ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:937:7: note: candidate expects 1 argument, 2 provided
/usr/include/c++/10/bits/stl_vector.h:957:7: note: candidate: 'void std::vector<_Tp, _Alloc>::resize(std::vector<_Tp, _Alloc>::size_type, const value_type&) [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = std::vector<int>]'
957 | resize(size_type __new_size, const value_type& __x)
| ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:957:54: note: no known conversion for argument 2 from 'std::vector<long long int>' to 'const value_type&' {aka 'const std::vector<int>&'}
957 | resize(size_type __new_size, const value_type& __x)
| ~~~~~~~~~~~~~~~~~~^~~
plants.cpp:75:32: error: no matching function for call to 'std::vector<std::vector<int> >::resize(int&, std::vector<long long int>)'
75 | r_.resize(n, vector<ll>(M, -1));
| ^
In file included from /usr/include/c++/10/vector:67,
from plants.h:1,
from plants.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:937:7: note: candidate: 'void std::vector<_Tp, _Alloc>::resize(std::vector<_Tp, _Alloc>::size_type) [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
937 | resize(size_type __new_size)
| ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:937:7: note: candidate expects 1 argument, 2 provided
/usr/include/c++/10/bits/stl_vector.h:957:7: note: candidate: 'void std::vector<_Tp, _Alloc>::resize(std::vector<_Tp, _Alloc>::size_type, const value_type&) [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = std::vector<int>]'
957 | resize(size_type __new_size, const value_type& __x)
| ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:957:54: note: no known conversion for argument 2 from 'std::vector<long long int>' to 'const value_type&' {aka 'const std::vector<int>&'}
957 | resize(size_type __new_size, const value_type& __x)
| ~~~~~~~~~~~~~~~~~~^~~
