Controllers
Contest: SWERC 2022-2023 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 1500
Tags: binary search, math

You are at your grandparents' house and you are playing an old video game on a strange console. Your controller has only two buttons and each button has a number written on it.

Initially, your score is $$$0$$$. The game is composed of $$$n$$$ rounds. For each $$$1\le i\le n$$$, the $$$i$$$-th round works as follows.

On the screen, a symbol $$$s_i$$$ appears, which is either $$$\texttt{+}$$$ (plus) or $$$\texttt{-}$$$ (minus). Then you must press one of the two buttons on the controller once. Suppose you press a button with the number $$$x$$$ written on it: your score will increase by $$$x$$$ if the symbol was $$$\texttt{+}$$$ and will decrease by $$$x$$$ if the symbol was $$$\texttt{-}$$$. After you press the button, the round ends.

After you have played all $$$n$$$ rounds, you win if your score is $$$0$$$.

Over the years, your grandparents bought many different controllers, so you have $$$q$$$ of them. The two buttons on the $$$j$$$-th controller have the numbers $$$a_j$$$ and $$$b_j$$$ written on them. For each controller, you must compute whether you can win the game playing with that controller.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — the number of rounds.

The second line contains a string $$$s$$$ of length $$$n$$$ — where $$$s_i$$$ is the symbol that will appear on the screen in the $$$i$$$-th round. It is guaranteed that $$$s$$$ contains only the characters $$$\texttt{+}$$$ and $$$\texttt{-}$$$.

The third line contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of controllers.

The following $$$q$$$ lines contain two integers $$$a_j$$$ and $$$b_j$$$ each ($$$1 \le a_j, b_j \le 10^9$$$) — the numbers on the buttons of controller $$$j$$$.

Output format:
Output $$$q$$$ lines. On line $$$j$$$ print $$$\texttt{YES}$$$ if the game is winnable using controller $$$j$$$, otherwise print $$$\texttt{NO}$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, one possible way to get score $$$0$$$ using the first controller is by pressing the button with numnber $$$1$$$ in rounds $$$1$$$, $$$2$$$, $$$4$$$, $$$5$$$, $$$6$$$ and $$$8$$$, and pressing the button with number $$$2$$$ in rounds $$$3$$$ and $$$7$$$. It is possible to show that there is no way to get a score of $$$0$$$ using the second controller.

Example input:
8
+-+---+-
5
2 1
10 3
7 9
10 10
5 3

Example output:
YES
NO
NO
NO
YES

Example input:
6
+-++--
2
9 7
1 1

Example output:
YES
YES

Editorial:
Denote by $$$p$$$ the number of $$$\texttt{+}$$$ in $$$s$$$ and by $$$m$$$ the number of $$$\texttt{-}$$$ in $$$s$$$ and by $$$tot$$$ the value $$$p-m$$$. We want to figure out whether we can win the game for a single controller with values $$$x$$$ and $$$y$$$ on the two buttons. If we only press the button with value $$$x$$$ written on it, then our sum at the end is $$$(p - m)\cdot x = tot\cdot x$$$. So if $$$tot=0$$$ we can always win the game and from here on we assume that $$$tot \neq 0$$$.
Assume we press the button with value $$$x$$$ $$$k_1$$$ times when the symbol $$$\texttt{+}$$$ comes up and $$$k_2$$$ times when the symbol $$$\texttt{-}$$$ comes up. This means we press the button with value $$$y$$$ $$$p-k_1$$$ times when the symbol $$$\texttt{+}$$$ comes up and $$$m-k_2$$$ times when the symbol $$$\texttt{-}$$$ comes up. Hence our total sum in the end is $$$k_1\cdot x-k_2\cdot x + (p-k_1)y- (m-k_2)y$$$.
We can define $$$k = k_1 - k_2$$$ and rewrite this as $$$k\cdot x + (tot - k)y$$$. Rewriting this even further gives that the sum is 0 if and only if $$$k(y-x)=tot\cdot y$$$. So if $$$x=y$$$ we cannot win the game (recall that we are assuming here that $$$tot \neq 0$$$). If $$$tot\cdot y$$$ is not divisible by $$$(y-x)$$$ we cannot win the game either.
Further, if $$$x\neq y$$$ we win if and only if $$$k = tot \cdot y / (y-x)$$$.
Can we get such value of $$$k$$$? Since $$$0\le k_1 \le p$$$ and $$$0\le k_2 \le m$$$, $$$k=k_1-k_2$$$ can have any integer value in the range $$$[-m,p]$$$. Or in other words, we can win the game if and only if $$$tot\cdot y/(y-x)$$$ is an integer between $$$-m$$$ and $$$p$$$.