#include <bits/stdc++.h>
using namespace std;
const int N = 500000;
const int INF = 1e9;
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);
}
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];
}
for (int i = 0; i < n; i++)
{
cout << H[i] << " " << up_left[i] << " " << up_right[i] << endl;
}
}
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)
{
int d;
d = x;
while (d != -1)
{
if (dist(d, y) < k && H[d] < H[y]) return -1;
d = up_right[d];
}
d = x;
while (d != -1)
{
if (dist(d, y) < k && H[d] < H[y]) return -1;
d = up_left[d];
}
d = y;
while (d != -1)
{
if (dist(d, x) < k && H[d] < H[x]) return 1;
d = up_right[d];
}
d = y;
while (d != -1)
{
if (dist(d, x) < k && H[d] < H[x]) return 1;
d = up_left[d];
}
return 0;
}
#ifdef LOCAL
int 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
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
