#include <bits/stdc++.h>
#include "plants.h"
#define int long long
#define deb first
#define fin second
#define mid ((deb + fin) >> 1)
using namespace std;
const int M = 1 << 19, N = 2 * M, T = 19, INF = 1e9 + 42;
int n, k, vals[N], corr[N], gauche[T][M], droite[T][M];
set<int> pos0, posMin;
int imin[N], nbInf[N], lazy[N], maxi[N];
void set0(int i, bool is0) {
if(is0) {
auto it = pos0.lower_bound(i);
if((*it) <= i + k)
posMin.erase((*it));
it--;
if(i > (*it) + k && n <= i && i < 2*n)
posMin.insert(i);
pos0.insert(i);
} else {
pos0.erase(i);
posMin.erase(i);
auto it = pos0.lower_bound(i);
int nex = (*it);
it--;
if(nex > (*it) + k && n <= nex && nex < 2*n)
posMin.insert(nex);
}
}
inline void applyOp(int i, int add) {
lazy[i] += add;
nbInf[i] += add;
}
pair<int, int> update(int i, int deb, int fin, int l, int r, int add) {
if(r <= deb || fin <= l)
return {INF, -1};
if(l <= deb && fin <= r) {
applyOp(i, add);
return {nbInf[i], imin[i]};
}
applyOp(i*2, lazy[i]);
applyOp(i*2+1, lazy[i]);
auto ans = min(update(i*2, deb, mid, l, r, add),
update(i*2+1, mid, fin, l, r, add));
lazy[i] = 0;
nbInf[i] = min(nbInf[i*2], nbInf[i*2+1]);
if(nbInf[i] == nbInf[i*2])
imin[i] = imin[i*2];
else
imin[i] = imin[i*2+1];
return ans;
}
void setMax(int i, int val) {
i += M;
while(i) {
maxi[i] = max(maxi[i], val);
i >>= 1;
}
}
int getMax(int i, int deb, int fin, int l, int r) {
if(r <= deb || fin <= l)
return 0;
if(l <= deb && fin <= r)
return maxi[i];
return max(getMax(i*2, deb, mid, l, r), getMax(i*2+1, mid, fin, l, r));
}
inline int getId(int i) {
while(i < 0)
i += n;
while(i >= n)
i -= n;
return i;
}
void init(int K, vector<int> r) {
k = K;
pos0.insert(INF);
pos0.insert(-INF);
k--;
n = (int)r.size();
for(int i = M; i < N; i++)
imin[i] = i - M;
for(int i = M-1; i > 0; i--)
imin[i] = imin[i*2];
for(int i = 0; i < n; i++) {
r[i] = k - r[i];
update(1, 0, M, i, i+1, r[i]);
if(r[i] == 0) {
set0(i, 1);
set0(i + n, 1);
}
}
for(int i = 0; i < n; i++) {
int id = getId((*posMin.begin()));
update(1, 0, M, id, id+1, INF);
set0(id, 0);
set0(id + n, 0);
vals[id] = i+1;
corr[i+1] = id;
corr[0] = id;
setMax(id, i+1);
setMax(id + n, i+1);
gauche[0][id] = getId(corr[getMax(1, 0, M, id + n - k, id + n)] - id),
droite[0][id] = getId(corr[getMax(1, 0, M, id + 1, id + k + 1)] - id);
if(gauche[0][id] > 0)
gauche[0][id] -= n;
if(id >= k) {
update(1, 0, M, id - k, id, -1);
} else {
update(1, 0, M, 0, id, -1);
update(1, 0, M, n + id - k, n, -1);
}
auto pii = update(1, 0, M, 0, n, 0);
while(pii.first == 0) {
update(1, 0, M, pii.second, pii.second+1, INF);
set0(pii.second, 1);
set0(pii.second + n, 1);
pii = update(1, 0, M, 0, n, 0);
}
}
for(int i = 1; i < T; i++) {
for(int j = 0; j < n; j++) {
gauche[i][j] = gauche[i-1][getId(j + gauche[i-1][j])] + gauche[i-1][j];
droite[i][j] = droite[i-1][getId(j + droite[i-1][j])] + droite[i-1][j];
}
}
}
int compare_plants(int x, int y) {
int ans = 1;
if(vals[x] < vals[y]) {
swap(x, y);
ans = -1;
}
int idl = x, idr = x, nbl = 0, nbr = 0;
for(int i = T-1; i > -1; i--) {
int l = getId(gauche[i][idl] + idl),
r = getId(droite[i][idr] + idr);
if(vals[l] >= vals[y]) {
nbl += gauche[i][idl];
idl = l;
}
if(vals[r] >= vals[y]) {
nbr += droite[i][idr];
idr = r;
}
}
int l = x + nbl, r = x + nbr;
if((l <= y - n && y - n <= r) || (l <= y && y <= r) || (l <= y + n && y + n <= r))
return ans;
return 0;
}
Compilation message
/usr/bin/ld: /tmp/ccpD8QI5.o: in function `main':
grader.cpp:(.text.startup+0x2fb): undefined reference to `init(int, std::vector<int, std::allocator<int> >)'
/usr/bin/ld: grader.cpp:(.text.startup+0x347): undefined reference to `compare_plants(int, int)'
collect2: error: ld returned 1 exit status
