#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 500000;
const int INF = 1e18;
int c;
int n;
int H[N];
int k;
pair<int, int> tree[4 * N];
int push[4 * N];
pair<int, int> Merge(pair<int, int> a, pair<int, int> b)
{
return min(a, b);
}
void Push(int V)
{
tree[2 * V + 1].first += push[V];
tree[2 * V + 2].first += push[V];
push[2 * V + 1] += push[V];
push[2 * V + 2] += push[V];
push[V] = 0;
}
void Build(int L, int R, int V, vector<int> &r)
{
if (L + 1 == R)
{
tree[V] = {r[L], L};
return;
}
int M = (L + R) / 2;
Build(L, M, 2 * V + 1, r);
Build(M, R, 2 * V + 2, r);
tree[V] = Merge(tree[2 * V + 1], tree[2 * V + 2]);
}
pair<int, int> Get(int l, int r, int L = 0, int R = n, int V = 0)
{
if (r <= L || R <= l) return {INF, 0};
if (l <= L && R <= r) return tree[V];
int M = (L + R) / 2;
Push(V);
return Merge(Get(l, r, L, M, 2 * V + 1), Get(l, r, M, R, 2 * V + 2));
}
void Add(int l, int r, int x, int L = 0, int R = n, int V = 0)
{
if (r <= L || R <= l) return;
if (l <= L && R <= r)
{
tree[V].first += x;
push[V] += x;
return;
}
int M = (L + R) / 2;
Push(V);
Add(l, r, x, L, M, 2 * V + 1);
Add(l, r, x, M, R, 2 * V + 2);
tree[V] = Merge(tree[2 * V + 1], tree[2 * V + 2]);
}
int CGet(int l, int r)
{
if (l < 0)
{
l += n;
pair<int, int> a = Get(l, n);
pair<int, int> b = Get(0, r);
if (a.first == 0) return a.second;
if (b.first == 0) return b.second;
return -1;
}
pair<int, int> a = Get(l, r);
if (a.first == 0) return a.second;
return -1;
}
void CAdd(int l, int r, int x)
{
if (l < 0)
{
l += n;
Add(l, n, x);
Add(0, r, x);
}
else
{
Add(l, r, x);
}
}
pair<int, int> tree2[4 * N];
void Build2(int L = 0, int R = n, int V = 0)
{
tree2[V] = {INF, L};
if (L + 1 == R) return;
int M = (L + R) / 2;
Build2(L, M, 2 * V + 1);
Build2(M, R, 2 * V + 2);
}
void Set2(int pos, int x, int L = 0, int R = n, int V = 0)
{
if (L + 1 == R)
{
tree2[V] = {x, L};
return;
}
int M = (L + R) / 2;
if (pos < M) Set2(pos, x, L, M, 2 * V + 1);
else Set2(pos, x, M, R, 2 * V + 2);
tree2[V] = min(tree2[2 * V + 1], tree2[2 * V + 2]);
}
pair<int, int> Get2(int l, int r, int L = 0, int R = n, int V = 0)
{
if (r <= L || R <= l) return {INF, 0};
if (l <= L && R <= r) return tree2[V];
int M = (L + R) / 2;
return min(Get2(l, r, L, M, 2 * V + 1), Get2(l, r, M, R, 2 * V + 2));
}
int up_left[N], up_right[N];
int CGet2(int l, int r)
{
if (l < 0 || r > n)
{
if (l < 0) l += n;
if (r > n) r -= n;
pair<int, int> a = Get2(l, n);
pair<int, int> b = Get2(0, r);
if (a.first < INF) return a.second;
if (b.first < INF) return b.second;
return -1;
}
pair<int, int> a = Get2(l, r);
if (a.first < INF) return a.second;
return -1;
}
void call(int i, int k, vector<int> &r, vector<int> &h1)
{
int id = CGet(i - k + 1, i);
while (id != -1)
{
call(id, k, r, h1);
id = CGet(i - k + 1, i);
}
up_right[i] = CGet2(i + 1, i + k);
up_left[i] = CGet2(i - k + 1, i);
h1[i] = c--;
Set2(i, h1[i]);
CAdd(i - k + 1, i, -1);
CAdd(i, i + 1, INF);
}
const int LG = 20;
int le[LG][N], ri[LG][N];
void init(int K, vector<int> r)
{
k = K;
n = r.size();
vector<int> h1(n);
c = n;
Build(0, n, 0, r);
Build2();
int id = CGet(0, n);
while (id != -1)
{
call(id, k, r, h1);
id = CGet(0, n);
}
for (int i = 0; i < n; i++)
{
H[i] = h1[i];
}
#ifdef LOCAL
for (int i = 0; i < n; i++)
{
cout << H[i] << " ";
}
cout << endl;
#endif // LOCAL
for (int i = 0; i < n; i++)
{
if (up_left[i] != -1)
{
le[0][i] = i - up_left[i];
if (le[0][i] < 0) le[0][i] += n;
} else le[0][i] = INF;
if (up_right[i] != -1)
{
ri[0][i] = up_right[i] - i;
if (ri[0][i] < 0) ri[0][i] += n;
} else ri[0][i] = INF;
assert(le[0][i] < k || le[0][i] == INF);
assert(ri[0][i] < k || ri[0][i] == INF);
}
for (int j = 1; j < LG; j++)
{
for (int i = 0; i < n; i++)
{
if (le[j - 1][i] < INF)
le[j][i] = min(le[j - 1][i] + le[j - 1][((i - le[j - 1][i]) % n + n) % n], INF);
else
le[j][i] = INF;
if (ri[j - 1][i] < INF)
ri[j][i] = min(ri[j - 1][i] + ri[j - 1][(i + ri[j - 1][i]) % n], INF);
else
ri[j][i] = INF;
}
}
}
int Dist(int x, int y)
{
if (x < y) return min(y - x, n - y + x);
return min(x - y, n - x + y);
}
int compare_plants(int x, int y)
{
if (Dist(x, y) < k)
{
if (H[x] <= H[y]) return -1;
return 1;
}
int d, dist;
d = x;
dist = y - x;
for (int j = 0; j >= 0 && Dist(d, y) >= k; )
{
if (ri[j][d] <= dist)
{
dist -= ri[j][d];
d += ri[j][d];
d = (d % n + n) % n;
}
else break;
}
assert(dist >= Dist(d, y));
if (Dist(d, y) < k && H[d] <= H[y]) return -1;
if (Dist(d, y) >= k)
{
assert(ri[0][d] == INF);
}
d = x;
dist = x - y + n;
for (int j = 0; j >= 0 && Dist(d, y) >= k; )
{
if (le[j][d] <= dist)
{
dist -= le[j][d];
d -= le[j][d];
d = (d % n + n) % n;
}
else break;
}
assert(dist >= Dist(d, y));
if (Dist(d, y) < k && H[d] <= H[y]) return -1;
if (Dist(d, y) >= k)
{
assert(le[0][d] == INF);
}
swap(x, y);
d = x;
dist = y - x + n;
for (int j = 0; j >= 0 && Dist(d, y) >= k;)
{
if (ri[j][d] <= dist)
{
dist -= ri[j][d];
d += ri[j][d];
d = (d % n + n) % n;
}
else break;
}
assert(dist >= Dist(d, y));
if (Dist(d, y) < k && H[d] <= H[y]) return 1;
if (Dist(d, y) >= k)
{
assert(ri[0][d] == INF);
}
d = x;
dist = x - y;
for (int j = 0; j >= 0 && Dist(d, y) >= k;)
{
if (le[j][d] <= dist)
{
dist -= le[j][d];
d -= le[j][d];
d = (d % n + n) % n;
}
else break;
}
assert(dist >= Dist(d, y));
if (Dist(d, y) < k && H[d] <= H[y]) return 1;
if (Dist(d, y) >= k)
{
assert(le[0][d] == INF);
}
return 0;
}
#ifdef LOCAL
signed main()
{
int n, k, q;
cin >> n >> k >> q;
vector<int> r(n);
for (int i = 0; i < n; i++) cin >> r[i];
init(k, r);
while (q--)
{
int x, y;
cin >> x >> y;
cout << compare_plants(x, y) << endl;
}
}
#endif
Compilation message
/tmp/ccsPOeAo.o: In function `main':
grader.cpp:(.text.startup+0x2d6): undefined reference to `init(int, std::vector<int, std::allocator<int> >)'
grader.cpp:(.text.startup+0x30d): undefined reference to `compare_plants(int, int)'
collect2: error: ld returned 1 exit status
