F. Julia the snail

Codeforces
IDCF793F
Time2000ms
Memory512MB
Difficulty—
data structuresdivide and conquerdp
English · Original
Chinese · Translation
Formal · Original
After hard work Igor decided to have some rest. He decided to have a snail. He bought an aquarium with a slippery tree trunk in the center, and put a snail named Julia into the aquarium. Igor noticed that sometimes Julia wants to climb onto the trunk, but can't do it because the trunk is too slippery. To help the snail Igor put some ropes on the tree, fixing the lower end of the _i_\-th rope on the trunk on the height _l__i_ above the ground, and the higher end on the height _r__i_ above the ground. For some reason no two ropes share the same position of the higher end, i.e. all _r__i_ are distinct. Now Julia can move down at any place of the trunk, and also move up from the lower end of some rope to its higher end. Igor is proud of his work, and sometimes think about possible movements of the snail. Namely, he is interested in the following questions: «Suppose the snail is on the trunk at height _x_ now. What is the highest position on the trunk the snail can get on if it would never be lower than _x_ or higher than _y_?» Please note that Julia can't move from a rope to the trunk before it reaches the higher end of the rope, and Igor is interested in the highest position **on the tree trunk**. Igor is interested in many questions, and not always can answer them. Help him, write a program that answers these questions. ## Input The first line contains single integer _n_ (1  ≤  _n_ ≤  100000) — the height of the trunk. The second line contains single integer _m_ (1  ≤  _m_  ≤  100000) — the number of ropes. The next _m_ lines contain information about the ropes. The _i_\-th of these lines contains two integers _l__i_ and _r__i_ (1  ≤ _l__i_ ≤ _r__i_ ≤ _n_) — the heights on which the lower and the higher ends of the _i_\-th rope are fixed, respectively. It is guaranteed that all _r__i_ are distinct. The next line contains single integer _q_ (1  ≤  _q_  ≤  100000) — the number of questions. The next _q_ lines contain information about the questions. Each of these lines contain two integers _x_ and _y_ (1  ≤ _x_ ≤ _y_ ≤ _n_), where _x_ is the height where Julia starts (and the height Julia can't get lower than), and _y_ is the height Julia can't get higher than. ## Output For each question print the maximum reachable for Julia height. [samples] ## Note The picture of the first sample is on the left, the picture of the second sample is on the right. Ropes' colors are just for clarity, they don't mean anything. <center>![image](https://espresso.codeforces.com/da764e6f0677013b27a050683365aadf7441667d.png)</center>
经过辛勤的工作，Igor 决定休息一下。 他决定养一只蜗牛。他买了一个水族箱，中间有一根光滑的树干，并将一只名叫 Julia 的蜗牛放入水族箱中。 Igor 发现，有时 Julia 想要爬到树干上，但由于树干太滑而无法做到。为了帮助蜗牛，Igor 在树干上放置了一些绳子，将第 #cf_span[i] 根绳子的下端固定在离地高度为 #cf_span[li] 的位置，上端固定在离地高度为 #cf_span[ri] 的位置。 出于某种原因，没有任何两根绳子的上端位于同一高度，即所有 #cf_span[ri] 互不相同。现在 Julia 可以在树干的任意位置向下移动，也可以从某根绳子的下端向上移动到其上端。Igor 为自己的工作感到自豪，有时会思考蜗牛可能的移动方式。具体来说，他感兴趣于以下问题：“假设蜗牛现在位于树干高度为 #cf_span[x] 的位置，如果它不能低于 #cf_span[x] 且不能高于 #cf_span[y]，那么它能达到的最高位置是多少？” 请注意，Julia 不能在到达绳子的上端之前从绳子移动到树干，而 Igor 关心的是树干上的最高位置。 Igor 对许多问题感兴趣，但并非总能回答。请帮助他，编写一个程序来回答这些问题。 第一行包含一个整数 #cf_span[n] (#cf_span[1  ≤  n ≤  100000]) —— 树干的高度。 第二行包含一个整数 #cf_span[m] (#cf_span[1  ≤  m  ≤  100000]) —— 绳子的数量。 接下来的 #cf_span[m] 行描述了每根绳子的信息。 第 #cf_span[i] 行包含两个整数 #cf_span[li] 和 #cf_span[ri] (#cf_span[1  ≤ li ≤ ri ≤ n])，分别表示第 #cf_span[i] 根绳子下端和上端固定的高度。保证所有 #cf_span[ri] 互不相同。 下一行包含一个整数 #cf_span[q] (#cf_span[1  ≤  q  ≤  100000]) —— 问题的数量。 接下来的 #cf_span[q] 行描述了每个问题。 每行包含两个整数 #cf_span[x] 和 #cf_span[y] (#cf_span[1  ≤ x ≤ y ≤ n])，其中 #cf_span[x] 是 Julia 的起始高度（也是 Julia 不能低于的高度），#cf_span[y] 是 Julia 不能超过的高度。 对于每个问题，请输出 Julia 能够到达的最大高度。 第一个样例的图示在左侧，第二个样例的图示在右侧。绳子的颜色仅用于清晰区分，没有其他含义。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1  ≤  n ≤  100000]) —— 树干的高度。第二行包含一个整数 #cf_span[m] (#cf_span[1  ≤  m  ≤  100000]) —— 绳子的数量。接下来的 #cf_span[m] 行描述了每根绳子的信息。第 #cf_span[i] 行包含两个整数 #cf_span[li] 和 #cf_span[ri] (#cf_span[1  ≤ li ≤ ri ≤ n])，分别表示第 #cf_span[i] 根绳子下端和上端固定的高度。保证所有 #cf_span[ri] 互不相同。下一行包含一个整数 #cf_span[q] (#cf_span[1  ≤  q  ≤  100000]) —— 问题的数量。接下来的 #cf_span[q] 行描述了每个问题。每行包含两个整数 #cf_span[x] 和 #cf_span[y] (#cf_span[1  ≤ x ≤ y ≤ n])，其中 #cf_span[x] 是 Julia 的起始高度（也是 Julia 不能低于的高度），#cf_span[y] 是 Julia 不能超过的高度。 ## Output 对于每个问题，请输出 Julia 能够到达的最大高度。 [samples] ## Note 第一个样例的图示在左侧，第二个样例的图示在右侧。绳子的颜色仅用于清晰区分，没有其他含义。
**Definitions** Let $ n \in \mathbb{Z}^+ $ be the height of the trunk. Let $ m \in \mathbb{Z}^+ $ be the number of ropes. Let $ R = \{ (l_i, r_i) \mid i \in \{1, \dots, m\} \} $ be the set of ropes, where $ 1 \le l_i \le r_i \le n $, and all $ r_i $ are distinct. Let $ q \in \mathbb{Z}^+ $ be the number of queries. Each query is a pair $ (x, y) $ with $ 1 \le x \le y \le n $. **Constraints** 1. $ 1 \le n \le 100000 $ 2. $ 1 \le m \le 100000 $ 3. $ 1 \le q \le 100000 $ 4. For each rope $ (l_i, r_i) $: $ 1 \le l_i \le r_i \le n $, and $ r_i $ are pairwise distinct. 5. For each query $ (x, y) $: $ 1 \le x \le y \le n $ **Objective** For each query $ (x, y) $, compute the maximum height $ h \in [x, y] $ reachable by Julia starting from height $ x $, under the following rules: - Julia can move downward freely along the trunk. - Julia can move upward along a rope $ (l_i, r_i) $ **only if** she is at height $ l_i $, and then she reaches height $ r_i $. - Julia **cannot** leave a rope before reaching its upper end $ r_i $. - Julia **cannot** go below $ x $ or above $ y $. - The goal is to find the maximum $ h \in [x, y] $ reachable from $ x $ via any sequence of rope ascents and trunk descents.
Samples
Input #1
8
4
1 2
3 4
2 5
6 7
5
1 2
1 4
1 6
2 7
6 8
Output #1
2
2
5
5
7
Input #2
10
10
3 7
1 4
1 6
5 5
1 1
3 9
7 8
1 2
3 3
7 10
10
2 4
1 7
3 4
3 5
2 8
2 5
5 5
3 5
7 7
3 10
Output #2
2
7
3
3
2
2
5
3
7
10
API Response (JSON) 
{
  "problem": {
    "name": "F. Julia the snail",
    "description": {
      "content": "After hard work Igor decided to have some rest. He decided to have a snail. He bought an aquarium with a slippery tree trunk in the center, and put a snail named Julia into the aquarium. Igor notice",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF793F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "After hard work Igor decided to have some rest.\n\nHe decided to have a snail. He bought an aquarium with a slippery tree trunk in the center, and put a snail named Julia into the aquarium.\n\nIgor notice...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "经过辛勤的工作，Igor 决定休息一下。\n\n他决定养一只蜗牛。他买了一个水族箱，中间有一根光滑的树干，并将一只名叫 Julia 的蜗牛放入水族箱中。\n\nIgor 发现，有时 Julia 想要爬到树干上，但由于树干太滑而无法做到。为了帮助蜗牛，Igor 在树干上放置了一些绳子，将第 #cf_span[i] 根绳子的下端固定在离地高度为 #cf_span[li] 的位置，上端固定在离地高度为 #cf_...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the height of the trunk.  \nLet $ m \\in \\mathbb{Z}^+ $ be the number of ropes.  \nLet $ R = \\{ (l_i, r_i) \\mid i \\in \\{1, \\dots, m\\} \\} $ be the set of ro...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments
© Rotriw 2026. 若您有相关疑问请联系 issue@rmj.ac