← 返回题目列表

Codeforces · 243/C

C. 科罗拉多马铃薯甲虫

中文机器翻译题面 查看原题

老麦克唐纳有一个农场和一大片土豆田,面积为(1010+1)×(1010+1)平方米。场地被划分为方形花园床,每个花园占地一平方米。

老麦克唐纳知道科罗拉多马铃薯甲虫即将入侵他的农场,并可能毁掉整个收成。为了对抗昆虫,老麦克唐纳想在一些床上喷洒杀虫剂。

于是老麦克唐纳来到了田地里,站在中央田床的中央,给这张床喷洒了杀虫剂。现在他要做一系列的动作,再喷几张床。在每次移动过程中,老麦克唐纳在球场上向左、向右、向上或向下移动整数米。老麦克唐纳一边走一边喷洒他踩过的所有床铺。换句话说,与老麦当劳轨迹有任何交集的床都喷洒了杀虫剂。

老麦克唐纳喷完后,将自己的所有动作都写在了一张纸上。现在他想知道在科罗拉多甲虫入侵后有多少张床不会被感染。

众所周知,科罗拉多甲虫的入侵过程如下。首先,田野边界上的一些床被感染。与任何没有被感染、没有喷洒杀虫剂并且与被感染的床有共同面的床一样,也会被感染。帮助老麦克唐纳确定不会被科罗拉多马铃薯甲虫感染的床铺数量。

输入

第一行包含一个整数 n (1 ≤ n ≤ 1000) — 老麦当劳的移动次数。

接下来的 n 行包含老麦当劳动作的描述。这些行中的第 i 行描述了第 i 个运动。每个运动以“di xi”格式给出,其中 di 是确定运动方向的字符(相应地,“L”、“R”、“U”或“D”分别表示方向“左”、“右”、“上”和“下”),xi (1 ≤ xi ≤ 106) 是一个整数,用于确定运动中的米数。

输出

打印一个整数 - 不会被科罗拉多马铃薯甲虫感染的床的数量。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

5
R 8
U 9
L 9
D 8
L 2

输出 #1

101

输入 #2

7
R 10
D 2
L 7
U 9
D 2
R 3
D 10

输出 #2

52