[problem:1297A]↵
↵
Author: [user:MikeMirzayanov,2020-02-28]↵
↵
<spoiler summary="Editorial">↵
[tutorial:1297A]↵
</spoiler>↵
↵
<spoiler summary="Solution (elizarov)">↵
↵
~~~~~↵
fun main() {↵
repeat(readLine()!!.toInt()) {↵
when (val n = readLine()!!.toInt()) {↵
in 0..999 -> println(n)↵
in 1000..999_499 -> println("${(n + 500) / 1000}K")↵
else -> println("${(n + 500_000) / 1_000_000}M")↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1297B]↵
↵
Author: [user:MikeMirzayanov,2020-02-28]↵
↵
<spoiler summary="Editorial">↵
[tutorial:1297B]↵
</spoiler>↵
↵
<spoiler summary="Solution (elizarov)">↵
↵
~~~~~↵
fun main() {↵
class M(val a: Int, val b: Int)↵
repeat(readLine()!!.toInt()) {↵
val n = readLine()!!.toInt()↵
val ms = Array(n) {↵
readLine()!!.split(" ").map { it.toInt() }.let { (a, b) -> M(a, b) }↵
}↵
var ans = -1↵
fun check(x: Int) {↵
if (ms.count { m -> x in m.a..m.b } == 1) ans = x↵
}↵
for (m in ms) {↵
for (d in -1..1) {↵
check(m.a + d)↵
check(m.b + d)↵
}↵
}↵
println(ans)↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1297C]↵
↵
Author: [user:MikeMirzayanov,2020-02-28]↵
↵
<spoiler summary="Editorial">↵
[tutorial:1297C]↵
</spoiler>↵
↵
<spoiler summary="Solution (elizarov)">↵
↵
~~~~~↵
fun main() {↵
repeat(readLine()!!.toInt()) {↵
val n = readLine()!!.toInt()↵
val a = readLine()!!.split(" ").map { it.toInt() }↵
val s = a.withIndex().sortedByDescending { it.value }↵
val i = s.indexOfLast { it.value > 0 }↵
val j = s.indexOfFirst { it.value < 0 }↵
val c = CharArray(n) { '0' }↵
for (k in 0 until i) c[s[k].index] = '1'↵
if (j >= 0 && -s[j].value < s[i].value) {↵
c[s[i].index] = '1'↵
c[s[j].index] = '1'↵
}↵
val sum = s.sumBy { if (c[it.index] == '1') it.value else 0 }↵
println(sum)↵
println(c.joinToString(""))↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1297D]↵
↵
Author: [user:MikeMirzayanov,2020-02-28]↵
↵
<spoiler summary="Editorial">↵
[tutorial:1297D]↵
</spoiler>↵
↵
<spoiler summary="Solution (elizarov)">↵
↵
~~~~~↵
fun main() {↵
repeat(readLine()!!.toInt()) {↵
val (n, k) = readLine()!!.split(" ").map { it.toInt() }↵
val a = readLine()!!.split(" ").map { it.toInt() }↵
val s = a.withIndex().sortedByDescending { it.value }↵
val d = IntArray(n)↵
var rem = k↵
for (p in 1 until n) {↵
val i = s[p - 1].index↵
val j = s[p].index↵
d[j] = minOf(a[i] + d[i] - a[j] - 1, rem)↵
rem -= d[j]↵
}↵
val add = rem / n↵
val ext = rem % n↵
for (p in 0 until n) d[s[p].index] += add + if (p < ext) 1 else 0↵
println(d.joinToString(" "))↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1297E]↵
↵
Author: [user:MikeMirzayanov,2020-02-28]↵
↵
<spoiler summary="Editorial">↵
[tutorial:1297E]↵
</spoiler>↵
↵
<spoiler summary="Solution (elizarov)">↵
↵
~~~~~↵
fun main() {↵
repeat(readLine()!!.toInt()) {↵
// readLine() // skip empty line↵
solveCase()↵
}↵
}↵
↵
private fun solveCase() {↵
val (n, k) = readLine()!!.split(" ").map { it.toInt() }↵
val gf = IntArray(n) { -1 }↵
val gy = IntArray(2 * n)↵
val gn = IntArray(2 * n)↵
var ec = 0↵
fun edge(x: Int, y: Int) {↵
gy[ec] = y↵
gn[ec] = gf[x]↵
gf[x] = ec++↵
}↵
repeat(n - 1) {↵
val (x, y) = readLine()!!.split(" ").map { it.toInt() - 1 }↵
edge(x, y)↵
edge(y, x)↵
}↵
val v = BooleanArray(n)↵
val q = IntArray(n)↵
var h = 0↵
var t = 0↵
fun enqueue(x: Int) {↵
q[t++] = x↵
v[x] = true↵
}↵
enqueue(0)↵
var lc = 1↵
while (lc < k && h < t) {↵
val x = q[h++]↵
var i = gf[x]↵
var cc = 0↵
while (i >= 0 && lc < k) {↵
val y = gy[i]↵
if (!v[y]) {↵
enqueue(y)↵
if (cc++ > 0) lc++↵
}↵
i = gn[i]↵
}↵
if (x == 0 && cc == 1) lc++↵
}↵
if (lc < k) {↵
println("No")↵
return↵
}↵
println("Yes")↵
println(v.count { it })↵
println(v.withIndex().filter { it.value }.joinToString(" ") { (it.index + 1).toString() })↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1297F]↵
↵
Author: [user:MikeMirzayanov,2020-02-28]↵
↵
<spoiler summary="Editorial">↵
[tutorial:1297F]↵
</spoiler>↵
↵
<spoiler summary="Solution (elizarov)">↵
↵
~~~~~↵
import java.util.*↵
↵
fun main() {↵
repeat(readLine()!!.toInt()) {↵
// readLine() // skip empty line↵
solveCase()↵
}↵
}↵
↵
private data class Mv(val i: Int, val a: Int, val b: Int, var t: Int = 0) : Comparable<Mv> {↵
override fun compareTo(other: Mv): Int = if (b != other.b) b.compareTo(other.b) else i.compareTo(other.i)↵
}↵
↵
private fun solveCase() {↵
val (n, m) = readLine()!!.split(" ").map { it.toInt() }↵
val d = Array(n) { i ->↵
readLine()!!.split(" ").map { it.toInt() }.let { (a, b) -> Mv(i, a, b) }↵
}↵
d.sortBy { it.a }↵
var t = 0↵
val w = TreeSet<Mv>()↵
fun advance(to: Int) {↵
while (t < to && !w.isEmpty()) {↵
repeat(minOf(w.size, m)) {↵
val v = w.first()↵
v.t = t↵
w -= v↵
}↵
t++↵
}↵
t = to↵
}↵
for (v in d) {↵
advance(v.a)↵
w += v↵
}↵
advance(Int.MAX_VALUE)↵
d.sortBy { it.i }↵
println(maxOf(0, d.map { it.t - it.b }.max()!!))↵
println(d.joinToString(" ") { it.t.toString() })↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:1297G]↵
↵
Author: [user:MikeMirzayanov,2020-02-28]↵
↵
<spoiler summary="Editorial">↵
[tutorial:1297G]↵
</spoiler>↵
↵
<spoiler summary="Solution (elizarov)">↵
↵
~~~~~↵
fun main() {↵
val (m, k) = readLine()!!.split(" ").map { it.toInt() }↵
val f = factor(m) ?: run {↵
println(-1)↵
return↵
}↵
val dp = HashMap<Long,Long>()↵
val dig = IntArray(100_000)↵
fun count(nd: Int, p: Long = -1): Long {↵
val e = f[0] + (f[1] shl 5) + (f[2] shl 10) + (f[3] shl 15) + (nd.toLong() shl 20)↵
if (nd == 0) return if (e == 0L) 1 else 0↵
if (p == -1L) dp[e]?.let { return it }↵
var cnt = 0L↵
for (d in 1..9) {↵
dig[nd - 1] = d↵
val df = factors[d]↵
for (i in 0..3) f[i] -= df[i]↵
if (f.all { it >= 0 }) {↵
val nc = count(nd - 1)↵
if (p >= 0 && cnt + nc > p) return count(nd - 1, p - cnt)↵
cnt += nc↵
}↵
for (i in 0..3) f[i] += df[i]↵
}↵
dp[e] = cnt↵
return cnt↵
}↵
var num = 1L↵
var nd = 1↵
while (count(nd) <= k - num) num += count(nd++)↵
check(count(nd, k - num) == 1L)↵
println(dig.take(nd).reversed().joinToString(""))↵
}↵
↵
private val pr = listOf(2, 3, 5, 7)↵
private val factors = Array(10) { factor(it)!! }↵
↵
private fun factor(m: Int): IntArray? {↵
val f = IntArray(4)↵
if (m <= 1) return f↵
var rem = m↵
for ((i, p) in pr.withIndex()) {↵
while (rem % p == 0) {↵
rem /= p↵
f[i]++↵
}↵
}↵
return f.takeIf { rem == 1 }↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:1297H]↵
↵
Authors: [user:MikeMirzayanov,2020-02-28], [user:antontrygubO_o,2020-02-28]↵
↵
<spoiler summary="Editorial">↵
[tutorial:1297H]↵
</spoiler>↵
↵
<spoiler summary="Solution (elizarov)">↵
↵
~~~~~↵
fun main() {↵
class Ans(val a: String, val m: String)↵
repeat(readLine()!!.toInt()) {↵
val s = readLine()!!↵
val n = s.length↵
val dp = Array(n) { i -> arrayOfNulls<Ans>(i + 1) }↵
dp[0][0] = Ans(s.substring(0, 1), "R")↵
var best = Ans(s, "")↵
fun updateBest(p: Ans) {↵
if (p.a <= best.a) best = p↵
}↵
fun updateDP(i: Int, j: Int, p: Ans) {↵
val cur = dp[i][j]↵
if (cur == null || p.a < cur.a) dp[i][j] = p↵
}↵
for (i in 1 until n) {↵
for (j in 0 until i) {↵
val p = dp[i - 1][j] ?: continue↵
updateDP(i, j, Ans(p.a + s[i], p.m + "R"))↵
if (j >= i - j) continue↵
if (s[i] == p.a[j]) updateDP(i, j + 1, Ans(p.a, p.m + "B"))↵
if (s[i] < p.a[j]) updateBest(Ans(p.a, p.m + "B".repeat(n - i)))↵
}↵
}↵
for (p in dp[n - 1]) if (p != null) updateBest(p)↵
println(best.m)↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:1297I]↵
↵
Authors: [user:FieryPhoenix,2020-02-28], [user:dragonslayerintraining,2020-02-28]↵
↵
<spoiler summary="Editorial">↵
[tutorial:1297I]↵
</spoiler>↵
↵
<spoiler summary="Solution (elizarov)">↵
↵
~~~~~↵
import java.util.*↵
↵
private class Block(val l: Int, val r: Int) : Comparable<Block> {↵
fun cover(c: Block) = l <= c.l && r >= c.r↵
override fun compareTo(other: Block): Int = l.compareTo(other.l)↵
}↵
↵
fun main() {↵
val (n, d) = readLine()!!.split(" ").map { it.toInt() }↵
val bh = arrayOfNulls<TreeSet<Block>>(n + 1) // blocks by height↵
// Segment tree↵
val tt = BooleanArray(4 * d) // terminal(leaf) node in segment tree↵
val th = IntArray(4 * d) // max height in this segment↵
tt[0] = true↵
// Segment tree functions↵
fun findMax(b: Block, i: Int, tl: Int, tr: Int): Int {↵
if (tt[i] || b.l <= tl && b.r >= tr) return th[i]↵
val tm = (tl + tr) / 2↵
return maxOf(↵
if (b.l <= tm) findMax(b, 2 * i + 1, tl, tm) else 0,↵
if (b.r > tm) findMax(b, 2 * i + 2, tm + 1, tr) else 0↵
)↵
}↵
fun setLeaf(i: Int, h: Int) {↵
tt[i] = true↵
th[i] = h↵
}↵
fun place(b: Block, h: Int, i: Int, tl: Int, tr: Int) {↵
if (b.l <= tl && b.r >= tr) return setLeaf(i, h)↵
val tm = (tl + tr) / 2↵
val j1 = 2 * i + 1↵
val j2 = 2 * i + 2↵
if (tt[i]) { // split node↵
tt[i] = false↵
setLeaf(j1, th[i])↵
setLeaf(j2, th[i])↵
}↵
if (b.l <= tm) place(b, h, j1, tl, tm)↵
if (b.r > tm) place(b, h, j2, tm + 1, tr)↵
th[i] = maxOf(th[j1], th[j2])↵
}↵
// Simulate each incoming block & print answer↵
var bc = 0↵
repeat(n) {↵
val b = readLine()!!.split(" ").map { it.toInt() }.let{ (l, r) -> Block(l, r) }↵
var maxH = findMax(b, 0, 1, d)↵
while (true) {↵
val bs = bh[maxH] ?: break↵
var floor = bs.floor(b)↵
if (floor != null && floor.r < b.l) floor = bs.higher(floor)↵
if (floor == null) floor = bs.first()↵
check(floor.l <= b.r)↵
val list = bs.tailSet(floor).takeWhile { it.l <= b.r }↵
if (!b.cover(list.first()) || !b.cover(list.last())) break↵
for (c in list) bs -= c // don't use bs.removeAll(list)↵
bc -= list.size↵
maxH--↵
}↵
val h = maxH + 1↵
place(b, h, 0, 1, d)↵
val bs = bh[h] ?: run { TreeSet<Block>().also { bh[h] = it } }↵
bs += b↵
println(++bc)↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
Author: [user:MikeMirzayanov,2020-02-28]↵
↵
<spoiler summary="Editorial">↵
[tutorial:1297A]↵
</spoiler>↵
↵
<spoiler summary="Solution (elizarov)">↵
↵
~~~~~↵
fun main() {↵
repeat(readLine()!!.toInt()) {↵
when (val n = readLine()!!.toInt()) {↵
in 0..999 -> println(n)↵
in 1000..999_499 -> println("${(n + 500) / 1000}K")↵
else -> println("${(n + 500_000) / 1_000_000}M")↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1297B]↵
↵
Author: [user:MikeMirzayanov,2020-02-28]↵
↵
<spoiler summary="Editorial">↵
[tutorial:1297B]↵
</spoiler>↵
↵
<spoiler summary="Solution (elizarov)">↵
↵
~~~~~↵
fun main() {↵
class M(val a: Int, val b: Int)↵
repeat(readLine()!!.toInt()) {↵
val n = readLine()!!.toInt()↵
val ms = Array(n) {↵
readLine()!!.split(" ").map { it.toInt() }.let { (a, b) -> M(a, b) }↵
}↵
var ans = -1↵
fun check(x: Int) {↵
if (ms.count { m -> x in m.a..m.b } == 1) ans = x↵
}↵
for (m in ms) {↵
for (d in -1..1) {↵
check(m.a + d)↵
check(m.b + d)↵
}↵
}↵
println(ans)↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1297C]↵
↵
Author: [user:MikeMirzayanov,2020-02-28]↵
↵
<spoiler summary="Editorial">↵
[tutorial:1297C]↵
</spoiler>↵
↵
<spoiler summary="Solution (elizarov)">↵
↵
~~~~~↵
fun main() {↵
repeat(readLine()!!.toInt()) {↵
val n = readLine()!!.toInt()↵
val a = readLine()!!.split(" ").map { it.toInt() }↵
val s = a.withIndex().sortedByDescending { it.value }↵
val i = s.indexOfLast { it.value > 0 }↵
val j = s.indexOfFirst { it.value < 0 }↵
val c = CharArray(n) { '0' }↵
for (k in 0 until i) c[s[k].index] = '1'↵
if (j >= 0 && -s[j].value < s[i].value) {↵
c[s[i].index] = '1'↵
c[s[j].index] = '1'↵
}↵
val sum = s.sumBy { if (c[it.index] == '1') it.value else 0 }↵
println(sum)↵
println(c.joinToString(""))↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1297D]↵
↵
Author: [user:MikeMirzayanov,2020-02-28]↵
↵
<spoiler summary="Editorial">↵
[tutorial:1297D]↵
</spoiler>↵
↵
<spoiler summary="Solution (elizarov)">↵
↵
~~~~~↵
fun main() {↵
repeat(readLine()!!.toInt()) {↵
val (n, k) = readLine()!!.split(" ").map { it.toInt() }↵
val a = readLine()!!.split(" ").map { it.toInt() }↵
val s = a.withIndex().sortedByDescending { it.value }↵
val d = IntArray(n)↵
var rem = k↵
for (p in 1 until n) {↵
val i = s[p - 1].index↵
val j = s[p].index↵
d[j] = minOf(a[i] + d[i] - a[j] - 1, rem)↵
rem -= d[j]↵
}↵
val add = rem / n↵
val ext = rem % n↵
for (p in 0 until n) d[s[p].index] += add + if (p < ext) 1 else 0↵
println(d.joinToString(" "))↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1297E]↵
↵
Author: [user:MikeMirzayanov,2020-02-28]↵
↵
<spoiler summary="Editorial">↵
[tutorial:1297E]↵
</spoiler>↵
↵
<spoiler summary="Solution (elizarov)">↵
↵
~~~~~↵
fun main() {↵
repeat(readLine()!!.toInt()) {↵
// readLine() // skip empty line↵
solveCase()↵
}↵
}↵
↵
private fun solveCase() {↵
val (n, k) = readLine()!!.split(" ").map { it.toInt() }↵
val gf = IntArray(n) { -1 }↵
val gy = IntArray(2 * n)↵
val gn = IntArray(2 * n)↵
var ec = 0↵
fun edge(x: Int, y: Int) {↵
gy[ec] = y↵
gn[ec] = gf[x]↵
gf[x] = ec++↵
}↵
repeat(n - 1) {↵
val (x, y) = readLine()!!.split(" ").map { it.toInt() - 1 }↵
edge(x, y)↵
edge(y, x)↵
}↵
val v = BooleanArray(n)↵
val q = IntArray(n)↵
var h = 0↵
var t = 0↵
fun enqueue(x: Int) {↵
q[t++] = x↵
v[x] = true↵
}↵
enqueue(0)↵
var lc = 1↵
while (lc < k && h < t) {↵
val x = q[h++]↵
var i = gf[x]↵
var cc = 0↵
while (i >= 0 && lc < k) {↵
val y = gy[i]↵
if (!v[y]) {↵
enqueue(y)↵
if (cc++ > 0) lc++↵
}↵
i = gn[i]↵
}↵
if (x == 0 && cc == 1) lc++↵
}↵
if (lc < k) {↵
println("No")↵
return↵
}↵
println("Yes")↵
println(v.count { it })↵
println(v.withIndex().filter { it.value }.joinToString(" ") { (it.index + 1).toString() })↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1297F]↵
↵
Author: [user:MikeMirzayanov,2020-02-28]↵
↵
<spoiler summary="Editorial">↵
[tutorial:1297F]↵
</spoiler>↵
↵
<spoiler summary="Solution (elizarov)">↵
↵
~~~~~↵
import java.util.*↵
↵
fun main() {↵
repeat(readLine()!!.toInt()) {↵
// readLine() // skip empty line↵
solveCase()↵
}↵
}↵
↵
private data class Mv(val i: Int, val a: Int, val b: Int, var t: Int = 0) : Comparable<Mv> {↵
override fun compareTo(other: Mv): Int = if (b != other.b) b.compareTo(other.b) else i.compareTo(other.i)↵
}↵
↵
private fun solveCase() {↵
val (n, m) = readLine()!!.split(" ").map { it.toInt() }↵
val d = Array(n) { i ->↵
readLine()!!.split(" ").map { it.toInt() }.let { (a, b) -> Mv(i, a, b) }↵
}↵
d.sortBy { it.a }↵
var t = 0↵
val w = TreeSet<Mv>()↵
fun advance(to: Int) {↵
while (t < to && !w.isEmpty()) {↵
repeat(minOf(w.size, m)) {↵
val v = w.first()↵
v.t = t↵
w -= v↵
}↵
t++↵
}↵
t = to↵
}↵
for (v in d) {↵
advance(v.a)↵
w += v↵
}↵
advance(Int.MAX_VALUE)↵
d.sortBy { it.i }↵
println(maxOf(0, d.map { it.t - it.b }.max()!!))↵
println(d.joinToString(" ") { it.t.toString() })↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:1297G]↵
↵
Author: [user:MikeMirzayanov,2020-02-28]↵
↵
<spoiler summary="Editorial">↵
[tutorial:1297G]↵
</spoiler>↵
↵
<spoiler summary="Solution (elizarov)">↵
↵
~~~~~↵
fun main() {↵
val (m, k) = readLine()!!.split(" ").map { it.toInt() }↵
val f = factor(m) ?: run {↵
println(-1)↵
return↵
}↵
val dp = HashMap<Long,Long>()↵
val dig = IntArray(100_000)↵
fun count(nd: Int, p: Long = -1): Long {↵
val e = f[0] + (f[1] shl 5) + (f[2] shl 10) + (f[3] shl 15) + (nd.toLong() shl 20)↵
if (nd == 0) return if (e == 0L) 1 else 0↵
if (p == -1L) dp[e]?.let { return it }↵
var cnt = 0L↵
for (d in 1..9) {↵
dig[nd - 1] = d↵
val df = factors[d]↵
for (i in 0..3) f[i] -= df[i]↵
if (f.all { it >= 0 }) {↵
val nc = count(nd - 1)↵
if (p >= 0 && cnt + nc > p) return count(nd - 1, p - cnt)↵
cnt += nc↵
}↵
for (i in 0..3) f[i] += df[i]↵
}↵
dp[e] = cnt↵
return cnt↵
}↵
var num = 1L↵
var nd = 1↵
while (count(nd) <= k - num) num += count(nd++)↵
check(count(nd, k - num) == 1L)↵
println(dig.take(nd).reversed().joinToString(""))↵
}↵
↵
private val pr = listOf(2, 3, 5, 7)↵
private val factors = Array(10) { factor(it)!! }↵
↵
private fun factor(m: Int): IntArray? {↵
val f = IntArray(4)↵
if (m <= 1) return f↵
var rem = m↵
for ((i, p) in pr.withIndex()) {↵
while (rem % p == 0) {↵
rem /= p↵
f[i]++↵
}↵
}↵
return f.takeIf { rem == 1 }↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:1297H]↵
↵
Authors: [user:MikeMirzayanov,2020-02-28], [user:antontrygubO_o,2020-02-28]↵
↵
<spoiler summary="Editorial">↵
[tutorial:1297H]↵
</spoiler>↵
↵
<spoiler summary="Solution (elizarov)">↵
↵
~~~~~↵
fun main() {↵
class Ans(val a: String, val m: String)↵
repeat(readLine()!!.toInt()) {↵
val s = readLine()!!↵
val n = s.length↵
val dp = Array(n) { i -> arrayOfNulls<Ans>(i + 1) }↵
dp[0][0] = Ans(s.substring(0, 1), "R")↵
var best = Ans(s, "")↵
fun updateBest(p: Ans) {↵
if (p.a <= best.a) best = p↵
}↵
fun updateDP(i: Int, j: Int, p: Ans) {↵
val cur = dp[i][j]↵
if (cur == null || p.a < cur.a) dp[i][j] = p↵
}↵
for (i in 1 until n) {↵
for (j in 0 until i) {↵
val p = dp[i - 1][j] ?: continue↵
updateDP(i, j, Ans(p.a + s[i], p.m + "R"))↵
if (j >= i - j) continue↵
if (s[i] == p.a[j]) updateDP(i, j + 1, Ans(p.a, p.m + "B"))↵
if (s[i] < p.a[j]) updateBest(Ans(p.a, p.m + "B".repeat(n - i)))↵
}↵
}↵
for (p in dp[n - 1]) if (p != null) updateBest(p)↵
println(best.m)↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[problem:1297I]↵
↵
Authors: [user:FieryPhoenix,2020-02-28], [user:dragonslayerintraining,2020-02-28]↵
↵
<spoiler summary="Editorial">↵
[tutorial:1297I]↵
</spoiler>↵
↵
<spoiler summary="Solution (elizarov)">↵
↵
~~~~~↵
import java.util.*↵
↵
private class Block(val l: Int, val r: Int) : Comparable<Block> {↵
fun cover(c: Block) = l <= c.l && r >= c.r↵
override fun compareTo(other: Block): Int = l.compareTo(other.l)↵
}↵
↵
fun main() {↵
val (n, d) = readLine()!!.split(" ").map { it.toInt() }↵
val bh = arrayOfNulls<TreeSet<Block>>(n + 1) // blocks by height↵
// Segment tree↵
val tt = BooleanArray(4 * d) // terminal(leaf) node in segment tree↵
val th = IntArray(4 * d) // max height in this segment↵
tt[0] = true↵
// Segment tree functions↵
fun findMax(b: Block, i: Int, tl: Int, tr: Int): Int {↵
if (tt[i] || b.l <= tl && b.r >= tr) return th[i]↵
val tm = (tl + tr) / 2↵
return maxOf(↵
if (b.l <= tm) findMax(b, 2 * i + 1, tl, tm) else 0,↵
if (b.r > tm) findMax(b, 2 * i + 2, tm + 1, tr) else 0↵
)↵
}↵
fun setLeaf(i: Int, h: Int) {↵
tt[i] = true↵
th[i] = h↵
}↵
fun place(b: Block, h: Int, i: Int, tl: Int, tr: Int) {↵
if (b.l <= tl && b.r >= tr) return setLeaf(i, h)↵
val tm = (tl + tr) / 2↵
val j1 = 2 * i + 1↵
val j2 = 2 * i + 2↵
if (tt[i]) { // split node↵
tt[i] = false↵
setLeaf(j1, th[i])↵
setLeaf(j2, th[i])↵
}↵
if (b.l <= tm) place(b, h, j1, tl, tm)↵
if (b.r > tm) place(b, h, j2, tm + 1, tr)↵
th[i] = maxOf(th[j1], th[j2])↵
}↵
// Simulate each incoming block & print answer↵
var bc = 0↵
repeat(n) {↵
val b = readLine()!!.split(" ").map { it.toInt() }.let{ (l, r) -> Block(l, r) }↵
var maxH = findMax(b, 0, 1, d)↵
while (true) {↵
val bs = bh[maxH] ?: break↵
var floor = bs.floor(b)↵
if (floor != null && floor.r < b.l) floor = bs.higher(floor)↵
if (floor == null) floor = bs.first()↵
check(floor.l <= b.r)↵
val list = bs.tailSet(floor).takeWhile { it.l <= b.r }↵
if (!b.cover(list.first()) || !b.cover(list.last())) break↵
for (c in list) bs -= c // don't use bs.removeAll(list)↵
bc -= list.size↵
maxH--↵
}↵
val h = maxH + 1↵
place(b, h, 0, 1, d)↵
val bs = bh[h] ?: run { TreeSet<Block>().also { bh[h] = it } }↵
bs += b↵
println(++bc)↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
