Блог пользователя toilanvd_HSGS

Queries with brackets
Автор toilanvd_HSGS, 10 лет назад, По-английски

A have some problems with this, could somebody solve it? Thanks!

Give you a string S with N elements, each element is '(' or ')', and M queries, each query has form (x,y), you have to find maximum length of a correct bracket string in the substring from S[x] to S[y].

A sample test:

Input:

()()(()()(

2

1 7

7 10

Output:

4

2

(Limit: 1 <= N, M <= 200000)

  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

ignore

→ Ответить
»
10 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Deleted because it's the solution to another problem

→ Ответить
»
10 лет назад, # |
← Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

It took me 20 minutes to find a solution and took me 1 hour to write it >.<

This is my solution:

http://paste.ubuntu.com/7971453/

P/S: My algorithm runs in O(1) for each query. My editorial is very complex, but please sympathize me, I did my best. You can believe that it is right. Comment anything if you didn't understand about that.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +13 Проголосовать: не нравится

    This test: ()()()()() and query (1,10) -> the answer is 10, it is in case 1. However according to case 1 we have |()()()()()| = |_()_()_()_()_()_| = |_Tree1_Tree2_Tree3_Tree4_Tree5_|, and with your algorithm, the answer is 2. Still OK, I think processing this problem is not hard, thank you very much ^_^!

    → Ответить