codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1571.md (25400B)


      1 Source: https://codeforces.com/blog/entry/95785
      2 
      3 First of all, I would like to thank all testers of the round: [pashka](/profile/pashka "International Grandmaster pashka"), [FlakeLCR](/profile/FlakeLCR "Master FlakeLCR"), [peti1234](/profile/peti1234 "International Grandmaster peti1234"), [Akulyat](/profile/Akulyat "Grandmaster Akulyat"), [bugdone](/profile/bugdone "Specialist bugdone"), [pacha2880](/profile/pacha2880 "Candidate Master pacha2880"). Also huge thanks to co-authors of the contest: [Neon](/profile/Neon "Candidate Master Neon"), [adedalic](/profile/adedalic "International Master adedalic") and [awoo](/profile/awoo "International Grandmaster awoo").
      4 
      5 I hope you enjoyed participating in the round!
      6 
      7 Okay, now for the editorial itself:
      8 
      9 [1571A - Sequence of Comparisons](/contest/1571/problem/A "Kotlin Heroes: Episode 8")
     10 
     11 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
     12 
     13 **Tutorial**
     14 
     15 Tutorial is loading...
     16 
     17 **Solution (Neon)**
     18 
     19 ```
     20 fun main() = repeat(readLine()!!.toInt()) {
     21   val s = readLine()!!
     22   val l = s.count({ it == '<' })
     23   val g = s.count({ it == '>' })
     24   if (l > 0 && g > 0) println("?")
     25   else if (l > 0) println("<");
     26   else if (g > 0) println(">");
     27   else println("=");
     28 }
     29 ```
     30 
     31 [1571B - Epic Novel](/contest/1571/problem/B "Kotlin Heroes: Episode 8")
     32 
     33 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [adedalic](/profile/adedalic "International Master adedalic")
     34 
     35 **Tutorial**
     36 
     37 Tutorial is loading...
     38 
     39 **Solution (adedalic)**
     40 
     41 ```
     42 fun main() {
     43     repeat(readLine()!!.toInt()) {
     44         val n = readLine()!!.toInt()
     45         val (d1, v1) = readLine()!!.split(' ').map { it.toInt() }
     46         val (d3, v3) = readLine()!!.split(' ').map { it.toInt() }
     47         val d2 = readLine()!!.toInt()
     48 
     49         fun isPossible(d1: Int, v1: Int, d2: Int, v2: Int) = (v2 - v1) <= (d2 - d1)
     50 
     51         for (v2 in v1..v3) {
     52             if (isPossible(d1, v1, d2, v1) && isPossible(d2, v2, d3, v3)) {
     53                 println(v2)
     54                 break
     55             }
     56         }
     57     }
     58 }
     59 ```
     60 
     61 [1571C - Rhyme](/contest/1571/problem/C "Kotlin Heroes: Episode 8")
     62 
     63 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [adedalic](/profile/adedalic "International Master adedalic")
     64 
     65 **Tutorial**
     66 
     67 Tutorial is loading...
     68 
     69 **Solution (adedalic)**
     70 
     71 ```
     72 fun main() {
     73     repeat(readLine()!!.toInt()) {
     74         val n = readLine()!!.toInt()
     75         var l = 0
     76         var r = 4e5.toInt()
     77         for (i in 1..n) {
     78             val pairs = readLine()!!.split(' ')
     79             val limit = pairs[0].commonSuffixWith(pairs[1]).length
     80             if (pairs[2] == "0")
     81                 l = maxOf(l, limit + 1)
     82             else
     83                 r = minOf(r, limit)
     84         }
     85         println(maxOf(0, r - l + 1))
     86         if (r - l + 1 > 0)
     87            println((l..r).joinToString(" "))
     88     }
     89 }
     90 ```
     91 
     92 [1571D - Sweepstake](/contest/1571/problem/D "Kotlin Heroes: Episode 8")
     93 
     94 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [adedalic](/profile/adedalic "International Master adedalic")
     95 
     96 **Tutorial**
     97 
     98 Tutorial is loading...
     99 
    100 **Solution (adedalic)**
    101 
    102 ```
    103 fun main() {
    104     val (n, m) = readLine()!!.split(' ').map { it.toInt() }
    105     val cntPairs = Array(n) { IntArray(n) { 0 } }
    106     val cntFirst = IntArray(n) { 0 }
    107     val cntLast = IntArray(n) { 0 }
    108 
    109     val firstPair = readLine()!!.split(' ').map { it.toInt() - 1 }
    110     for (i in 2..m) {
    111         val (f, l) = readLine()!!.split(' ').map { it.toInt() - 1 }
    112         cntPairs[f][l]++
    113         cntFirst[f]++
    114         cntLast[l]++
    115     }
    116 
    117     fun I(a: Boolean) = if (a) 1 else 0
    118 
    119     var worstPlace = 0
    120     for (w in 0 until n) {
    121         for (l in 0 until n) {
    122             if (w == l)
    123                 continue
    124             val yourScore = I(w == firstPair[0]) + I(l == firstPair[1])
    125             var place = 1
    126             if (yourScore < 2)
    127                 place += cntPairs[w][l]
    128             if (yourScore < 1)
    129                 place += cntFirst[w] + cntLast[l] - 2 * cntPairs[w][l]
    130             worstPlace = maxOf(worstPlace, place)
    131         }
    132     }
    133     println(worstPlace)
    134 }
    135 ```
    136 
    137 [1571E - Fix the String](/contest/1571/problem/E "Kotlin Heroes: Episode 8")
    138 
    139 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
    140 
    141 **Tutorial**
    142 
    143 Tutorial is loading...
    144 
    145 **Solution (pashka)**
    146 
    147 ```
    148 @file:Suppress("CanBeVal")
    149  
    150 import java.io.BufferedReader
    151 import java.io.InputStreamReader
    152 import java.io.OutputStreamWriter
    153 import java.io.PrintWriter
    154 import java.util.*
    155  
    156 private fun solve() {
    157     var n = readInt()
    158     var s = readLn()
    159     var a = readLn()
    160     var j = -1
    161     for (i in a.indices) {
    162         if (a[i] == '1') {
    163             if (j >= 0 && ((i - j) == 1 || (i - j) == 3)) {
    164                 println(-1)
    165                 return
    166             }
    167             j = i
    168         }
    169     }
    170     var i = 0
    171     var res = 0
    172     while (i < a.length) {
    173         if (a[i] == '1') {
    174             j = i
    175             while (j < a.length && a[j] == '1') {
    176                 j += 2
    177             }
    178  
    179             if (j == i + 2) {
    180                 res += minOf(diff(s.substring(i, i + 4), "(())"),
    181                         diff(s.substring(i, i + 4), "()()"))
    182             } else {
    183                 for (k in i .. j step 2) {
    184                     res += diff(s.substring(k, k + 2), "()")
    185                 }
    186             }
    187             i = j + 1
    188         } else {
    189             i++
    190         }
    191     }
    192     println(res)
    193 }
    194  
    195 private fun diff(a: String, b: String): Int {
    196     var res = 0
    197     for (i in a.indices) {
    198         if (a[i] != b[i]) res++
    199     }
    200     return res
    201 }
    202  
    203 // TEMPLATE
    204 fun main(args: Array<String>) {
    205     reader = BufferedReader(InputStreamReader(System.`in`))
    206     out = PrintWriter(OutputStreamWriter(System.out))
    207     repeat(readInt()) {
    208         solve()
    209     }
    210     out.close()
    211 }
    212  
    213 private lateinit var out: PrintWriter
    214 private lateinit var reader: BufferedReader
    215 private var tokenizer: StringTokenizer? = null
    216 private fun read(): String {
    217     while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
    218         tokenizer = StringTokenizer(readLn())
    219     }
    220     return tokenizer!!.nextToken()
    221 }
    222  
    223 private fun readInt() = read().toInt()
    224 private fun readLong() = read().toLong()
    225 private fun readLn() = reader.readLine()!!
    226 private fun readInts() = readLn().split(" ").map { it.toInt() }
    227 private fun readInts(sz: Int) = Array(sz) { readInt() }
    228 private fun readLongs() = readLn().split(" ").map { it.toLong() }
    229 private fun readLongs(sz: Int) = Array(sz) { readLong() }
    230 private fun print(b: Boolean) = out.print(b)
    231 private fun print(i: Int) = out.print(i)
    232 private fun print(d: Double) = out.print(d)
    233 private fun print(l: Long) = out.print(l)
    234 private fun print(s: String) = out.print(s)
    235 private fun print(message: Any?) = out.print(message)
    236 private fun print(a: Array<Int>) = a.forEach { print("$it ") }
    237 private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") }
    238 private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") }
    239 private fun println(b: Boolean) = out.println(b)
    240 private fun println(i: Int) = out.println(i)
    241 private fun println(d: Double) = out.println(d)
    242 private fun println(l: Long) = out.println(l)
    243 private fun println(s: String) = out.println(s)
    244 private fun println() = out.println()
    245 private fun println(message: Any?) = out.println(message)
    246 private fun <T> println(a: Array<out T>) {
    247     a.forEach { print("$it ") }
    248     println()
    249 }
    250  
    251 private fun println(a: IntArray) {
    252     a.forEach { print("$it ") }
    253     println()
    254 }
    255  
    256 private fun println(a: LongArray) {
    257     a.forEach { print("$it ") }
    258     println()
    259 }
    260  
    261 private fun <T> println(a: Collection<T>) {
    262     a.forEach { print("$it ") }
    263     println()
    264 }
    265  
    266 private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v }
    267 private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v }
    268 private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) }
    269 private fun <T> init(vararg elements: T) = elements
    270 private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init }
    271 private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) }
    272 private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> {
    273     return Comparator { a, b ->
    274         val res = a.first.compareTo(b.first)
    275         if (res == 0) a.second.compareTo(b.second) else res
    276     }
    277 }
    278 ```
    279 
    280 [1571F - Kotlinforces](/contest/1571/problem/F "Kotlin Heroes: Episode 8")
    281 
    282 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    283 
    284 **Tutorial**
    285 
    286 Tutorial is loading...
    287 
    288 **Solution (pashka)**
    289 
    290 ```
    291 @file:Suppress("CanBeVal")
    292  
    293 import java.io.BufferedReader
    294 import java.io.InputStreamReader
    295 import java.io.OutputStreamWriter
    296 import java.io.PrintWriter
    297 import java.util.*
    298  
    299 private fun solve() {
    300     var (n, m) = readInts()
    301     var k = intarr(n)
    302     var t = intarr(n)
    303     for (i in k.indices) {
    304         var (kk, tt) = readInts()
    305         k[i] = kk
    306         t[i] = tt
    307     }
    308     var s1 = 0
    309     var s2 = 0
    310     var d = intarr(m + 1, -1)
    311     d[0] = 0
    312     for (i in k.indices) {
    313         if (t[i] == 2) {
    314             s1 += k[i]
    315             for (j in m downTo 0) {
    316                 if (d[j] != -1 && j + k[i] <= m && d[j + k[i]] == -1) {
    317                     d[j + k[i]] = i
    318                 }
    319             }
    320         } else {
    321             s2 += k[i]
    322         }
    323     }
    324     for (i in 0..m) {
    325         if (d[i] == -1) continue
    326         if (maxOf(i * 2 - 1, (s1 - i) * 2) + s2 > m) continue
    327         var c = BooleanArray(n)
    328         var x = i
    329         while (x > 0) {
    330             c[d[x]] = true
    331             x -= k[d[x]]
    332         }
    333         var res = intarr(n)
    334         var kk = 1
    335         for (i in 0 until n) {
    336             if (t[i] == 2 && c[i]) {
    337                 res[i] = kk
    338                 kk += k[i] * 2
    339             }
    340         }
    341         kk = 2
    342         for (i in 0 until n) {
    343             if (t[i] == 2 && !c[i]) {
    344                 res[i] = kk
    345                 kk += k[i] * 2
    346             }
    347         }
    348         kk = m + 1
    349         for (i in 0 until n) {
    350             if (t[i] == 1) {
    351                 kk -= k[i]
    352                 res[i] = kk
    353             }
    354         }
    355         println(res)
    356         return
    357     }
    358     println(-1)
    359 }
    360  
    361 // TEMPLATE
    362 fun main(args: Array<String>) {
    363     reader = BufferedReader(InputStreamReader(System.`in`))
    364     out = PrintWriter(OutputStreamWriter(System.out))
    365 //    repeat(readInt()) {
    366     solve()
    367 //    }
    368     out.close()
    369 }
    370  
    371 private lateinit var out: PrintWriter
    372 private lateinit var reader: BufferedReader
    373 private var tokenizer: StringTokenizer? = null
    374 private fun read(): String {
    375     while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
    376         tokenizer = StringTokenizer(readLn())
    377     }
    378     return tokenizer!!.nextToken()
    379 }
    380  
    381 private fun readInt() = read().toInt()
    382 private fun readLong() = read().toLong()
    383 private fun readLn() = reader.readLine()!!
    384 private fun readInts() = readLn().split(" ").map { it.toInt() }
    385 private fun readInts(sz: Int) = Array(sz) { readInt() }
    386 private fun readLongs() = readLn().split(" ").map { it.toLong() }
    387 private fun readLongs(sz: Int) = Array(sz) { readLong() }
    388 private fun print(b: Boolean) = out.print(b)
    389 private fun print(i: Int) = out.print(i)
    390 private fun print(d: Double) = out.print(d)
    391 private fun print(l: Long) = out.print(l)
    392 private fun print(s: String) = out.print(s)
    393 private fun print(message: Any?) = out.print(message)
    394 private fun print(a: Array<Int>) = a.forEach { print("$it ") }
    395 private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") }
    396 private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") }
    397 private fun println(b: Boolean) = out.println(b)
    398 private fun println(i: Int) = out.println(i)
    399 private fun println(d: Double) = out.println(d)
    400 private fun println(l: Long) = out.println(l)
    401 private fun println(s: String) = out.println(s)
    402 private fun println() = out.println()
    403 private fun println(message: Any?) = out.println(message)
    404 private fun <T> println(a: Array<out T>) {
    405     a.forEach { print("$it ") }
    406     println()
    407 }
    408  
    409 private fun println(a: IntArray) {
    410     a.forEach { print("$it ") }
    411     println()
    412 }
    413  
    414 private fun println(a: LongArray) {
    415     a.forEach { print("$it ") }
    416     println()
    417 }
    418  
    419 private fun <T> println(a: Collection<T>) {
    420     a.forEach { print("$it ") }
    421     println()
    422 }
    423  
    424 private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v }
    425 private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v }
    426 private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) }
    427 private fun <T> init(vararg elements: T) = elements
    428 private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init }
    429 private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) }
    430 private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> {
    431     return Comparator { a, b ->
    432         val res = a.first.compareTo(b.first)
    433         if (res == 0) a.second.compareTo(b.second) else res
    434     }
    435 }
    436 ```
    437 
    438 [1571G - A Battle Against a Dragon](/contest/1571/problem/G "Kotlin Heroes: Episode 8")
    439 
    440 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [awoo](/profile/awoo "International Grandmaster awoo")
    441 
    442 **Tutorial**
    443 
    444 Tutorial is loading...
    445 
    446 **Solution (awoo)**
    447 
    448 ```
    449 class Attack(val a: Int, val b: Int, val i: Int)
    450 
    451 fun main() {
    452 	val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    453 	val ev = ArrayList<Attack>()
    454 
    455 	for (i in 0 until n) {
    456 		val k = readLine()!!.toInt()
    457 		val a = readLine()!!.split(" ").map { it.toInt() }
    458 		val b = readLine()!!.split(" ").map { it.toInt() }
    459 		for (j in 0 until k) {
    460 			ev.add(Attack(a[j], b[j], i))
    461 		}
    462 	}
    463 	ev.sortWith(compareBy({ -it.b }, { it.i }))
    464 	
    465 	val INF = 1e18.toLong()
    466 	val mx = m + n + 1
    467 	val f = LongArray(mx) { -INF }
    468 	
    469 	fun update(pos: Int, x: Long) {
    470 		var i = pos
    471 		while (i < mx) {
    472 			f[i] = maxOf(f[i], x)
    473 			i = i or (i + 1)
    474 		}
    475 	}
    476 	
    477 	fun query(pos: Int) : Long {
    478 		var res = -INF
    479 		var i = pos
    480 		while (i >= 0) {
    481 			res = maxOf(res, f[i])
    482 			i = (i and (i + 1)) - 1
    483 		}
    484 		return res
    485 	}
    486 	
    487 	update(m - 1, 0L)
    488 	for (it in ev) {
    489 		val dp = query(it.i + it.b - 1) + it.a
    490 		update(it.i + it.b, dp)
    491 	}
    492 	println(query(mx - 1))
    493 }
    494 ```
    495 
    496 [1571H - Laser Beams](/contest/1571/problem/H "Kotlin Heroes: Episode 8")
    497 
    498 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    499 
    500 **Tutorial**
    501 
    502 Tutorial is loading...
    503 
    504 **Solution (pashka)**
    505 
    506 ```
    507 @file:Suppress("CanBeVal")
    508  
    509 import java.io.BufferedReader
    510 import java.io.InputStreamReader
    511 import java.io.OutputStreamWriter
    512 import java.io.PrintWriter
    513 import java.util.*
    514  
    515 private fun solveTest() {
    516     var n = readInt()
    517     var l = readInts()
    518     var r = readInts()
    519     var rr = r.toMutableList()
    520     rr.sort()
    521     var x = Integer.MAX_VALUE
    522     for (i in 0 until n) {
    523         x = minOf(x, rr[i] - i)
    524     }
    525     var a = (0 until n).toMutableList()
    526     a.sortBy { i -> l[i] }
    527     var j = 0
    528     var pq = PriorityQueue<Int>(compareBy { i -> r[i] })
    529     var res = intarr(n)
    530     for (t in x until x + n) {
    531         while (j < n && l[a[j]] <= t) {
    532             pq.add(a[j])
    533             j++
    534         }
    535         if (pq.isEmpty()) {
    536             println(-1)
    537             return
    538         }
    539         var q = pq.remove()
    540         if (r[q] < t) {
    541             println(-1)
    542             return
    543         }
    544         res[t - x] = q + 1
    545     }
    546     println(x)
    547     println(res)
    548 }
    549  
    550 private fun solve() {
    551     var t = readInt()
    552     while (t-- > 0) {
    553         solveTest()
    554     }
    555 }
    556  
    557 // TEMPLATE
    558 fun main(args: Array<String>) {
    559     reader = BufferedReader(InputStreamReader(System.`in`))
    560     out = PrintWriter(OutputStreamWriter(System.out))
    561     solve()
    562     out.close()
    563 }
    564  
    565 private lateinit var out: PrintWriter
    566 private lateinit var reader: BufferedReader
    567 private var tokenizer: StringTokenizer? = null
    568 private fun read(): String {
    569     while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
    570         tokenizer = StringTokenizer(readLn())
    571     }
    572     return tokenizer!!.nextToken()
    573 }
    574  
    575 private fun readInt() = read().toInt()
    576 private fun readLong() = read().toLong()
    577 private fun readLn() = reader.readLine()!!
    578 private fun readInts() = readLn().split(" ").map { it.toInt() }
    579 private fun readInts(sz: Int) = Array(sz) { readInt() }
    580 private fun readLongs() = readLn().split(" ").map { it.toLong() }
    581 private fun readLongs(sz: Int) = Array(sz) { readLong() }
    582 private fun print(b: Boolean) = out.print(b)
    583 private fun print(i: Int) = out.print(i)
    584 private fun print(d: Double) = out.print(d)
    585 private fun print(l: Long) = out.print(l)
    586 private fun print(s: String) = out.print(s)
    587 private fun print(message: Any?) = out.print(message)
    588 private fun print(a: Array<Int>) = a.forEach { print("$it ") }
    589 private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") }
    590 private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") }
    591 private fun println(b: Boolean) = out.println(b)
    592 private fun println(i: Int) = out.println(i)
    593 private fun println(d: Double) = out.println(d)
    594 private fun println(l: Long) = out.println(l)
    595 private fun println(s: String) = out.println(s)
    596 private fun println() = out.println()
    597 private fun println(message: Any?) = out.println(message)
    598 private fun <T> println(a: Array<out T>) {
    599     a.forEach { print("$it ") }
    600     println()
    601 }
    602  
    603 private fun println(a: IntArray) {
    604     a.forEach { print("$it ") }
    605     println()
    606 }
    607  
    608 private fun <T> println(a: Collection<T>) {
    609     a.forEach { print("$it ") }
    610     println()
    611 }
    612  
    613 private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v }
    614 private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v }
    615 private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) }
    616 private fun <T> init(vararg elements: T) = elements
    617 private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init }
    618 private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) }
    619 private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> {
    620     return Comparator { a, b ->
    621         val res = a.first.compareTo(b.first)
    622         if (res == 0) a.second.compareTo(b.second) else res
    623     }
    624 }
    625 ```
    626 
    627 [1571I - Physical Examination](/contest/1571/problem/I "Kotlin Heroes: Episode 8")
    628 
    629 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [awoo](/profile/awoo "International Grandmaster awoo")
    630 
    631 **Tutorial**
    632 
    633 Tutorial is loading...
    634 
    635 **Solution (awoo)**
    636 
    637 ```
    638 import java.util.*
    639 
    640 fun main() = repeat(readLine()!!.toInt()) {
    641 	val n = readLine()!!.toInt()
    642 	val L = readLine()!!.split(" ").map { it.toInt() }
    643 	val R = readLine()!!.split(" ").map { it.toInt() }
    644 	
    645 	val ord = Array(n, { i -> i })
    646 	ord.sortWith({x : Int, y: Int -> L[x] - L[y]})
    647 	
    648 	val ans = IntArray(n)
    649 	
    650 	fun check(m: Int, fl: Boolean): Int {
    651 		val cur = PriorityQueue<Int>(compareBy { R[it] })
    652 		var j = 0
    653 		var res = 0
    654 		for (t in m until m + n) {
    655 			while (j < n && L[ord[j]] <= t) {
    656 				cur.add(ord[j])
    657 				++j;
    658 			}
    659 			if (cur.isEmpty()) {
    660 				res = 1
    661 				break
    662 			}
    663 			if (R[cur.peek()] < t) {
    664 				res = -1
    665 				break
    666 			}
    667 			if (fl) ans[t - m] = cur.peek() + 1
    668 			cur.poll()
    669 		}
    670 		return res;
    671 	}
    672 	
    673 	var l = 1
    674 	var r = 1e9.toInt()
    675 	var res = -1
    676 	while (l <= r) {
    677 		val m = (l + r) / 2
    678 		val tmp = check(m, false)
    679 		if (tmp == 0) {
    680 			res = m
    681 			break
    682 		}
    683 		if (tmp == -1) {
    684 			r = m - 1
    685 		}
    686 		else {
    687 			l = m + 1
    688 		}
    689 	}
    690 	
    691 	println(res)
    692 	if (res != -1) {
    693 		check(res, true)
    694 		println(ans.joinToString(" "))
    695 	}
    696 }
    697 ```
    698 
    699 [1571J - Two Railroads](/contest/1571/problem/J "Kotlin Heroes: Episode 8")
    700 
    701 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    702 
    703 **Tutorial**
    704 
    705 Tutorial is loading...
    706 
    707 **Solution (pashka)**
    708 
    709 ```
    710 @file:Suppress("CanBeVal")
    711  
    712 import java.io.BufferedReader
    713 import java.io.InputStreamReader
    714 import java.io.OutputStreamWriter
    715 import java.io.PrintWriter
    716 import java.util.*
    717  
    718 private class SegmentTree(private val size: Int) {
    719  
    720     class Item(val a: Long) {
    721         fun add(item: Item): Item {
    722             return if (a < item.a) this else item
    723         }
    724     }
    725  
    726     val NEUTRAL = Item(Long.MAX_VALUE)
    727  
    728     private val a: Array<Item>
    729  
    730     operator fun set(i: Int, v: Item) {
    731         set(0, 0, size, i, v)
    732     }
    733  
    734     private operator fun set(n: Int, l: Int, r: Int, i: Int, v: Item) {
    735         if (r == l + 1) {
    736             a[n] = a[n].add(v)
    737         } else {
    738             val m = (l + r) / 2
    739             if (i < m) {
    740                 set(n * 2 + 1, l, m, i, v)
    741             } else {
    742                 set(n * 2 + 2, m, r, i, v)
    743             }
    744             a[n] = a[n * 2 + 1].add(a[n * 2 + 2])
    745         }
    746     }
    747  
    748     fun sum(l: Int, r: Int): Item {
    749         return sum(0, 0, size, l, r)
    750     }
    751  
    752     private fun sum(n: Int, ll: Int, rr: Int, l: Int, r: Int): Item {
    753         return if (ll >= l && rr <= r) {
    754             a[n]
    755         } else if (ll >= r || l >= rr) {
    756             NEUTRAL
    757         } else {
    758             val m = (ll + rr) / 2
    759             sum(n * 2 + 1, ll, m, l, r).add(sum(n * 2 + 2, m, rr, l, r))
    760         }
    761     }
    762  
    763     init {
    764         a = Array<Item>(4 * size) { NEUTRAL }
    765     }
    766 }
    767  
    768 private fun solveTest() {
    769     var n = readInt()
    770     var a = readLongs(n - 1)
    771     var b = readLongs(n - 1)
    772     var c = readLongs(n)
    773  
    774     var d = longarr(n - 1)
    775     for (i in d.indices) {
    776         d[i] = when (i) {
    777             0 -> minOf(b[i], c[i])
    778             n - 2 -> minOf(b[i], c[i + 1])
    779             else -> b[i]
    780         }
    781     }
    782     for (i in 1..n - 2) {
    783         d[i] = minOf(d[i], c[i] + d[i - 1])
    784     }
    785     for (i in n - 3 downTo 0) {
    786         d[i] = minOf(d[i], c[i + 1] + d[i + 1])
    787     }
    788     var st = SegmentTree(n - 1)
    789     for (i in 0..n - 2) {
    790         st[i] = SegmentTree.Item(d[i] + a[i])
    791     }
    792     var ul = longarr(n - 1)
    793     var s = 0L
    794     for (i in 0..n - 2) {
    795         s += c[i]
    796         ul[i] = s
    797     }
    798     var ur = longarr(n - 1)
    799     s = 0L
    800     for (i in n - 2 downTo 0) {
    801         s += c[i + 1]
    802         ur[i] = s
    803     }
    804     var stl = SegmentTree(n - 1)
    805     for (i in 0..n - 2) {
    806         stl[i] = SegmentTree.Item(a[i] + ul[i])
    807     }
    808     var str = SegmentTree(n - 1)
    809     for (i in 0..n - 2) {
    810         str[i] = SegmentTree.Item(a[i] + ur[i])
    811     }
    812  
    813     var q = readInt()
    814     while (q-- > 0) {
    815         var (l, r) = readInts(2)
    816         l--; r--
    817         var res = st.sum(l, r).a
    818         if (l > 0) {
    819             var s1 = stl.sum(l, r).a - ul[l - 1]
    820 //            var s2 = str.sum(0, l).a - ur[l - 1]
    821             res = minOf(res, s1)
    822         }
    823         if (r < n - 1) {
    824             var s1 = str.sum(l, r).a - ur[r]
    825 //            var s2 = stl.sum(r, n - 1).a - ul[r]
    826             res = minOf(res, s1)
    827         }
    828         println(res)
    829     }
    830  
    831  
    832 }
    833  
    834 private fun solve() {
    835 //    repeat(readInt()) {
    836         solveTest()
    837 //    }
    838 }
    839  
    840 // TEMPLATE
    841 fun main(args: Array<String>) {
    842     reader = BufferedReader(InputStreamReader(System.`in`))
    843     out = PrintWriter(OutputStreamWriter(System.out))
    844     solve()
    845     out.close()
    846 }
    847  
    848 private lateinit var out: PrintWriter
    849 private lateinit var reader: BufferedReader
    850 private var tokenizer: StringTokenizer? = null
    851 private fun read(): String {
    852     while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
    853         tokenizer = StringTokenizer(readLn())
    854     }
    855     return tokenizer!!.nextToken()
    856 }
    857  
    858 private fun readInt() = read().toInt()
    859 private fun readLong() = read().toLong()
    860 private fun readLn() = reader.readLine()!!
    861 private fun readInts() = readLn().split(" ").map { it.toInt() }
    862 private fun readInts(sz: Int) = Array(sz) { readInt() }
    863 private fun readLongs() = readLn().split(" ").map { it.toLong() }
    864 private fun readLongs(sz: Int) = Array(sz) { readLong() }
    865 private fun print(b: Boolean) = out.print(b)
    866 private fun print(i: Int) = out.print(i)
    867 private fun print(d: Double) = out.print(d)
    868 private fun print(l: Long) = out.print(l)
    869 private fun print(s: String) = out.print(s)
    870 private fun print(message: Any?) = out.print(message)
    871 private fun print(a: Array<Int>) = a.forEach { print("$it ") }
    872 private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") }
    873 private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") }
    874 private fun println(b: Boolean) = out.println(b)
    875 private fun println(i: Int) = out.println(i)
    876 private fun println(d: Double) = out.println(d)
    877 private fun println(l: Long) = out.println(l)
    878 private fun println(s: String) = out.println(s)
    879 private fun println() = out.println()
    880 private fun println(message: Any?) = out.println(message)
    881 private fun <T> println(a: Array<out T>) {
    882     a.forEach { print("$it ") }
    883     println()
    884 }
    885  
    886 private fun println(a: IntArray) {
    887     a.forEach { print("$it ") }
    888     println()
    889 }
    890  
    891 private fun <T> println(a: Collection<T>) {
    892     a.forEach { print("$it ") }
    893     println()
    894 }
    895  
    896 private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v }
    897 private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v }
    898 private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) }
    899 private fun <T> init(vararg elements: T) = elements
    900 private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init }
    901 private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) }
    902 private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> {
    903     return Comparator { a, b ->
    904         val res = a.first.compareTo(b.first)
    905         if (res == 0) a.second.compareTo(b.second) else res
    906     }
    907 }
    908 ```