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 ```