E. Sleep in Class

Codeforces

IDCF733E

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsdata structuresmathtwo pointers

English · Original

Chinese · Translation

Formal · Original

The academic year has just begun, but lessons and olympiads have already occupied all the free time. It is not a surprise that today Olga fell asleep on the Literature. She had a dream in which she was on a stairs. The stairs consists of _n_ steps. The steps are numbered from bottom to top, it means that the lowest step has number 1, and the highest step has number _n_. Above each of them there is a pointer with the direction (up or down) Olga should move from this step. As soon as Olga goes to the next step, the direction of the pointer (above the step she leaves) changes. It means that the direction "up" changes to "down", the direction "down" — to the direction "up". Olga always moves to the next step in the direction which is shown on the pointer above the step. If Olga moves beyond the stairs, she will fall and wake up. Moving beyond the stairs is a moving down from the first step or moving up from the last one (it means the _n_\-th) step. In one second Olga moves one step up or down according to the direction of the pointer which is located above the step on which Olga had been at the beginning of the second. For each step find the duration of the dream if Olga was at this step at the beginning of the dream. Olga's fall also takes one second, so if she was on the first step and went down, she would wake up in the next second. ## Input The first line contains single integer _n_ (1 ≤ _n_ ≤ 106) — the number of steps on the stairs. The second line contains a string _s_ with the length _n_ — it denotes the initial direction of pointers on the stairs. The _i_\-th character of string _s_ denotes the direction of the pointer above _i_\-th step, and is either '_U_' (it means that this pointer is directed up), or '_D_' (it means this pointed is directed down). The pointers are given in order from bottom to top. ## Output Print _n_ numbers, the _i_\-th of which is equal either to the duration of Olga's dream or to - 1 if Olga never goes beyond the stairs, if in the beginning of sleep she was on the _i_\-th step. [samples]

[{"iden":"statement","content":"学年刚刚开始，但课程和竞赛已经占据了所有空闲时间。难怪今天奥尔加在文学课上睡着了。她做了一个梦，梦见自己站在楼梯上。\n\n楼梯共有 #cf_span[n] 级台阶。台阶从下到上编号，即最低的台阶编号为 #cf_span[1]，最高的台阶编号为 #cf_span[n]。每个台阶上方有一个指示方向的指针（向上或向下），表示奥尔加应从该台阶移动的方向。当奥尔加移动到下一个台阶时，她离开的台阶上方的指针方向会改变：\"向上\"变为\"向下\"，\"向下\"变为\"向上\"。\n\n奥尔加总是根据她所在台阶上方指针所指的方向移动到下一个台阶。\n\n如果奥尔加移出楼梯，她就会跌落并醒来。移出楼梯指从第 1 级台阶向下移动，或从第 #cf_span[n] 级台阶向上移动。\n\n每一秒，奥尔加根据她开始这一秒时所在台阶上方的指针方向移动一级台阶（向上或向下）。\n\n奥尔加跌落也需要一秒，因此如果她位于第 1 级台阶并向下移动，她将在下一秒醒来。\n\n对于每一级台阶，求出如果奥尔加在梦开始时位于该台阶，她的梦境持续多长时间。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10^6]）——楼梯的台阶数。\n\n第二行包含一个长度为 #cf_span[n] 的字符串 #cf_span[s]，表示楼梯上指针的初始方向。字符串 #cf_span[s] 的第 #cf_span[i] 个字符表示第 #cf_span[i] 级台阶上方指针的方向，要么是 '_U_'（表示指针向上），要么是 '_D_'（表示指针向下）。\n\n指针按从下到上的顺序给出。\n\n请输出 #cf_span[n] 个数字，第 #cf_span[i] 个数字表示如果奥尔加在梦开始时位于第 #cf_span[i] 级台阶，她的梦境持续时间；如果她永远不会移出楼梯，则输出 #cf_span[ - 1]。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10^6]）——楼梯的台阶数。第二行包含一个长度为 #cf_span[n] 的字符串 #cf_span[s]，表示楼梯上指针的初始方向。字符串 #cf_span[s] 的第 #cf_span[i] 个字符表示第 #cf_span[i] 级台阶上方指针的方向，要么是 '_U_'（表示指针向上），要么是 '_D_'（表示指针向下）。指针按从下到上的顺序给出。"},{"iden":"output","content":"请输出 #cf_span[n] 个数字，第 #cf_span[i] 个数字表示如果奥尔加在梦开始时位于第 #cf_span[i] 级台阶，她的梦境持续时间；如果她永远不会移出楼梯，则输出 #cf_span[ - 1]。"},{"iden":"examples","content":"输入3UUD输出5 6 3 输入10UUDUDUUDDU输出5 12 23 34 36 27 18 11 6 1 "}]}

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of steps, with steps indexed from $ 1 $ to $ n $. Let $ s \in \{U, D\}^n $ be the initial direction string, where $ s_i $ is the initial direction at step $ i $. Let $ d_i(t) \in \{U, D\} $ denote the direction at step $ i $ at time $ t $, with $ d_i(0) = s_i $. Let $ p(t) \in \{1, \dots, n\} $ denote Olga’s position at time $ t $, starting at $ p(0) = i $ for the $ i $-th query. **Transition Rule** At each second $ t $: - Olga moves from position $ p(t) $ to $ p(t+1) = p(t) + 1 $ if $ d_{p(t)}(t) = U $, - or to $ p(t+1) = p(t) - 1 $ if $ d_{p(t)}(t) = D $. - After the move, the direction at step $ p(t) $ flips: $ d_{p(t)}(t+1) = \neg d_{p(t)}(t) $. **Termination Condition** Olga wakes up at the smallest $ t > 0 $ such that $ p(t) = 0 $ or $ p(t) = n+1 $. If no such $ t $ exists, the dream duration is $ -1 $. **Objective** For each starting position $ i \in \{1, \dots, n\} $, compute the minimal $ t $ such that $ p(t) \notin \{1, \dots, n\} $, or $ -1 $ if the path is infinite.

Samples

Input #1

3
UUD

Output #1

5 6 3

Input #2

10
UUDUDUUDDU

Output #2

5 12 23 34 36 27 18 11 6 1

API Response (JSON)

{
  "problem": {
    "name": "E. Sleep in Class",
    "description": {
      "content": "The academic year has just begun, but lessons and olympiads have already occupied all the free time. It is not a surprise that today Olga fell asleep on the Literature. She had a dream in which she wa",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF733E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The academic year has just begun, but lessons and olympiads have already occupied all the free time. It is not a surprise that today Olga fell asleep on the Literature. She had a dream in which she wa...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"学年刚刚开始，但课程和竞赛已经占据了所有空闲时间。难怪今天奥尔加在文学课上睡着了。她做了一个梦，梦见自己站在楼梯上。\\n\\n楼梯共有 #cf_span[n] 级台阶。台阶从下到上编号，即最低的台阶编号为 #cf_span[1]，最高的台阶编号为 #cf_span[n]。每个台阶上方有一个指示方向的指针（向上或向下），表示奥尔加应从该台...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of steps, with steps indexed from $ 1 $ to $ n $.  \nLet $ s \\in \\{U, D\\}^n $ be the initial direction string, where $ s_i $ is the initial di...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments