[COCI 2022/2023 #1] Iksevi

Luogu

IDLGP9031

Time3000ms

Memory512MB

DifficultyP5

2022COCI（克罗地亚）

Vinko 需要使用正方形瓷砖铺满音乐厅的地板。他不会让瓷砖的边与墙壁平行；相反，他选择让瓷砖的对角线与墙壁平行。 Vinko 还没有决定他将使用的瓷砖大小，但他知道所有瓷砖必须大小相同，而且对角线的长度必须是一个正偶数。 Vinko 铺下的第一块瓷砖的角将与左侧和后方的墙接触。此后他铺下的每一块瓷砖都与至少一块已铺好的瓷砖有一条边重合。他将重复这以一过程，直到铺满整个 $10^7 \times 10^7$ 平方毫米的地面。除了程序员和陶艺家，Vinko 也是一个优秀的音乐家。正因为如此，他知道地板上有 $n$ 个点对大厅的音响效果至关重要。如果瓷砖的角落位于 $n$ 个点中的一个，大厅的声学效果将显著改善。 ![](https://cdn.luogu.com.cn/upload/image_hosting/o4bbstj2.png) 如图，左图为瓷砖对角线长度为 $4$ 的铺装，在此条件下，点 $(2,4)$ 在瓷砖的角落上，此时它满足条件，使得音响效果大为改善，但点 $(4,3)$ 和 $(5,1)$ 不满足条件。右图则为瓷砖对角线长度为 $2$ 的铺装，此时点 $(4,3)$ 在四块瓷砖的角落，而点 $(2,4)$ 和 $(5,1)$ 不在。帮助 Vinko 确定对于 $n$ 个点中的每个点，有多少种瓷砖尺寸可以使铺满地面后第 $i$ 个点位于瓷砖的角落上。 ## Input 第一行包含一个整数 $n$，即声学关键点的数目。接下来 $n$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 个声学关键点与左侧墙壁与后方墙壁的距离。 ## Output 输出 $n$ 行，每行一个整数。第 $i$ 行表示能使 $i$ 号声学关键点位于瓷砖角落的瓷砖尺寸数。 [samples] ## Background 写了十年的代码后，Vinko 决定转行做一名陶艺家。他在新工作的第一天就接到了一项艰巨的任务。 ## Note | 子任务 | 分值 | 数据范围 | | :-----------: | :-----------: | :-----------: | | $1$ | $15$ | $1\leq n \leq 10^4,0\leq x_i,y_i \leq 100$ | | $2$ | $55$ | $1\leq n \leq 10^4,0\leq x_i,y_i \leq 10^7$ | | $3$ | $40$ | $1\leq n \leq 10^6,0\leq x_i,y_i \leq 10^7$ | 本题满分 $110$ 分。

Samples

Input #1

Output #1

1
0
3

Input #2

Output #2

0
1
1

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2022/2023 #1] Iksevi",
    "description": {
      "content": "Vinko 需要使用正方形瓷砖铺满音乐厅的地板。他不会让瓷砖的边与墙壁平行；相反，他选择让瓷砖的对角线与墙壁平行。 Vinko 还没有决定他将使用的瓷砖大小，但他知道所有瓷砖必须大小相同，而且对角线的长度必须是一个正偶数。 Vinko 铺下的第一块瓷砖的角将与左侧和后方的墙接触。此后他铺下的每一块瓷砖都与至少一块已铺好的瓷砖有一条边重合。他将重复这以一过程，直到铺满整个 $10^7 \\time",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9031"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Vinko 需要使用正方形瓷砖铺满音乐厅的地板。他不会让瓷砖的边与墙壁平行；相反，他选择让瓷砖的对角线与墙壁平行。\n\nVinko 还没有决定他将使用的瓷砖大小，但他知道所有瓷砖必须大小相同，而且对角线的长度必须是一个正偶数。\n\nVinko 铺下的第一块瓷砖的角将与左侧和后方的墙接触。此后他铺下的每一块瓷砖都与至少一块已铺好的瓷砖有一条边重合。他将重复这以一过程，直到铺满整个 $10^7 \\time...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments