Problem:

D: 矢 / Arrow

問題

rodea 君は 1 次元座標系の中におり、x = 0 の場所に立っている。この位置から、x = N の位置にある的を目がけて、 常に速さ 1 で移動する正の整数の長さの矢を投げる。しかし、rodea 君は非力なため、  区間 0 \leq x \leq N の中に合計 M 個の送風機を置くことにしている。

ここで、矢の先端から根元までの位置に 1 つの送風機も含まれない場合を「損失」と定義する。損失の判定は、矢の先端が x = 1, 2, 3, $\ldots$, N に到達した際に行う（つまり、合計 N 回行う）。

このとき、以下のクエリを Q 回処理せよ。

 「損失」許容可能な回数 l_i が与えられる。すなわち、N 回の判定において、「損失」が合計 l_i 回以下なら矢を的に届けることが可能である。このときの、矢を的に届けるために必要な最短の矢の長さを求める。

入力形式

N M
m_1 m_2 $\ldots$ m_M
Q
l_1 l_2 $\ldots$ l_Q

1 行目に距離 N と送風機の個数 M が空白区切りで与えられる。

2 行目に、M 個の送風機それぞれの位置が与えられる。m_i=j のとき、 i 番目の送風機は x=j-1 と x=j の丁度中間に位置している。

3 行目にクエリの個数 Q が与えられ、4 行目に「損失」許容可能な回数 l_i が Q 個与えられる。

制約

1 \leq N \leq 10^5

1 \leq M \leq N

1 \leq m_1 < m_2 < $\ldots$ < m_M \leq N

1 \leq Q \leq 10^5

0 \leq l_i \leq 10^5 (1 \leq i \leq Q)

出力形式

与えられる Q 個の l_i に対して考えられる最短の矢の長さを、順に改行して出力せよ。

ただし、条件を満たす正の整数の長さの矢が存在しない場合は -1 を出力するものとする。

入力例1

5 1
2
1
3

出力例1

2

矢の先端が x = 1 に到達したとき、先端から根元までに送風機は含まれないので、「損失」回数は 1 になる。

矢の先端が x = 2 に到達したとき、先端から根元までに送風機は含まれるので、「損失」回数は 1 のままである。

矢の先端が x = 3 に到達したとき、先端から根元までに送風機は含まれるので、「損失」回数は 1 のままである。

矢の先端が x = 4 に到達したとき、先端から根元までに送風機は含まれないので、「損失」回数は 2 になる。

矢の先端が x = 5 に到達したとき、先端から根元までに送風機は含まれないので、「損失」回数は 3 になる。

長さ 2 より短い矢を投げる場合、「損失」回数が 3 よりも多くなるため、長さ 2 の矢を投げるときが条件を満たす最短の矢の長さである。

入力例2

11 3
2 5 9
3
1 4 8

出力例2

4
3
1



Sample input:
5 1
2
1
3


Sample output:
2

Submission status: Accepted

Solution code:
import bisect

n,m = map(int,input().split())
pos = list(map(int,input().split()))
q = int(input())
l = list(map(int,input().split()))

pos.append(n+1)
d = [pos[i+1]-pos[i]-1 for i in range(m)]
d.sort()
s = [0]*(m+1)
for i in range(len(d)):
    s[i+1] = s[i]+d[i]

for lim in l:
    ok = n+1
    ng = 0
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        idx = bisect.bisect_left(d,mid)
        cost = (s[-1]-s[idx]) - (m-idx)*(mid-1) + (pos[0]-1)
        if cost <= lim:
            ok = mid
        else:
            ng = mid
    if ok <= n:
        print(ok)
    else:
        print(-1)

Submission status: Accepted

Solution code:
import itertools as ite
import math

INF = 10 ** 18
N, M = map(int, raw_input().split())
m = map(int, raw_input().split()) + [N + 1]
Q = input()
l = map(int, raw_input().split())
cost = [0] * (N + 1)
for i in range(M):
    cost[m[i + 1] - m[i] - 1] += 1
cost[N] += m[0] - 1
grad = 0
for i in range(N)[::-1]:
    grad += cost[i]
    cost[i] = cost[i + 1] + grad
dic = {}
S = 10 ** 5 + 1
for i in range(1, N + 1):
    if S != cost[i]:
        for j in range(cost[i], S):
            dic[j] = i
        S = cost[i]
for num in l:
    if not num in dic:
        print -1
    else:
        print dic[num]

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
"""
n,m = LI()
a = LI()
b = LI()
li = list(set(a)|set(b))
li2 = list(set(a)&set(b))
li.sort()
li2.sort()
print(len(li2),len(li))
for i in li2:
    print(i)
for i in li:
    print(i)
"""

#B
"""
n = I()
p = LI()
ans = [None for i in range(2*n)]
ind = [i for i in range(n)]
for i in range(n):
    ind[p[i]-1] = i
l = 0
print(ind)
for i in range(n):
    while ans[l] != None:l += 1
    ans[l] = "("
    r = n+ind[i]
    while ans[r] != None:r += 1
    ans[r] = ")"
    print(ans)
k = []
q = []
a = 1
print(ans)
for i in range(2*n):
    if ans[i] == "(":
        q.append(a)
        a += 1
    else:
        k.append(q.pop(-1))
if k != p:
    print(":(")
else:
    for i in range(2*n-1):
        print(ans[i],end = "")
    print(ans[-1])
"""

#C
"""
def fact(n):
    i = 2
    a = n
    if n < 4:
        return [1,n],[n]
    li = [1,n]
    while i**2 <= a:
        if n%i == 0:
            li.append(i)
            if i != n//i:
                li.append(n//i)
        i += 1
    li.sort()
    i = 2
    if len(li) == 2:
        return li,[a]
    k = []
    b = a
    while i**2 <= b:
        if a%i == 0:
            k.append(i)
            while a%i == 0:
                a//= i
        i += 1
    if a!=1:
        k.append(a)
    return li,k
n = I()
l,k = fact(n)
if len(l) == 2:
    print(1,1)
else:
    print(len(k),len(l)-1)
"""

#D
n,m = LI()
a = LI()
f = [0 for i in range(n+1)]
for i in range(1,m):
    f[a[i]-a[i-1]-1] += 1
f[n-a[-1]] += 1
s = 0
k = [0 for i in range(n+1)]
for i in range(n)[::-1]:
    s += f[i]
    k[i] += s+k[i+1]
for i in range(n+1):
    k[i] += a[0]-1
q = I()
p = LI()
for i in p:
    l = 0
    r = n
    while r-l>1:
        m = (l+r)//2
        if k[m] > i:
            l = m
        else:
            r = m
    if k[r] > i:
        print(-1)
    else:
        print(r)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
from bisect import bisect_left
def inpl(): return list(map(int, input().split()))

N, M = inpl()
X = inpl()
Q = int(input())
L = inpl()

X += [N+1]
initcost = X[0] - 1
costs = [X[i+1] - X[i] - 1 for i in range(M) if X[i+1] - X[i] > 1]
C = [0]*(N+1)
C[0] = - 10**9

for i in range(1, N+1):
    cost = 0
    costs2 = []
    for c in costs:
        cost += c
        if c > 1:
            costs2.append(c-1)
    C[i] = - (initcost + cost)
    costs = costs2

for l in L:
    if l < - C[-1]:
        print(-1)
    else:
        print(bisect_left(C, -l))