{"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第一行包含两个整数，机器人的大小 $k$ 和操作数量 $n$。\n\n接下来的 $n$ 行中，每行包含一个移动操作和对应的距离 $a_i$。移动操作用字母 $d_i$ 表示（`N` 即向上，`E` 即向右，`W` 即向左，`S` 即向下），且距离 $a_i$ 是一个整数。\n\n## Output\n\n输出机器人清扫的总面积。\n\n[samples]\n\n## Background\n\n翻译自 [ROIR 2023 D1T3](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day1.pdf)。\n\n一个扫地机器人正在清洁一个二维坐标平面。扫地机器人是一个边长 $k\\times k$ 的正方形，边与坐标轴平行。初始时，扫地机器人左下角位于 $(0,0)$，右上角位于 $(k,k)$。\n\n## Note\n\n样例解释：下图是两个样例中机器人的移动情况。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/v8w6xnzb.png)\n\n#### 数据规模和约定\n\n**本题使用捆绑测试。**\n\n|子任务编号|分值  |$k$       |$n$       |$a_i$     |\n|:---:|:--:|:--------:|:--------:|:--------:|\n|$1$  |$9$ |$= 1$     |$\\le 10$  |$\\le 10$  |\n|$2$  |$10$|$\\le 10$  |^         |$\\le 100$ |\n|$3$  |$11$|$\\le 1000$|$\\le 1000$|$= 1$     |\n|$4$  |$8$ |$\\le 10^4$|$\\le 10^5$|$= k$     |\n|$5$  |$14$|$=1$      |$\\le 1000$|$\\le 10^9$|\n|$6$  |$15$|$\\le 10^4$|^         |^         |\n|$7$  |$16$|$= 1$     |$\\le 10^5$|^         |\n|$8$  |$17$|$\\le 10^4$|^         |^         |\n\n对于 $100\\%$ 的数据，$1 \\le k \\le 10^4$，$1 \\le n \\le 10^5$，$1 \\le a_i \\le 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10096","tags":["线段树","2023","离散化","Special Judge","扫描线","ROIR（俄罗斯）"],"sample_group":[["1 5\nE 2\nN 2\nW 4\nS 4\nE 4","17"],["3 4\nW 2\nN 1\nW 1\nN 2","27"]],"created_at":"2026-03-03 11:09:25"}}