結果

問題 No.1441 MErGe
ユーザー yakamotoyakamoto
提出日時 2021-03-27 16:53:08
言語 Kotlin
(1.9.23)
結果
RE  
実行時間 -
コード長 10,362 bytes
コンパイル時間 19,391 ms
コンパイル使用メモリ 472,676 KB
実行使用メモリ 106,136 KB
最終ジャッジ日時 2024-11-29 08:21:50
合計ジャッジ時間 44,482 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 265 ms
49,804 KB
testcase_01 RE -
testcase_02 RE -
testcase_03 AC 373 ms
52,036 KB
testcase_04 AC 373 ms
52,404 KB
testcase_05 AC 412 ms
53,000 KB
testcase_06 AC 411 ms
52,792 KB
testcase_07 AC 399 ms
52,944 KB
testcase_08 AC 578 ms
74,440 KB
testcase_09 AC 581 ms
74,180 KB
testcase_10 AC 656 ms
85,024 KB
testcase_11 AC 695 ms
85,688 KB
testcase_12 AC 698 ms
85,024 KB
testcase_13 TLE -
testcase_14 AC 986 ms
103,256 KB
testcase_15 TLE -
testcase_16 AC 959 ms
106,136 KB
testcase_17 TLE -
testcase_18 AC 880 ms
98,544 KB
testcase_19 AC 920 ms
103,596 KB
testcase_20 AC 835 ms
91,944 KB
testcase_21 AC 783 ms
93,036 KB
testcase_22 AC 933 ms
100,244 KB
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 AC 829 ms
97,584 KB
testcase_29 AC 896 ms
97,600 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.kt:70:13: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types
    private inline fun fx(x1: Int, x2: Int) = x1 + x2
            ^
Main.kt:71:13: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types
    private inline fun ap(x: Int, m: Int) = m
            ^
Main.kt:71:27: warning: parameter 'x' is never used
    private inline fun ap(x: Int, m: Int) = m
                          ^
Main.kt:72:13: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types
    private inline fun fm(m1: Int, m2: Int) = m2
            ^
Main.kt:72:27: warning: parameter 'm1' is never used
    private inline fun fm(m1: Int, m2: Int) = m2
                          ^
Main.kt:73:13: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types
    private inline fun fp(m: Int, n: Int) = m*n
            ^
Main.kt:76:13: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types
    private inline fun contains(k: Int, x: Int): Boolean = false
            ^
Main.kt:76:33: warning: parameter 'k' is never used
    private inline fun contains(k: Int, x: Int): Boolean = false
                                ^
Main.kt:76:41: warning: parameter 'x' is never used
    private inline fun contains(k: Int, x: Int): Boolean = false
                                        ^
Main.kt:122:13: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types
    private inline fun push(k: Int, len: Int) {
            ^
Main.kt:132:13: warning: expected performance impact from inlining is insignificant. Inlining works best for functi

ソースコード

diff # 

import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.lang.AssertionError
import java.util.*
import kotlin.math.abs
import kotlin.math.max
import kotlin.math.min

val MOD = 1_000_000_007




class Solver(stream: InputStream, private val out: java.io.PrintWriter) {
  private val reader = BufferedReader(InputStreamReader(stream), 32768)

  fun solve() {
    val N = ni()
    val Q = ni()
    val A = na(N)
    val S = LongArray(N + 1)
    for (i in 0 until N) {
      S[i + 1] = S[i] + A[i]
    }
    val tree = DelayMergeTree(N)
    tree.build(IntArray(N + 1){1})
    for (q in 0 until Q) {
      val type = ni()
      val l0 = ni()
      val r0 = ni() + 1
      val l = tree.lowerBound(l0)
      val r = tree.lowerBound(r0)

      when(type) {
        1 -> {
          tree.apply(l + 1, r, 0)
        }
        else -> {
          val ans = S[r] - S[l]
          out.println(ans)
        }
      }
    }

  }


  inner class DelayMergeTree(val n: Int) {
    /*
      fx: x同士の結合
      fa: mをxに作用させる
      fm: 作用素を結合
      fp: (x1 + x2)*fp(m, n) == x1*fp(m, n/2) + x2*fp(m, n/2) <- fxが+だったらm*n

      (+, +)
      ↓の実装は区間sum、更新はaddの場合
     */
//  private inline fun fx(x1: Int, x2: Int) = x1 + x2
//  private inline fun ap(x: Int, m: Int) = x + m
//  private inline fun fm(m1: Int, m2: Int) = m1 + m2
//  private inline fun fp(m: Int, n: Int) = m*n
//  private val zeroX = 0L
//  private val zeroM = 0L
//  private inline fun contains(k: Int, x: Int): Boolean = false

    /*
      (+, 入れ替え)
     */
    private inline fun fx(x1: Int, x2: Int) = x1 + x2
    private inline fun ap(x: Int, m: Int) = m
    private inline fun fm(m1: Int, m2: Int) = m2
    private inline fun fp(m: Int, n: Int) = m*n
    private val zeroX = 0
    private val zeroM = -1
    private inline fun contains(k: Int, x: Int): Boolean = false

    /*
      (min, 入れ替え)
      こちらはmin、更新は入れ替えの場合
      更新のところにifいらないかも
     */
//  private inline fun fx(x1: Int, x2: Int) = min(x1, x2)
//  private inline fun ap(x: Int, m: Int) = if (m == zeroM) x else m
//  private inline fun fm(m1: Int, m2: Int) = if (m2 == zeroM) m1 else m2
//  private inline fun fp(m: Int, n: Int) = m
//  private val inf = 2e18.toInt() + 100
//  private val zeroX = inf
//  private val zeroM = inf
//  private inline fun contains(k: Int, x: Int): Boolean = value[k] < x

    /*
      (max, +)
    */
//  private inline fun fx(x1: Int, x2: Int) = max(x1, x2)
//  private inline fun ap(x: Int, m: Int) = x + m
//  private inline fun fm(m1: Int, m2: Int) = m1 + m2
//  private inline fun fp(m: Int, n: Int) = m
//  private val inf = 0L // マイナスありなら -(2e18.toInt + 100)
//  private val zeroX = inf
//  private val zeroM = inf
//  private inline fun contains(k: Int, x: Int): Boolean = value[k] > x

    /*
      (xor, 入れ替え)
     */
//  private inline fun fx(x1: Int, x2: Int) = x1 or x2
//  private inline fun ap(x: Int, m: Int) = m
//  private inline fun fm(m1: Int, m2: Int) = m2
//  private inline fun fp(m: Int, n: Int) = m
//  private val zeroX = 0L
//  private val zeroM = 0L
//  private inline fun contains(k: Int, x: Int): Boolean = false // min/maxじゃないと使えない

    private val log = log2_ceil(n)
    private val N = 1 shl log

    // zeroX, zeroMよりも前にあると初期化できなくなるので注意
    private val value = IntArray(N * 2){zeroX}
    private val delay = IntArray(N * 2){zeroM}

    private inline fun push(k: Int, len: Int) {
      if (delay[k] == zeroM) return
      if (k < N) {
        delay[k * 2] = fm(delay[k * 2], delay[k])
        delay[k * 2 + 1] = fm(delay[k * 2 + 1], delay[k])
      }
      value[k] = ap(value[k], fp(delay[k], len))
      delay[k] = zeroM
    }

    private inline fun pushAll(a: Int, b: Int) {
      val ka = a + N
      val kb = b + N
      for (j in log downTo 1) {
        push(ka shr j, N shr j)
        push(kb shr j, N shr j)
      }
    }

    fun build(A: IntArray) {
      for (i in A.indices) {
        value[N + i] = A[i]
      }
      for (k in N - 1 downTo 0) {
        value[k] = fx(value[k*2], value[k*2 + 1])
      }
    }

    /**
     * [a, b)
     */
    fun apply(a: Int, b: Int, x: Int, k: Int = 1, l: Int = 0, r: Int = N) {
      push(k, r - l)
      if (a >= r || l >= b) return // ノードが範囲からはずれてる
      if (a <= l && r <= b) { // ノードが完全に範囲に含まれる
        delay[k] = fm(delay[k], x)
        push(k, r - l)
        return
      }

      val m = (l + r) / 2
      val lft = k * 2
      val rgt = lft + 1
      apply(a, b, x, lft, l, m)
      apply(a, b, x, rgt, m, r)
      value[k] = fx(value[lft], value[rgt])
    }

    /**
     * [a, b)
     */
    fun prod(a: Int, b: Int): Int {
      pushAll(a, b)

      // 通り道のdelayを消費したので、後は普通のSegTreeと一緒

      var res = zeroX
      var left = a + N
      var right = b - 1 + N

      while(left <= right) {
        if ((left and 1) == 1) res = fx(res, value[left])
        if ((right and 1) == 0) res = fx(res, value[right])
        left = (left + 1) shr 1 // 右の子供なら右の親に移動
        right = (right - 1) shr 1 // 左の子供なら左の親に移動
      }

      return res

//      pushAll(a, b)
//
//      // delayを消費したので、後は普通のSegTreeと一緒
//
//      var res: Int = zeroX
//      var left = a + N
//      var right = b - 1 + N
//
//      while(left <= right) {
//        if ((left and 1) == 1) res = fx(res, value[left])
//        if ((right and 1) == 0) res = fx(res, value[right])
//        left = (left + 1) shr 1 // 右の子供なら右の親に移動
//        right = (right - 1) shr 1 // 左の子供なら左の親に移動
//      }
//
//      return res
    }

    fun get(i: Int): Int {
      val k = i + N
      for (j in log downTo 1) {
        push(k shr j, N shr j)
      }
      return value[k]
    }

    fun set(i: Int, x: Int) {
      val k = i + N
      for (j in log downTo 1) {
        push(k shr j, N shr j)
      }
      value[k] = x
      for (j in 1 .. log) {
        val kk = k shr j
        value[kk] = fx(value[kk*2], value[kk*2 + 1])
      }
    }

    /**
     * @param x 左右どちらからか最初に contains になる場所を探す。containsはfxがmin/maxかで違う
     * @param fromR 右から探すか
     * @return 見つからなかったら -1
     */
    fun query(x: Int, k: Int = 1, l: Int = 0, r: Int = N, fromR: Boolean = true): Int {
      push(k, r - l)
      if (!contains(k, x)) return -1
      if (l + 1 == r) return l

      val m = (l + r) / 2
      val lft = k * 2
      val rgt = lft + 1

      if (fromR) {
        val ans = query(x, rgt, m, r, fromR)
        if (ans != -1) return ans
        return query(x, lft, l, m, fromR)
      }
      else {
        val ans = query(x, lft, l, m, fromR)
        if (ans != -1) return ans
        return query(x, rgt, m, r, fromR)
      }
    }

    /**
     * @return 最初にvalue>=xになるindexを返す。0-indexed 見つからなかったら n
     * fxがsum かつ 値に負がないことが条件
     */
    fun lowerBound(x: Int): Int {
      var remain = x
      var k = 1
      var len = N
      var res = 0
      push(1, N)
      for (i in 1 .. log) {
        push(k*2, len/2)
        if (value[k*2] < remain) {
          remain -= value[k*2]
          res += len/2
          push(k*2 + 1, len/2)
          k = k*2 + 1
        }
        else {
          k *= 2
        }
        len /= 2
      }
      return min(n, res)
    }

    fun inspect() = run { Pair(value, delay) }


    /**
     * 最初に x<=2^k になるkを返す
     */
    fun log2_ceil(x: Int): Int {
      var k = 0
      var pow2 = 1
      while(pow2 < x) {
        pow2 *= 2
        k++
      }
      return k
    }
  }











































  private val isDebug = try {
    // なんか本番でエラーでる
    System.getenv("MY_DEBUG") != null
  } catch (t: Throwable) {
    false
  }

  private var tokenizer: StringTokenizer? = null
  private fun next(): String {
    while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
      tokenizer = StringTokenizer(reader.readLine())
    }
    return tokenizer!!.nextToken()
  }

  private fun ni() = next().toInt()
  private fun nl() = next().toLong()
  private fun ns() = next()
  private fun na(n: Int, offset: Int = 0): IntArray {
    return IntArray(n) { ni() + offset }
  }
  private fun nal(n: Int, offset: Int = 0): LongArray {
    val res = LongArray(n)
    for (i in 0 until n) {
      res[i] = nl() + offset
    }
    return res
  }

  private fun na2(n: Int, offset: Int = 0): Array<IntArray> {
    val a  = Array(2){IntArray(n)}
    for (i in 0 until n) {
      for (e in a) {
        e[i] = ni() + offset
      }
    }
    return a
  }

  private inline fun debug(msg: () -> String) {
    if (isDebug) System.err.println(msg())
  }

  /**
   * コーナーケースでエラー出たりするので、debug(dp[1])のように添え字付きの場合はdebug{}をつかうこと
   */
  private inline fun debug(a: LongArray) {
    debug { a.joinToString(" ") }
  }

  private inline fun debug(a: IntArray) {
    debug { a.joinToString(" ") }
  }

  private inline fun debug(a: BooleanArray) {
    debug { toString(a) }
  }

  private inline fun toString(a: BooleanArray) = run{a.map { if (it) 1 else 0 }.joinToString("")}

  private inline fun debugDim(A: Array<LongArray>) {
    if (isDebug) {
      for (a in A) {
        debug(a)
      }
    }
  }
  private inline fun debugDim(A: Array<IntArray>) {
    if (isDebug) {
      for (a in A) {
        debug(a)
      }
    }
  }
  private inline fun debugDim(A: Array<BooleanArray>) {
    if (isDebug) {
      for (a in A) {
        debug(a)
      }
    }
  }

  /**
   * 勝手にimport消されるのを防ぎたい
   */
  private fun hoge() {
    min(1, 2)
    max(1, 2)
    abs(-10)
  }

  private inline fun assert(b: Boolean) = run{if (!b) throw AssertionError()}
  private inline fun assert(b: Boolean, f: () -> String) = run{if (!b) throw AssertionError(f())}
}

fun main() {
  val out = java.io.PrintWriter(System.out)
  Solver(System.`in`, out).solve()
  out.flush()
}
0