| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 302556 | polyakoff | 식물 비교 (IOI20_plants) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
class plants {
private int k, n;
private int[] r, level;
private class SegTree {
class Node {
int min, toAdd;
ArrayList<Integer> inds;
Node() {
toAdd = 0;
inds = new ArrayList<>();
}
}
Node[] t;
int size;
Node merge(Node t1, Node t2) {
Node res = new Node();
if (t1.min < t2.min) {
res.min = t1.min;
res.inds.addAll(t1.inds);
} else if (t2.min < t1.min) {
res.min = t2.min;
res.inds.addAll(t2.inds);
} else {
res.min = t1.min;
res.inds.addAll(t1.inds);
if (res.inds.size() > 0 && t2.inds.size() > 0 && t2.inds.get(0) - res.inds.get(res.inds.size() - 1) < k) {
for (int i = 1; i < t2.inds.size(); i++)
res.inds.add(t2.inds.get(i));
} else {
res.inds.addAll(t2.inds);
}
}
return res;
}
void push(int v) {
if (t[v].toAdd != 0) {
t[v * 2 + 1].min += t[v].toAdd;
t[v * 2 + 1].toAdd += t[v].toAdd;
t[v * 2 + 2].min += t[v].toAdd;
t[v * 2 + 2].toAdd += t[v].toAdd;
t[v].toAdd = 0;
}
}
void build(int v, int tl, int tr, int[] arr) {
if (tl == tr) {
t[v] = new Node();
t[v].min = arr[tl];
t[v].inds.add(tl);
} else {
int tm = (tl + tr) / 2;
build(v * 2 + 1, tl, tm, arr);
build(v * 2 + 2, tm + 1, tr, arr);
t[v] = merge(t[v * 2 + 1], t[v * 2 + 2]);
}
}
void addOn(int v, int tl, int tr, int l, int r, int val) {
if (r < tl || tr < l)
return;
if (l <= tl && tr <= r) {
t[v].min += val;
t[v].toAdd += val;
return;
}
int tm = (tl + tr) / 2;
push(v);
addOn(v * 2 + 1, tl, tm, l, r, val);
addOn(v * 2 + 2, tm + 1, tr, l, r, val);
t[v] = merge(t[v * 2 + 1], t[v * 2 + 2]);
}
void build(int[] arr) {
size = arr.length;
t = new Node[size * 4];
build(0, 0, size - 1, arr);
}
void addOn(int l, int r, int val) {
addOn(0, 0, size - 1, l, r, val);
}
ArrayList<Integer> findZeros() {
ArrayList<Integer> res = new ArrayList<>();
if (t[0].inds.size() >= 2 && t[0].inds.get(0) + n - t[0].inds.get(t[0].inds.size() - 1) < k) {
for (int i = 1; i < t[0].inds.size(); i++)
res.add(t[0].inds.get(i));
} else {
res.addAll(t[0].inds);
}
return res;
}
}
void init(int k, int[] r) {
this.k = k;
this.r = r;
n = r.length;
SegTree st = new SegTree();
st.build(r);
level = new int[n];
for (int cnt = 0, lvl = 0; cnt < n; lvl++) {
ArrayList<Integer> zeros = st.findZeros();
for (int i : zeros) {
level[i] = lvl;
st.addOn(i, i, k - 1);
st.addOn(Math.max(0, i - (k - 1)), i - 1, -1);
if (i - (k - 1) < 0)
st.addOn(n - (k - 1 - i), n - 1, -1);
}
cnt += zeros.size();
}
}
int compare_plants(int x, int y) {
if (level[x] < level[y])
return 1;
else if (level[x] > level[y])
return -1;
return 0;
}
}