General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
54686628 Contestant:
limed
1168C - 23 Scala Accepted 1216 ms 68008 KB 2019-05-26 19:52:10 2019-05-26 21:08:21
 
 
→ Source
object C extends App {

  @inline def tokenizeLine = new java.util.StringTokenizer(scala.io.StdIn.readLine)
  def readInts(n: Int) = { val tl = tokenizeLine; Array.fill(n)(tl.nextToken.toInt) }
  def readLongs(n: Int) = { val tl = tokenizeLine; Array.fill(n)(tl.nextToken.toLong) }
  def readBigs(n: Int) = { val tl = tokenizeLine; Array.fill(n)(BigInt(tl.nextToken)) }

  val Array(n, q) = readInts(2)
  val as = readInts(n)

  val BITS = 20
  @inline def bit(i: Int) = 1 << i

  val minReachableWith = Array.fill(BITS){ n + 1 }
  for (b <- 0 until BITS) {
    if ((as.last & bit(b)) > 0) minReachableWith(b) = n - 1
  }

  val minReachable = Array.fill(n, BITS){ n + 1 }

  for (i <- n - 2 to 0 by -1) {
    val a = as(i)
    var b = 0
    while (b < BITS) {
      if ((a & bit(b)) > 0) {
        if (minReachableWith(b) < n) {
          val j = minReachableWith(b)
          var b2 = 0
          while (b2 < BITS) {
            if (minReachable(j)(b2) < minReachable(i)(b2)) minReachable(i)(b2) = minReachable(j)(b2)
            b2 += 1
          }
        }
        minReachableWith(b) = i
        minReachable(i)(b) = i
      }
      b += 1
    }
    var b2 = 0
    while (b2 < BITS) {
      if (minReachable(i)(b2) < minReachableWith(b2)) minReachableWith(b2) = minReachable(i)(b2)
      b2 += 1
    }
  }

  val reachable = Array.fill(q)(false)
  for (i <- 0 until q) {
    val Array(l0, r0) = readInts(2)
    val l = l0 - 1
    val r = r0 - 1
    var b = 0
    while (b < BITS) {
      if ((as(r) & bit(b)) > 0 && minReachable(l)(b) <= r) reachable(i) = true
      b += 1
    }
  }

  Console.setOut(new java.io.BufferedOutputStream(Console.out))

  println(reachable.map(if (_) "Shi" else "Fou").mkString("\n"))

  Console.flush
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details