Facebook
From Spheniscine, 1 Year ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 101
  1. @file:Suppress("NOTHING_TO_INLINE", "EXPERIMENTAL_FEATURE_WARNING", "OVERRIDE_BY_INLINE")
  2. @file:OptIn(ExperimentalStdlibApi::class)
  3.  
  4. import java.io.PrintWriter
  5. import java.util.TreeMap
  6. import kotlin.math.*
  7. import kotlin.random.Random
  8. import kotlin.collections.sort as _sort
  9. import kotlin.collections.sortDescending as _sortDescending
  10. import kotlin.io.println as iprintln
  11.  
  12.  
  13. /** @author Spheniscine */
  14. fun main() { _writer.solve(); _writer.flush() }
  15. fun PrintWriter.solve() {
  16. //    val startTime = System.nanoTime()
  17.  
  18.     val numCases = 1//readInt()
  19.     case@ for(case in 1..numCases) {
  20. //        print("Case #$case: ")
  21.  
  22.         object {
  23.             val n = readInt()
  24.  
  25.             val M = TreeMap<Int, Int>()
  26.             var lenB = 0
  27.  
  28.             fun add(l: Int, r: Int) {
  29.                 M[r] = l
  30.                 lenB += r - l
  31.             }
  32.  
  33.             fun rem(l: Int, r: Int) {
  34.                 M.remove(r)
  35.                 lenB -= r - l
  36.             }
  37.  
  38.             init {
  39.                 repeat(n) {
  40.                     val b = readChar() == 'B'
  41.                     var l = readInt()
  42.                     var r = l + readInt()
  43.  
  44.                     if(b) {
  45.                         while(true) {
  46.                             val (ri: Int, li: Int) = M.ceilingEntry(l) ?: break
  47.                             if(li > r) break
  48.  
  49.                             if(li < l) l = li
  50.                             if(ri > r) r = ri
  51.                             rem(li, ri)
  52.                         }
  53.                         add(l, r)
  54.                     } else {
  55.                         while(true) {
  56.                             val (ri: Int, li: Int) = M.higherEntry(l) ?: break
  57.                             if(li >= r) break
  58.  
  59.                             rem(li, ri)
  60.                             if(li < l) add(li, l)
  61.                             if(ri > r) add(r, ri)
  62.                         }
  63.                     }
  64.  
  65.                     println("${M.size} $lenB")
  66.                 }
  67.             }
  68.         }
  69.  
  70.     }
  71.  
  72. //    iprintln("Time: ${(System.nanoTime() - startTime) / 1000000} ms")
  73. }
  74.  
  75. /** IO */
  76. //const val PATH = "src/main/resources/"
  77. //@JvmField val INPUT = File(PATH + "input.txt").inputStream()
  78. //@JvmField val OUTPUT = File(PATH + "output.txt").outputStream()
  79. @JvmField val INPUT = System.`in`
  80. @JvmField val OUTPUT = System.out
  81.  
  82. const val _BUFFER_SIZE = 1 shl 16
  83. @JvmField val _buffer = ByteArray(_BUFFER_SIZE)
  84. @JvmField var _bufferPt = 0
  85. @JvmField var _bytesRead = 0
  86.  
  87. tailrec fun readChar(): Char {
  88.     if(_bufferPt == _bytesRead) {
  89.         _bufferPt = 0
  90.         _bytesRead = INPUT.read(_buffer, 0, _BUFFER_SIZE)
  91.     }
  92.     return if(_bytesRead < 0) Char.MIN_VALUE
  93.     else {
  94.         val c = _buffer[_bufferPt++].toChar()
  95.         if (c == '\r') readChar()
  96.         else c
  97.     }
  98. }
  99.  
  100. fun readLine(): String? {
  101.     var c = readChar()
  102.     return if(c == Char.MIN_VALUE) null
  103.     else buildString {
  104.         while(c != '\n' && c != Char.MIN_VALUE) {
  105.             append(c)
  106.             c = readChar()
  107.         }
  108.     }
  109. }
  110. fun readLn() = readLine()!!
  111.  
  112. fun read() = buildString {
  113.     var c = readChar()
  114.     while(c <= ' ') {
  115.         if(c == Char.MIN_VALUE) return@buildString
  116.         c = readChar()
  117.     }
  118.     do {
  119.         append(c)
  120.         c = readChar()
  121.     } while(c > ' ')
  122. }
  123. fun readInt() = read().toInt()
  124. fun readDouble() = read().toDouble()
  125. fun readLong() = read().toLong()
  126. fun readStrings(n: Int) = List(n) { read() }
  127. fun readLines(n: Int) = List(n) { readLn() }
  128. fun readInts(n: Int) = List(n) { read().toInt() }
  129. fun readIntArray(n: Int) = IntArray(n) { read().toInt() }
  130. fun readDoubles(n: Int) = List(n) { read().toDouble() }
  131. fun readDoubleArray(n: Int) = DoubleArray(n) { read().toDouble() }
  132. fun readLongs(n: Int) = List(n) { read().toLong() }
  133. fun readLongArray(n: Int) = LongArray(n) { read().toLong() }
  134.  
  135. @JvmField val _writer = PrintWriter(OUTPUT, false)
  136.  
  137. /**  sort overrides to avoid quicksort attacks */
  138.  
  139. @JvmField var _random: Random? = null
  140. val random get() = _random ?: Random(0x594E215C123 * System.nanoTime()).also { _random = it }
  141.  
  142. fun IntArray.sort() { shuffle(random); _sort() }
  143. fun IntArray.sortDescending() { shuffle(random); _sortDescending() }
  144.  
  145. fun LongArray.sort() { shuffle(random); _sort() }
  146. fun LongArray.sortDescending() { shuffle(random); _sortDescending() }
  147.  
  148. fun DoubleArray.sort() { shuffle(random); _sort() }
  149. fun DoubleArray.sortDescending() { shuffle(random); _sortDescending() }
  150.  
  151. inline fun CharArray.sort() { _sort() }
  152. inline fun CharArray.sortDescending() { _sortDescending() }
  153.  
  154. inline fun <T : Comparable<T>> Array<out T>.sort() = _sort()
  155. inline fun <T : Comparable<T>> Array<out T>.sortDescending() = _sortDescending()
  156. inline fun <T : Comparable<T>> MutableList<out T>.sort() = _sort()
  157. inline fun <T : Comparable<T>> MutableList<out T>.sortDescending() = _sortDescending()
  158.  
  159. // import preserving junk function
  160. @Suppress("NonAsciiCharacters") fun 雪花飄飄北風嘯嘯天地一片蒼茫() { iprintln(max(1, 2)) }