[蓝桥杯 2023 国 B] 抓娃娃

Luogu
IDLGP9426
Time1000ms
Memory500MB
DifficultyP3
2023前缀和蓝桥杯国赛
小明拿了 $n$ 条线段练习抓娃娃。他将所有线段铺在数轴上,第 $i$ 条线段的左端点在 $l_i$,右端点在 $r_i$。小明用 $m$ 个区间去框这些线段,第 $i$ 个区间的范围是 $[L_i, R_i]$。如果一个线段有**至少一半**的长度被包含在某个区间内,则将其视为被这个区间框住。请计算出每个区间框住了多少个线段? ## Input 输入共 $n + m + 1$ 行。 第一行为两个正整数 $n, m$。 后面 $n$ 行,每行两个整数 $l_i, r_i$。 后面 $m$ 行,每行两个整数 $L_i, R_i$。 ## Output 输出共 $m$ 行,每行一个整数。 [samples] ## Note ### 评测用例规模与约定 - 对于 $20\%$ 的数据,保证 $n, m \le 10^3$。 - 对于 $100\%$ 的数据,保证 $n, m ≤ 10^5$,$l_i < r_i$,$0 < l_i, r_i, L_i, R_i \le 10^6$,$\max \{r_i − l_i\} \le \min \{R_i − L_i\}$。 第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组 H 题。
Samples
Input #1
3 2
1 2
1 3
3 4
1 4
2 4
Output #1
3
2
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯 2023 国 B] 抓娃娃",
    "description": {
      "content": "小明拿了 $n$ 条线段练习抓娃娃。他将所有线段铺在数轴上,第 $i$ 条线段的左端点在 $l_i$,右端点在 $r_i$。小明用 $m$ 个区间去框这些线段,第 $i$ 个区间的范围是 $[L_i, R_i]$。如果一个线段有**至少一半**的长度被包含在某个区间内,则将其视为被这个区间框住。请计算出每个区间框住了多少个线段?",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 512000
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9426"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小明拿了 $n$ 条线段练习抓娃娃。他将所有线段铺在数轴上,第 $i$ 条线段的左端点在 $l_i$,右端点在 $r_i$。小明用 $m$ 个区间去框这些线段,第 $i$ 个区间的范围是 $[L_i, R_i]$。如果一个线段有**至少一半**的长度被包含在某个区间内,则将其视为被这个区间框住。请计算出每个区间框住了多少个线段?\n\n## Input\n\n输入共 $n + m + 1$ 行。\n\n第一行...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments