1776L.md (2539B)
1 Source: https://codeforces.com/problemset/problem/1776/L 2 3 L. Controllers 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 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. 24 25 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. 26 27 After you have played all $n$ rounds, you win if your score is $0$. 28 29 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. 30 31 Input 32 33 The first line contains a single integer $n$ ($1 \le n \le 2\cdot 10^5$) — the number of rounds. 34 35 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{-}$. 36 37 The third line contains an integer $q$ ($1 \le q \le 10^5$) — the number of controllers. 38 39 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$. 40 41 Output 42 43 Output $q$ lines. On line $j$ print $\texttt{YES}$ if the game is winnable using controller $j$, otherwise print $\texttt{NO}$. 44 45 Examples 46 47 Input 48 49 ``` 50 8 51 +-+---+- 52 5 53 2 1 54 10 3 55 7 9 56 10 10 57 5 3 58 ``` 59 60 Output 61 62 ``` 63 YES 64 NO 65 NO 66 NO 67 YES 68 ``` 69 70 Input 71 72 ``` 73 6 74 +-++-- 75 2 76 9 7 77 1 1 78 ``` 79 80 Output 81 82 ``` 83 YES 84 YES 85 ``` 86 87 Input 88 89 ``` 90 20 91 +-----+--+--------+- 92 2 93 1000000000 99999997 94 250000000 1000000000 95 ``` 96 97 Output 98 99 ``` 100 NO 101 YES 102 ``` 103 104 Note 105 106 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.