Problem:


B : RUPC

問題文

ロシア連邦でプログラミングコンテストが開催される。コンテストには N 個の問題が出題され、M 人の参加者がいる。問題 i には得点 a_i が設定されており、参加者 j の実力は b_j であることがわかっている。問題 i と参加者 j について、 a_i ≤ b_j のときかつそのとき限り、参加者 j は問題 i を必ず解くことができる。 コンテストを通した参加者の得点は、その人が解くことができた問題の得点の総和である。また、参加者 j は、このコンテストでの目標点数 c_j を定めている。

各参加者が、目標点数以上の得点を獲得できるか判定せよ。

入力

入力は以下の形式で与えられる。

N
a_{0} a_{1} a_{2} … a_{N&minus;1}
M
b_{0} b_{1} b_{2} … b_{M&minus;1}
c_{0} c_{1} c_{2} … c_{M&minus;1}

制約

入力はすべて整数である

1 \≤ N \≤ 300\,000

1 \≤ M \≤ 300\,000

0 \≤ a_{i} \≤ 1\,000\,000

0 \≤ b_{i} \≤ 1\,000\,000

0 \≤ c_{i} \≤ &sum;a_k

出力

答えを M 行で出力せよ。 i 行目には、参加者 i&minus;1 が目標点数以上の得点を獲得できるなら Yes、できないなら No と出力せよ。

サンプル

サンプル入力1

6
1 2 1 3 4 5
7
1 3 4 5 3 1 0
2 4 5 3 4 5 3

サンプル出力1

Yes
Yes
Yes
Yes
Yes
No
No

各参加者の得られる得点は以下のようになる。

参加者0 : 1+1=2

参加者1 : 1+2+1+3=7

参加者2 : 1+2+1+3+4=11

参加者3 : 1+2+1+3+4+5=16

参加者4 : 1+2+1+3=7

参加者5 : 1+1=2

参加者6 : 0

サンプル入力2

8
1 1 2 3 3 4 6 100
4
1 3 4 99
1 10 15 120

サンプル出力2

Yes
Yes
No
No



Sample input:
6
1 2 1 3 4 5
7
1 3 4 5 3 1 0
2 4 5 3 4 5 3


Sample output:
Yes
Yes
Yes
Yes
Yes
No
No

Submission status: Wrong Answer

Solution code:
import bisect
N = int(raw_input())
a = sorted(map(int,raw_input().split()))
s = [0]*(N+1)
for i in xrange(N):
    s[i+1] = s[i]+a[i]
s += [10**9]

M = int(raw_input())
b = map(int,raw_input().split())
c = map(int,raw_input().split())

for i in xrange(M):
    p = bisect.bisect(a,b[i])
    print "YES" if s[p] >= c[i] else "NO"

Submission status: Wrong Answer

Solution code:
import bisect
n=int(input())
a=sorted(list(map(int,input().split())))
d=[0]*(n+1)
for i in range(1,n+1):d[i]=d[i-1]+a[i-1]
m=int(input())
b,c=[list(map(int,input().split())) for _ in [0,0]]
for i in range(m):
    p=bisect.bisect_right(d,b[i])
    print(['Yes','No'][d[p]<c[i]])

Submission status: Time Limit Exceeded

Solution code:
_ = int(input())
A = list(map(int, input().split()))
_ = int(input())
B = list(map(int, input().split()))
C = list(map(int, input().split()))

for b, c in zip(B, C):
    total = 0
    for a in A:
        if a <= b:
            total += a

    if c <= total:
        print("Yes")
    else:
        print("No")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# Copyright  : @Huki_Hara
# Created    : 2015-03-14

n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
c = list(map(int, input().split()))
l = []
for i in range(m):
    sum = 0
    for j in range(n):
        if a[j] <= b[i]:
            sum += a[j]

    l.append(sum)

for i in range(m):
    if l[i] >= c[i]:
        print("Yes")
    else:
        print("No")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# Copyright  : @Huki_Hara
# Created    : 2015-03-14

n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
c = list(map(int, input().split()))
l = []
i = 0
while i < m: 
    sum = 0
    j = 0
    while j < n:
        if a[j] <= b[i]:
            sum += a[j]
        j += 1
    i += 1
    l.append(sum)

i = 0
while i < m:
    if l[i] >= c[i]:
        print("Yes")
    else:
        print("No")
    i += 1

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# Copyright  : @Huki_Hara
# Created    : 2015-03-14

n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
c = list(map(int, input().split()))
l = [True] * m
for i in range(m):
    sum = 0
    for j in range(n):
        if a[j] <= b[i]:
            sum += a[j]

    if sum < c[i]:
        l[i] = False

for i in range(m):
    if l[i] :
        print("Yes")
    else:
        print("No")

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
c = map(int, input().split())
l = [True] * m
for i in range(m):
    sum = 0
    for j in range(n):
        if a[j] <= b[i]:
            sum += a[j]

    if sum < c.__next__():
        l[i] = False

for i in range(m):
    if l[i] :
        print("Yes")
    else:
        print("No")

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
c = map(int, input().split())
l = [False] * m

a.sort()
for i in range(m):
    sum = 0
    for j in range(n):
        if a[j] > b[i]:
            break
        sum += a[j]
    if sum >= c.__next__():
        l[i] = True

for i in range(m):
    if l[i]:
        print("Yes")
    else:
        print("No")

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = map(int, input().split())
c = map(int, input().split())
l = []

a.sort()
for i in b:
    sum = 0
    for j in range(n):
        if a[j] > i:
            break
        sum += a[j]
    if sum >= c.__next__():
        l.append(True)
    else:
        l.append(False)

for i in range(m):
    if l[i]:
        print("Yes")
    else:
        print("No")

Submission status: Time Limit Exceeded

Solution code:
input()
a=list(map(int,input().split()))
m=int(input())
b,c=[list(map(int,input().split())) for _ in [0,0]]
[print(['Yes','No'][sum([j for j in a if j<=b[i]])<c[i]])for i in range(m)]

Submission status: Time Limit Exceeded

Solution code:
input()
a=list(map(int,input().split()))
d=[0]*(max(a)+1)
for i in a:d[i]=i*a.count(i)+d[i-1]
m=int(input())
b,c=[list(map(int,input().split())) for _ in [0,0]]
[print(['Yes','No'][d[b[i]]<c[i]])for i in range(m)]

Submission status: Accepted

Solution code:
import bisect
N = int(raw_input())
a = sorted(map(int,raw_input().split()))
s = [0]*(N+1)
for i in xrange(N):
    s[i+1] = s[i]+a[i]
s += [10**9]

M = int(raw_input())
b = map(int,raw_input().split())
c = map(int,raw_input().split())

for i in xrange(M):
    p = bisect.bisect(a,b[i])
    print "Yes" if s[p] >= c[i] else "No"

Submission status: Accepted

Solution code:
import bisect
n=int(input())
a=sorted(list(map(int,input().split())))
d=[0]*(n+1)
for i in range(1,n+1):d[i]=d[i-1]+a[i-1]
m=int(input())
b,c=[list(map(int,input().split())) for _ in [0,0]]
for i in range(m):
    p=bisect.bisect_right(a,b[i])
    print(['Yes','No'][d[p]<c[i]])

Submission status: Accepted

Solution code:
import bisect
n=int(input())
a=sorted(list(map(int,input().split())))
d=[0]*(n+1)
for i in range(1,n+1):d[i]=d[i-1]+a[i-1]
m=int(input())
b,c=[list(map(int,input().split())) for _ in [0,0]]
[print(['Yes','No'][d[bisect.bisect_right(a,b[i])]<c[i]]) for i in range(m)]

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
a.sort()
import bisect
c = list(map(int, input().split()))
d = [0] * (n+1)
for i in range(n):
    d[i+1] = a[i]
for i in range(n):
    d[i+1] += d[i]
for i in range(m):
    n = bisect.bisect_right(a,b[i])
    n = d[n]
    if c[i] <= n:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect_right as br
n = int(input())
alst = sorted(map(int, input().split()))
acc = list(accumulate(alst))
m = int(input())
blst = list(map(int, input().split()))
clst = list(map(int, input().split()))
for b, c in zip(blst, clst):
  index = br(alst, b)
  print(["No", "Yes"][(acc[index - 1] if index > 0 else 0) >= c])