#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const long long MXN = 2e5 + 5;
const long long LOG = 20;
#define inf 0x3F3F3F3F
long long n;
array<long long, 2> p[2][LOG][MXN];
long long rr[MXN], f[MXN];
long long cnt[MXN];
array<long long, 2> st[MXN << 2];
long long lz[MXN << 2];
void build(long long l, long long r, long long x)
{
if (l == r)
{
st[x] = {cnt[l] - rr[l], l};
return;
}
long long mid = (l + r) >> 1;
build(l, mid, 2*x);
build(mid + 1, r, 2*x + 1);
st[x] = min(st[2*x], st[2*x + 1]);
}
void relax(long long l, long long r, long long x)
{
if (!lz[x]) return;
st[x][0] += lz[x];
if (l == r)
{
lz[x] = 0;
return;
}
lz[2*x] += lz[x], lz[2*x + 1] += lz[x];
lz[x] = 0;
}
void upd(long long l, long long r, long long x, long long lx, long long rx, long long val)
{
if (lx > rx) return;
relax(l, r, x);
if (l > rx || r < lx) return;
if (l >= lx && r <= rx)
{
lz[x] += val;
relax(l, r, x);
return;
}
long long mid = (l + r) >> 1;
upd(l, mid, 2*x, lx, rx, val);
upd(mid + 1, r, 2*x + 1, lx, rx, val);
st[x] = min(st[2*x], st[2*x + 1]);
}
set<long long> idx;
set<array<long long, 2>> dif;
void ins(long long x)
{
idx.insert(x);
if (idx.size() == 1)
{
dif.insert({0, x});
return;
}
auto it = idx.find(x);
auto itl = it, itr = it;
if (it == idx.begin()) itl = prev(idx.end());
else itl = prev(it);
if (next(it) == idx.end()) itr = idx.begin();
else itr = next(it);
dif.erase({(*itr - *itl + n) % n, *itr});
dif.insert({(x - *itl + n) % n, x});
dif.insert({(*itr - x + n) % n, *itr});
}
void ers(long long x)
{
if (idx.size() == 1)
{
idx.clear();
dif.clear();
return;
}
auto it = idx.find(x);
auto itl = it, itr = it;
if (it == idx.begin()) itl = prev(idx.end());
else itl = prev(it);
if (next(it) == idx.end()) itr = idx.begin();
else itr = next(it);
dif.erase({(x - *itl + n) % n, x});
dif.erase({(*itr - x + n) % n, *itr});
dif.insert({(*itr - *itl + n) % n, *itr});
idx.erase(it);
}
// 4 3 2
// 0 1 1 2
// 0 2
// 1 2
void init(int k, vector<int> r)
{
n = r.size();
f[n] = inf;
p[0][0][n] = {n, 0};
p[1][0][n] = {n, 0};
for (long long i = 1; i <= (n * 4); i++) st[i] = {inf, -1};
for (long long i = 0; i < n; i++) rr[i] = r[i];
for (long long i = 0; i < n; i++) cnt[i] = k - 1;
build(0, n - 1, 1);
while (1)
{
array<long long, 2> x = st[1];
if (!x[0])
{
ins(x[1]);
upd(0, n - 1, 1, x[1], x[1], inf);
}
else break;
}
long long cur = 0;
while (!idx.empty())
{
long long ind = (*dif.rbegin())[1];
ers(ind);
f[ind] = ++cur;
if (ind - 1 >= 0) upd(0, n - 1, 1, max(ind - k + 1, 0), ind - 1, -1);
if (ind - k + 1 < 0) upd(0, n - 1, 1, (ind - k + 1 + n) % n, n - 1, -1);
// for (long long i = (idx[ind] - 1 + n) % n; i != idx[(ind - 1 + sz) % sz]; i = (i - 1 + n) % n)
// {
// if (!f[i]) adj[idx[ind]].push_back(i);
// }
// for (long long i = (idx[ind] + 1) % n; i != (idx[ind] + k) % n; i = (i + 1) % n)
// {
// if (!f[i]) adj[idx[ind]].push_back(i);
// }
// for (long long i = (idx[ind] - 1 + n) % n; i != (idx[ind] - k + n) % n; i = (i - 1 + n) % n)
// {
// if (!f[i]) adj[idx[ind]].push_back(i);
// cnt[i]--;
// }
// f[idx[ind]] = 1;
while (1)
{
array<long long, 2> x = st[1];
if (!x[0])
{
ins(x[1]);
upd(0, n - 1, 1, x[1], x[1], inf);
}
else break;
}
}
set<array<long long, 2>> s;
for (long long i = 0; i < k; i++) s.insert({f[i], i});
for (long long i = n - 1; i >= 0; i--)
{
s.erase({f[(i + k) % n], (i + k) % n});
auto it = s.lower_bound({f[i], i});
if (it != s.end())
{
p[0][0][i] = {(*it)[1], ((*it)[1] - i + n) % n};
}
else p[0][0][i] = {n, inf};
s.insert({f[i], i});
}
s.clear();
for (long long i = n - k; i < n; i++) s.insert({f[i], i});
for (long long i = 0; i < n; i++)
{
s.erase({f[(i - k + n) % n], (i - k + n) % n});
auto it = s.lower_bound({f[i], i});
if (it != s.end())
{
p[1][0][i] = {(*it)[1], (i - (*it)[1] + n) % n};
}
else p[1][0][i] = {n, inf};
s.insert({f[i], i});
}
// for (long long i = 0; i < n; i++)
// {
// cout << f[i] << ' ';
// }
// cout << '\n';
// for (long long i = 0; i < n; i++)
// {
// cout << p[0][0][i][0] << ' ';
// }
// cout << '\n';
// for (long long i = 0; i < n; i++)
// {
// cout << p[1][0][i][0] << ' ';
// }
// cout << '\n';
for (long long j = 0; j < 2; j++)
{
for (long long i = 1; i < LOG; i++)
{
for (long long k = 0; k <= n; k++)
{
long long par = p[j][i - 1][k][0];
p[j][i][k] = {p[j][i - 1][par][0], p[j][i - 1][par][1] + p[j][i - 1][k][1]};
}
}
}
}
long long check(long long x, long long y)
{
long long x1 = x;
long long d = (y - x + n) % n;
long long res = 0;
for (long long i = LOG - 1; i >= 0; i--)
{
if (f[p[0][i][x][0]] <= f[y])
{
res += 1LL * p[0][i][x][1];
x = p[0][i][x][0];
}
}
if (f[x] <= f[y] && res >= d) return 1;
res = 0, x = x1;
d = (x - y + n) % n;
for (long long i = LOG - 1; i >= 0; i--)
{
if (f[p[1][i][x][0]] <= f[y])
{
res += 1LL * p[1][i][x][1];
x = p[1][i][x][0];
}
}
return (f[x] <= f[y] && res >= d);
}
int compare_plants(int x, int y)
{
// ? x < y
if (check(x, y)) return -1;
if (check(y, x)) return 1;
return 0;
// return (a[x] > a[y] ? 1 : -1);
}
Compilation message
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:131:56: error: no matching function for call to 'max(long long int, int)'
131 | if (ind - 1 >= 0) upd(0, n - 1, 1, max(ind - k + 1, 0), ind - 1, -1);
| ^
In file included from /usr/include/c++/10/vector:60,
from plants.h:1,
from plants.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
plants.cpp:131:56: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
131 | if (ind - 1 >= 0) upd(0, n - 1, 1, max(ind - k + 1, 0), ind - 1, -1);
| ^
In file included from /usr/include/c++/10/vector:60,
from plants.h:1,
from plants.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
plants.cpp:131:56: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
131 | if (ind - 1 >= 0) upd(0, n - 1, 1, max(ind - k + 1, 0), ind - 1, -1);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from plants.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
plants.cpp:131:56: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
131 | if (ind - 1 >= 0) upd(0, n - 1, 1, max(ind - k + 1, 0), ind - 1, -1);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from plants.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
plants.cpp:131:56: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
131 | if (ind - 1 >= 0) upd(0, n - 1, 1, max(ind - k + 1, 0), ind - 1, -1);
| ^
