はじめに

B問題を再帰で解こうとしたらREで無理でした。（参考: http://abc024.contest.atcoder.jp/submissions/415693）では、Cなら行けるのではなかろうか、だって再帰の深さ1000程度だし。10⁵ と比べたらだいぶ小さいし。

というわけで書きました。

ソースコード

if式の部分がちょっと汚いですが許してください

import java.util.Scanner
 
object Main {
  val sc = new Scanner(System.in)
 
  def main(args: Array[String]): Unit = {
    val n, d, k = sc.nextInt()
    val list = for(i <- 1 to d) yield (sc.nextInt(), sc.nextInt())
    
    for(i <- 1 to k)
      println(solve(sc.nextInt(), sc.nextInt(), list.toList))
  }
  
  def solve(s: Int, t: Int, list: List[(Int, Int)]): Int = list match {
    case Nil => return 0
    case (l, r) :: cdr => {
      if(l <= s && s <= r){
        // 範囲に入っている場合
        if(l <= t && t <= r){
          // もうゴールしてもいいよね
          1
        }else if(t < s){
          // 左まで行く
          1 + solve(l, t, cdr)
        }else{
          // 右まで行く
          1 + solve(r, t, cdr)
        }
      }else{
        // 範囲に入っていない場合
        1 + solve(s, t, cdr)
      }
    }
  }
}