[ROIR 2023] 扫地机器人 (Day 1)

Luogu

IDLGP10096

Time1000ms

Memory512MB

DifficultyP5

线段树2023离散化Special Judge扫描线ROIR（俄罗斯）

给定一个由 $n$ 个移动操作组成的序列，第 $i$ 个移动操作由方向 $d_i$（`N` 表示向上，增加 $y$ 坐标；`E` 表示向右，增加 $x$ 坐标；`W` 表示向左，减小 $x$ 坐标；`S` 表示向下，减小 $y$ 坐标）和距离 $a_i$（机器人移动的距离）组成。根据给定的机器人移动操作，计算清扫的总面积（被机器人覆盖过的点就算被清扫过的点）。 ## Input 第一行包含两个整数，机器人的大小 $k$ 和操作数量 $n$。接下来的 $n$ 行中，每行包含一个移动操作和对应的距离 $a_i$。移动操作用字母 $d_i$ 表示（`N` 即向上，`E` 即向右，`W` 即向左，`S` 即向下），且距离 $a_i$ 是一个整数。 ## Output 输出机器人清扫的总面积。 [samples] ## Background 翻译自 [ROIR 2023 D1T3](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day1.pdf)。一个扫地机器人正在清洁一个二维坐标平面。扫地机器人是一个边长 $k\times k$ 的正方形，边与坐标轴平行。初始时，扫地机器人左下角位于 $(0,0)$，右上角位于 $(k,k)$。 ## Note 样例解释：下图是两个样例中机器人的移动情况。 ![](https://cdn.luogu.com.cn/upload/image_hosting/v8w6xnzb.png) #### 数据规模和约定 **本题使用捆绑测试。** |子任务编号|分值 |$k$ |$n$ |$a_i$ | |:---:|:--:|:--------:|:--------:|:--------:| |$1$ |$9$ |$= 1$ |$\le 10$ |$\le 10$ | |$2$ |$10$|$\le 10$ |^ |$\le 100$ | |$3$ |$11$|$\le 1000$|$\le 1000$|$= 1$ | |$4$ |$8$ |$\le 10^4$|$\le 10^5$|$= k$ | |$5$ |$14$|$=1$ |$\le 1000$|$\le 10^9$| |$6$ |$15$|$\le 10^4$|^ |^ | |$7$ |$16$|$= 1$ |$\le 10^5$|^ | |$8$ |$17$|$\le 10^4$|^ |^ | 对于 $100\%$ 的数据，$1 \le k \le 10^4$，$1 \le n \le 10^5$，$1 \le a_i \le 10^9$。

Samples

Input #1

1 5
E 2
N 2
W 4
S 4
E 4

Output #1

Input #2

3 4
W 2
N 1
W 1
N 2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[ROIR 2023] 扫地机器人 (Day 1)",
    "description": {
      "content": "给定一个由 $n$ 个移动操作组成的序列，第 $i$ 个移动操作由方向 $d_i$（`N` 表示向上，增加 $y$ 坐标；`E` 表示向右，增加 $x$ 坐标；`W` 表示向左，减小 $x$ 坐标；`S` 表示向下，减小 $y$ 坐标）和距离 $a_i$（机器人移动的距离）组成。根据给定的机器人移动操作，计算清扫的总面积（被机器人覆盖过的点就算被清扫过的点）。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10096"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个由 $n$ 个移动操作组成的序列，第 $i$ 个移动操作由方向 $d_i$（`N` 表示向上，增加 $y$ 坐标；`E` 表示向右，增加 $x$ 坐标；`W` 表示向左，减小 $x$ 坐标；`S` 表示向下，减小 $y$ 坐标）和距离 $a_i$（机器人移动的距离）组成。根据给定的机器人移动操作，计算清扫的总面积（被机器人覆盖过的点就算被清扫过的点）。\n\n## Input\n\n第一行包含两个...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments