/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 333 点
問題文
高橋君はお花見の幹事を務めることになりました。会場近くの商店街には N 軒のお店が 1 番から N 番まで一列に並んでおり、各お店ではそれぞれ 1 種類の商品を販売しています。 i 番目のお店の商品の価格は A_i 円です。
高橋君は Q 回の買い出しを行います。 j 回目の買い出しでは、 L_j 番目から R_j 番目までの連続するお店すべてで商品を 1 つずつ購入する予定です。このとき、 j 回目の買い出しでの合計金額は A_{L_j} + A_{L_j+1} + \cdots + A_{R_j} 円です。
お花見の予算には上限 T 円が設けられています。 1 回の買い出しでの合計金額が T 円を超える（すなわち T 円より真に大きい）場合、追加の承認手続きが必要になります。合計金額が T 円以下の場合は、予算内に収まっているものとして追加の承認手続きは不要です。
各回の買い出しについて、購入する商品の合計金額が予算上限 T 円を超えるかどうかを判定してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq T \leq 10^{14}
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
- 入力はすべて整数である。
入力
N Q T A_1 A_2 \ldots A_N L_1 R_1 L_2 R_2 \vdots L_Q R_Q
- 1 行目には、お店の軒数を表す整数 N 、買い出しの回数を表す整数 Q 、予算上限を表す整数 T が、スペース区切りで与えられる。
- 2 行目には、各お店の商品の価格を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
- 続く Q 行にわたって、各買い出しの情報が与えられる。
- 2 + j 行目 (1 \leq j \leq Q) には、 j 回目の買い出しで訪れるお店の区間の左端 L_j と右端 R_j が、スペース区切りで与えられる。
出力
Q 行出力してください。 j 行目には、 j 回目の買い出しにおける合計金額 A_{L_j} + A_{L_j+1} + \cdots + A_{R_j} が T より大きい場合は Yes を、 T 以下である場合は No を出力してください。
入力例 1
5 3 600 100 200 300 400 500 1 3 2 4 5 5
出力例 1
No Yes No
入力例 2
8 5 1000 150 300 250 100 500 350 200 450 1 4 3 7 1 8 6 8 4 5
出力例 2
No Yes Yes No No
入力例 3
10 6 3000000000 1000000000 999999999 999999998 500000000 1 2 999999997 800000000 700000000 300000000 1 3 1 4 5 6 7 10 1 10 4 8
出力例 3
No Yes No No Yes No
Score : 333 pts
Problem Statement
Takahashi has been appointed as the organizer of a hanami (cherry blossom viewing) party. Near the venue, there is a shopping street with N shops lined up in a row, numbered from 1 to N. Each shop sells one type of product. The price of the product at the i-th shop is A_i yen.
Takahashi will make Q shopping trips. On the j-th shopping trip, he plans to purchase one item from each of the consecutive shops from shop L_j to shop R_j. The total cost of the j-th shopping trip is A_{L_j} + A_{L_j+1} + \cdots + A_{R_j} yen.
The hanami has a budget limit of T yen. If the total cost of a single shopping trip exceeds T yen (i.e., is strictly greater than T yen), an additional approval procedure is required. If the total cost is T yen or less, it is considered within budget and no additional approval procedure is needed.
For each shopping trip, determine whether the total cost of the purchased items exceeds the budget limit of T yen.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq T \leq 10^{14}
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
- All input values are integers.
Input
N Q T A_1 A_2 \ldots A_N L_1 R_1 L_2 R_2 \vdots L_Q R_Q
- The first line contains three space-separated integers: N representing the number of shops, Q representing the number of shopping trips, and T representing the budget limit.
- The second line contains space-separated integers A_1, A_2, \ldots, A_N, representing the price of the product at each shop.
- The following Q lines contain information about each shopping trip.
- The (2 + j)-th line (1 \leq j \leq Q) contains the left endpoint L_j and right endpoint R_j of the range of shops visited on the j-th shopping trip, separated by a space.
Output
Print Q lines. On the j-th line, print Yes if the total cost A_{L_j} + A_{L_j+1} + \cdots + A_{R_j} of the j-th shopping trip is greater than T, and No if it is T or less.
Sample Input 1
5 3 600 100 200 300 400 500 1 3 2 4 5 5
Sample Output 1
No Yes No
Sample Input 2
8 5 1000 150 300 250 100 500 350 200 450 1 4 3 7 1 8 6 8 4 5
Sample Output 2
No Yes Yes No No
Sample Input 3
10 6 3000000000 1000000000 999999999 999999998 500000000 1 2 999999997 800000000 700000000 300000000 1 3 1 4 5 6 7 10 1 10 4 8
Sample Output 3
No Yes No No Yes No