oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

bracketeditor Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

bracketeditor.html

Problem Statement

You are attempting to develop a text editor for programmers.

Your editor consists of a line of semi-infinite length (there is a first position but no last position) and a cursor which points to the current character. The user can move the cursor one position to the left or right. If it is already in the leftmost position, it will not move.

Initially, the cursor is pointing at the leftmost character and all characters are ' '.

The user can write a lowercase latin letter or a bracket (either '(' or ')') to the current position of the cursor. This overwrites the letter currently there.

Your editor must check whether the line forms a valid text. A text s is considered valid if it satisfies any of these three conditions:

  • it does not contain any brackets;
  • the first character is '(', the last character is ')', and the characters between them form a valid text;
  • it is a concatenation of two valid texts.

Thus, texts such as ((hello)(world)) are valid texts while texts such as okbu(ma)) are not. Take note that a valid text may contain spaces.

There are three commands that the user can give to your program. They are as follows:

  • L - move the cursor one position to the left (if it is in the leftmost position, do not move it)
  • R - move the cursor one position to the right
  • any lowercase latin letter or a bracket - write the character to the current position of the cursor

After each command, your editor must determine two things:

  • is the text in the editor a valid text?
  • if so, what is the number of layers of nested brackets?

For example, the string ((()())()) is valid and has three layers of nested brackets.

Write a program to perform this task!

Input

The first line of input contains a single integer n (1 ≤ n ≤ 1000000), the number of commmands.

The next line of input contains a string of length n, where each character represents a command.

Output

In a single line print n integers, where the i-th integer is:

  • -1 if the current text is not a valid text;
  • the number of layers of nested brackets otherwise.

Subtasks

Subtask 1 (40%): n ≤ 3000

Subtask 2 (60%): No additional constraints.

Sample Input 1

11
(RaRbR)L)L(

Sample Output 1

-1 -1 -1 -1 -1 -1 1 1 -1 -1 2

Sample Input 2

11
(R)R(R)Ra)c

Sample Output 2

-1 -1 1 1 -1 -1 1 1 1 -1 1

Explanation

For Sample Input 1, _ denotes space, bold denotes cursor position.
  1. (__________
  2. (__________
  3. (a_________
  4. (a_________
  5. (ab________
  6. (ab________
  7. (ab)_______
  8. (ab)_______
  9. (a))_______
  10. (a))_______
  11. (())_______

Tags

Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
140171s256MBMinimum
260251s256MBMinimum
3021s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o bracketeditor -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.