#include "plants.h"
#include <bits/stdc++.h>
struct Node {
int pos, val;
Node(int pos_ = 0, int val_ = 0): pos(pos_), val(val_) {}
Node friend operator+ (Node a, Node b) {
if (a.val == b.val) {
return a.pos < b.pos ? a : b;
} else {
return a.val < b.val ? a : b;
}
}
};
struct SegmentTree {
#define lc (v << 1)
#define rc (v << 1 | 1)
#define mid (l + r) / 2
int n;
std::vector<Node> a;
std::vector<int> b;
SegmentTree(int n_): n(n_), a(4 * n + 1), b(4 * n + 1, 0) {}
void push(int v) {
if (a[v].val != n) {
a[v].val += b[v];
}
if (lc <= 4 * n) {
b[lc] += b[v];
}
if (rc <= 4 * n) {
b[rc] += b[v];
}
b[v] = 0;
}
void set_val(int i, int x, int v, int l, int r) {
push(v);
if (r - l == 1) {
a[v] = Node(i, x);
return;
}
i < mid ? set_val(i, x, lc, l, mid) : set_val(i, x, rc, mid, r);
push(lc);
push(rc);
a[v] = a[lc] + a[rc];
}
void set_val(int i, int x) {
set_val(i, x, 1, 0, n);
}
void update(int s, int e, int x, int v, int l, int r) {
push(v);
if (s <= l && r <= e) {
b[v] += x;
push(v);
return;
}
if (s < mid) {
update(s, e, x, lc, l, mid);
}
if (e > mid) {
update(s, e, x, rc, mid, r);
}
push(lc);
push(rc);
a[v] = a[lc] + a[rc];
}
void update(int s, int e, int x) {
update(s, e, x, 1, 0, n);
};
Node get(int s, int e, int v, int l, int r) {
push(v);
if (s <= l && r <= e) {
return a[v];
}
if (e <= mid) {
return get(s, e, lc, l, mid);
} else if (s >= mid) {
return get(s, e, rc, mid, r);
} else {
return get(s, e, lc, l, mid) + get(s, e, rc, mid, r);
}
}
Node get(int s, int e) {
return get(s, e, 1, 0, n);
}
};
constexpr int N = 2E5;
int h[N];
void init(int k, std::vector<int> org_r) {
int n = org_r.size();
auto norm = [&](int i) {
i %= n;
if (i < 0) {
return i + n;
} else {
return i;
}
};
SegmentTree r(n);
for (int i = 0; i < n; i++) {
r.set_val(i, org_r[i]);
}
auto get = [&](int s, int e) -> Node {
s = norm(s);
e = norm(e);
// std::cout << "(s, e) = (" << s << ", " << e << ")\n";
if (s <= e) {
return r.get(s, e + 1);
} else {
return r.get(s, n) + r.get(0, e + 1);
}
};
auto update = [&](int s, int e, int x) {
s = norm(s);
e = norm(e);
if (s <= e) {
r.update(s, e + 1, x);
} else {
r.update(s, n, x);
r.update(0, e + 1, x);
}
};
int cur = n - 1;
auto dec = [&](auto self, int i, int x) -> void {
if (get(i - k + 1, i - 1).val == 0) {
self(self, get(i - k + 1, i - 1).pos, x - 1);
}
cur--;
h[i] = x;
r.set_val(i, n);
update(i - k + 1, i - 1, -1);
};
while (cur >= 0) {
int i = get(0, n - 1).pos;
dec(dec, i, cur);
}
return;
}
int compare_plants(int x, int y) {
if (h[x] > h[y]) {
return 1;
} else if (h[x] < h[y]) {
return -1;
} else {
return 0;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |