#include "plants.h"
#include <bits/stdc++.h>
#define int long long
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) x.size();
using namespace std;
typedef pair<int,int> ii;
struct node{
int s, e, m;
ii val = ii(0,0); int lazy = 0;
node *l, *r;
node(int S, int E){
s = S, e = E, m = (s+e)/2;
if(s == e) val = ii(0, S);
else{
l = new node(s, m);
r = new node(m+1, e);
val = min(l->val, r->val);
}
}
void apply(int L){
val.first += L;
lazy += L;
}
void push(){
if(s == e) return;
l->apply(lazy);
r->apply(lazy);
lazy = 0;
}
void update(int S, int E, int L){
push();
if(s == S && E == e){
apply(L);
return;
}
else if(E <= m) l->update(S, E, L);
else if(S >= m+1) r->update(S, E, L);
else l->update(S, m, L), r->update(m+1, E, L);
val = min(l->val, r->val);
}
ii query(int S, int E){
push();
if(s == S && E == e) return val;
else if(E <= m) return l->query(S, E);
else if(S >= m+1) return r->query(S, E);
else return min(l->query(S, m), r->query(m+1, E));
}
} *root;
int n, K;
int H[200005];
int height;
void assign(int u){
while(true){
int R = u-1, L = u-K+1;
if(L < 0) L += n; if(R < 0) R += n;
ii res;
if(L <= R) res = root->query(L,R);
else res = min(root->query(L, n-1), root->query(0,R));
if(res.first == 0) assign(res.second);
else break;
}
H[u] = height;
int R = u-1, L = u-K+1;
if(L < 0) L += n; if(R < 0) R += n;
if(L <= R) root->update(L, R, -1);
else root->update(L, n-1, -1), root->update(0, R, -1);
root->update(u, u, 1e9);
height--;
}
ii pl[20][200005];
ii pr[20][200005];
ii get(int i){
if(i < 0) i += n;
if(i >= n) i -= n;
return ii(H[i], i);
}
void init(int _K, vector<int> R) {
n = sz(R); K = _K;
root = new node(0, n-1);
for(int i = 0;i < n;i++) root->update(i,i,R[i]);
fill(H,H+n,-1);
height = n-1;
while(height >= 0){
ii res = root->query(0, n-1);
assign(res.second);
}
set<ii> Left, Right;
for(int k = 1;k < K;k++){
Left.insert(get(-k));
Right.insert(get(k));
}
H[n] = -1; ///dummy height
for(int i = 0;i < n;i++){
auto it = Left.upper_bound(ii(H[i],0));
if(it != Left.begin()){
it--;
int dis = i - it->second;
if(dis < 0) dis += n;
pl[0][i] = ii(it->second, dis);
}
else pl[0][i] = ii(n, -1);
it = Right.upper_bound(ii(H[i],0));
if(it != Right.begin()){
it--;
int dis = it->second - i;
if(dis < 0) dis += n;
pr[0][i] = ii(it->second, dis);
}
else pr[0][i] = ii(n, -1);
Left.erase(get(i-K+1));
Left.insert(get(i));
Right.erase(get(i+1));
Right.insert(get(i+K));
}
for(int k = 0;k <= 18;k++) pl[k][n] = ii(n, -1), pr[k][n] = ii(n, -1); ///dummy
for(int k = 1;k <= 18;k++){
for(int i = 0;i < n;i++){
ii a = pl[k-1][i];
ii b = pl[k-1][a.first];
pl[k][i] = ii(b.first, a.second+b.second);
a = pr[k-1][i];
b = pr[k-1][a.first];
pr[k][i] = ii(b.first, a.second+b.second);
}
}
return;
}
int compare_plants(int x, int y) {
int ans = 1;
if(H[x] < H[y]){
swap(x, y);
ans *= -1;
}
long long dL = 0, dR = 0;
int u = x;
for(int k = 18;k >= 0;k--){
ii toL = pl[k][u];
if(H[toL.first] > H[y]){
dL += toL.second;
u = toL.first;
}
}
u = x;
for(int k = 18;k >= 0;k--){
ii toR = pr[k][u];
if(H[toR.first] > H[y]){
dR += toR.second;
u = toR.first;
}
}
int needL = x - y;
if(needL < 0) needL += n;
needL -= (K-1);
int needR = y - x;
if(needR < 0) needR += n;
needR -= (K-1);
if(dL < needL && dR < needR) ans = 0;
return ans;
}
Compilation message
plants.cpp: In function 'void assign(long long int)':
plants.cpp:64:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
64 | if(L < 0) L += n; if(R < 0) R += n;
| ^~
plants.cpp:64:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
64 | if(L < 0) L += n; if(R < 0) R += n;
| ^~
plants.cpp:76:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
76 | if(L < 0) L += n; if(R < 0) R += n;
| ^~
plants.cpp:76:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
76 | if(L < 0) L += n; if(R < 0) R += n;
| ^~
/tmp/cce8dhiB.o: In function `main':
grader.cpp:(.text.startup+0x30e): undefined reference to `init(int, std::vector<int, std::allocator<int> >)'
grader.cpp:(.text.startup+0x357): undefined reference to `compare_plants(int, int)'
collect2: error: ld returned 1 exit status
