RoAlgo Contest #4 (avansati) | poseidon

This was the problem page during the contest. Access the current page here.
Time limit: 1.5s Memory limit: 64MB Input: Output:

After FlaviuS mysteriously discovered that he is ambidextrous, he defined a boat of size xx as a string of characters that looks like this:

For example, a boat of size 33 looks like this: \\\___/// (_ appears 33 times). FlaviuS also found a string of NN characters, SS, composed only of the characters \, _, and /. He has QQ queries of the form (ll, rr): What is the maximum size of a boat that is a subsequence of the subarray Sl,Sl+1,,SrS_l, S_{l+1}, \dots, S_r?

A subsequence is obtained from another string by deleting some elements while keeping the order of the remaining elements. For example, \_ is a subsequence of the string \/_/, but _\ is not a subsequence of the string \/_/.

Input data

The first line contains two numbers, NN and QQ, representing the length of the string and the number of questions FlaviuS asks. The second line contains the string SS. The next QQ lines contain two numbers each, ll and rr.

Output data

On line ii, 1iQ1 \leq i \leq Q, there will be a single number xx, the maximum size of a boat.

Constraints and clarifications

  • 1N,Q1061 \leq N, Q \leq 10^6
  • 1lrN1 \leq l \leq r \leq N for each query
  • If there is no boat in the chosen subarray for a query, the output will be 00.
# Points Constraints
0 0 Example
1 9 1N,Q2001 \leq N, Q \leq 200
2 22 1N,Q2 0001 \leq N, Q \leq 2 \ 000
3 33 1N,Q100 0001 \leq N, Q \leq 100 \ 000
4 36 No further constraints

Example

stdin

17 6
\_/\/_\___/_/\/_/
1 2
1 3
1 17
3 10
2 16
5 10

stdout

0
1
3
0
2
0

Explanation

For the first query, the subarray is \_, so there is no boat.

For the second query, the subarray is \_/, so there is a boat of size 11.

For the third query, the subarray is the entire string. There is a boat of size 33 formed by the characters at positions 1,4,7,8,9,10,11,13,171, 4, 7, 8, 9, 10, 11, 13, 17. A boat of size 33 looks like this: \\\___///.

Log in or sign up to be able to send submissions!