Problem:


Score : 600 points

Problem Statement

Silver Fox is fighting with N monsters.

The monsters are standing in a row, and we can assume them to be standing on a number line. The i-th monster, standing at the coordinate X_i, has the health of H_i.

Silver Fox can use bombs to attack the monsters.
Using a bomb at the coordinate x decreases the healths of all monsters between the coordinates x-D and x+D (inclusive) by A.
There is no way other than bombs to decrease the monster's health.

Silver Fox wins when all the monsters' healths become 0 or below.

Find the minimum number of bombs needed to win.

Constraints

1 \leq N \leq 2 \times 10^5

0 \leq D \leq 10^9

1 \leq A \leq 10^9

0 \leq X_i \leq 10^9

1 \leq H_i \leq 10^9

X_i are distinct.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N D A
X_1 H_1
:
X_N H_N

Output

Print the minimum number of bombs needed to win.

Sample Input 1

3 3 2
1 2
5 4
9 2

Sample Output 1

2

First, let us use a bomb at the coordinate 4 to decrease the first and second monsters' health by 2.

Then, use a bomb at the coordinate 6 to decrease the second and third monsters' health by 2.

Now, all the monsters' healths are 0.
We cannot make all the monsters' health drop to 0 or below with just one bomb.

Sample Input 2

9 4 1
1 5
2 4
3 3
4 2
5 1
6 2
7 3
8 4
9 5

Sample Output 2

5

We should use five bombs at the coordinate 5.

Sample Input 3

3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000

Sample Output 3

3000000000

Watch out for overflow.



Sample input:
3 3 2
1 2
5 4
9 2


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# from numba import njit
i8 = np.int64

# @njit
def solve(X, H, D):
    N = X.shape[0]
    area = 2 * D
    res = 0
    for i in range(N):
        if H[i] > 0:
            res += H[i]
            for j in range(i + 1, N):
                if X[j] - X[i] <= area:
                    H[j] -= H[i]
                else:
                    break
    return res

def main(X, H, D, A):
    arg = np.argsort(X)
    X = X[arg]
    H = H[arg]
    H = (H - 1) // A + 1
    return solve(X, H, D)

if __name__ == '__main__':
    stdin = np.fromstring(open(0).read(), i8, sep=' ')
    N, D, A = stdin[:3]
    XH = stdin[3:].reshape((-1, 2)).T
    X = XH[0]
    H = XH[1]
    ans = main(X, H, D, A)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
from operator import itemgetter
import sys

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, d, a = map(int, read().split())
    xh = [None] * n
    for i in range(n):
        xh[i] = tuple(map(int, read().split()))
    xh.sort(key=itemgetter(0))
    x, h = [0] * n, [0] * n
    for i, (xi, hi) in enumerate(xh):
        x[i] = xi
        h[i] = hi
    r = [0] * n
    for i, xi in enumerate(x):
        r[i] = bisect_right(x, xi + 2 * d) - 1
    cnt = 0
    for i, hi in enumerate(h):
        if hi <= 0:
            continue
        b = (hi + a - 1) // a
        cnt += b
        for j in range(i, r[i] + 1):
            h[j] -= a * b
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
from operator import itemgetter
import sys

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, d, a = map(int, read().split())
    xh = [[int(i) for i in read().split()] for _ in range(n)]
    xh.sort(key=itemgetter(0))
    x, h = [i for i in zip(*xh)]
    h = list(h)
    r = [bisect_right(x, xi + 2 * d) - 1 for xi in x]
    cnt = 0
    for i, hi in enumerate(h):
        if hi <= 0:
            continue
        b = (hi + a - 1) // a
        cnt += b
        for j in range(i, r[i] + 1):
            h[j] -= a * b
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N,D,A=[int(i) for i in input().split()]
XH=[]
for _ in range(N):
    x,h=[int(i) for i in input().split()]
    XH.append([x,h])
XH.sort()

def problemA(H):
    if H%A==0:
        ans=H//A
    else:
        ans=H//A+1
    return ans

ans=0
for i in range(N):
    H=XH[i][1]
    a=problemA(H)
    if H>0:
        ans+=a
        l=0
        while len(XH)>l and XH[i][0]+2*D>=XH[l][0]:
            XH[l][1]-=a*A
            l+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A=[int(i) for i in input().split()]
XH=[]
for _ in range(N):
    x,h=[int(i) for i in input().split()]
    XH.append([x,h])
XH.sort()

def problemA(H):
    if H%A==0:
        ans=H//A
    else:
        ans=H//A+1
    return ans

ans=0
for i in range(N):
    H=XH[i][1]
    a=problemA(H)
    if H>0:
        ans+=a
        l=0
        while XH[i][0]+2*D>=XH[l][0]:
            XH[l][1]-=a*A
            l+=1
            if len(XH)<=l:
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A=[int(i) for i in input().split()]
XH=[]
for _ in range(N):
    x,h=[int(i) for i in input().split()]
    XH.append((x,h))
XH.sort()

def problemA(H):
    if H%A==0:
        ans=H//A
    else:
        ans=H//A+1
    return ans

ans=0
cnt=[0]*N
for i in range(N):
    H=XH[i][1]-cnt[i]*A
    if H>0:
        ans+=problemA(H)
        l=0
        while XH[i][0]+2*D>=XH[l][0]:
            cnt[l]+=problemA(H)
            l+=1
            if len(XH)<=l:
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A = map(int,input().split())
d = {}
E = []
import math
for i in range(N):
    x,h = map(int,input().split())
    n = math.ceil(h/A)
    d[x] = n
    E.append(x)
E.sort()
F = {}
import bisect
for i in range(N):
    x = E[i]
    y = bisect.bisect_right(E,x+2*D)
    F[i] = y
ans = 0
i = 0
while E:
    x = E.pop(0)
    i += 1
    y = F[i-1] - i
    if d[x] <= 0:
        continue
    z = d[x]
    ans += z
    for j in range(y):
        d[E[j]] -= z 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A = map(int,input().split())
d = {}
E = []
import math
for i in range(N):
    x,h = map(int,input().split())
    n = math.ceil(h/A)
    d[x] = n
    E.append(x)
E.sort()
F = {}
import bisect
for i in range(N):
    x = E[i]
    y = bisect.bisect_right(E,x+2*D)
    F[i] = y
ans = 0
for i in range(N):
    x = E[i]
    if d[x] <= 0:
        continue
    y = F[i]
    z = d[x]
    ans += z
    for j in range(i,y):
        d[E[j]] -= z 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# = int(input())
# = map(int, input().split())
# = list(map(int, input().split()))
# = list(input())
# = [tuple(map(int, input().split())) for _ in range(n)]

n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]

xh.sort()

ans = 0
L = 0
H = 0
while L < n:
    while H < n:
        if xh[H][0] > xh[L][0] + d * 2:
            H -= 1
            break
        H += 1
    if H == n:
        H -= 1

    temp = xh[L][1] // a
    if xh[L][1] % a > 0:
        temp += 1
    ans += temp
    temp *= a
    xh[L][1] = 0
    for i in range(L+1, H+1):
        xh[i][1] -= temp

    while xh[L][1] <= 0:
        L += 1
        if L >= n:
            break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
import sys
import numpy as np

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, d, a = map(int, read().split())
    x, h = np.zeros(n, dtype=int), np.zeros(n, dtype=int)
    for i in range(n):
        x[i], h[i] = map(int, read().split())
    idx = np.argsort(x)
    x, h = x[idx], h[idx]
    r = np.zeros(n, dtype=int)
    for i, xi in enumerate(x):
        r[i] = bisect_right(x, xi + 2 * d) - 1
    cnt = 0
    for i, hi in enumerate(h):
        if hi <= 0:
            continue
        b = (hi + a - 1) // a
        cnt += b
        for j in range(i, r[i] + 1):
            h[j] -= a * b
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import sys

# スペース区切りの整数入力
n,d,a = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
e = []
for i in range(n):
    e.append([int(x) for x in input().split()])
e.sort(key=itemgetter(0))

atk_times_sum = 0

atk = []

for i in range(n):
    for j in range(len(atk)-1,-1,-1):
        if e[i][0] <= atk[j][0]:
            e[i][1] -= atk[j][1]
        else:
            break    
    if e[i][1] <= 0:
        continue
    atk_u = e[i][0] + d*2
    if e[i][1] % a == 0:
        atk_times = e[i][1] // a
    else:
        atk_times = e[i][1] // a + 1
    e[i][1] = 0 
    atk_times_sum += atk_times
    atk.append([atk_u,a*atk_times])

print(atk_times_sum)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import sys

# スペース区切りの整数入力
n,d,a = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
e = []
for i in range(n):
    e.append([int(x) for x in input().split()])
e.sort(key=itemgetter(0))

atk_times_sum = 0

for i in range(n):
    if e[i][1] <= 0:
        continue
    #atk_l = e[i][0]
    atk_u = e[i][0] + d*2
    if e[i][1] % a == 0:
        atk_times = e[i][1] // a
    else:
        atk_times = e[i][1] // a + 1
    atk_times_sum += atk_times
    for j in range(i,n):
        #if atk_l <= e[j][0] and e[j][0] <= atk_u:
        if e[j][0] <= atk_u:
            e[j][1] -=  a * atk_times
        else:
            break

print(atk_times_sum)

Submission status: Time Limit Exceeded

Solution code:
import math,bisect
n,d,a = map(int,input().split())
lst1 = [list(map(int,input().split())) for i in range(n)]
lst1.sort()

#解法3 - セグ木
"""
ダメージ量をセグ木の区間で管理する。
なお、72行目までセグ木のコードなのでそれ以降を読めば良い。

この解法では、
自分の座標より右側の巻き込める量を調べる
ではなく、
自分より右側なんてしったこっちゃ無いので自分より左側のダメージが足りてるかどうかを
逐一確認し、足りないなら自分の座標に必要なだけのダメージを記録する
という考え方をする。
故に、変数kは左側であるx - 2*dを参照する。

恐らくlst1を[[1,2]...]ではなく[1000000002,...]という感じで持てば間に合うが、
簡単の為そっちは実装しない。
"""
#####segfunc######
def segfunc(x,y):
    return x+y

def init(init_val): #渡されたリストでsegを初期化
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x): #segの要素kをxに変更(セグ木全体の更新)
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q): #区間[p,q)での、segfuncに準じた値を返す
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
"""
最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
　　和のセグ木 → 0
　　積のセグ木 → 1
　　gcdのセグ木 → 0　(gcdを更新しない値は0)
"""
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num


#process
x = []
for i in lst1:
    x.append(i[0])


ans = 0

for i in range(n):
    k = bisect.bisect_left(x,lst1[i][0]-2*d) #手前側にあるダメージ量を確認

    r = query(k,i) #kからiまでの合計ダメージを取得

    if lst1[i][1] > r:
        need = math.ceil((lst1[i][1]-r)/a)
        ans += need
        update(i,need*a)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,bisect
n,d,a = map(int,input().split())
lst1 = [list(map(int,input().split())) for i in range(n)]
lst1.sort()

#解法3 - セグ木
"""
ダメージ量をセグ木の区間で管理する。
なお、61行目までセグ木のコードなのでそれ以降を読めば良い。

この解法では、
自分の座標より右側の巻き込める量を調べる
ではなく、
自分より右側なんてしったこっちゃ無いので自分より左側のダメージが足りてるかどうかを
逐一確認し、足りないなら自分の座標に必要なだけのダメージを記録する
という考え方をする。
故に、変数kは左側であるx - 2*dを参照する。
"""
#####segfunc######
def segfunc(x,y):
    return x+y

def init(init_val): #渡されたリストでsegを初期化
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x): #segの要素kをxに変更(セグ木全体の更新)
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q): #区間[p,q)での、segfuncに準じた値を返す
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
"""
最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
　　和のセグ木 → 0
　　積のセグ木 → 1
　　gcdのセグ木 → 0　(gcdを更新しない値は0)
"""
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

#process
x = []
for i in lst1:
    x.append(i[0])


ans = 0

for i in range(n):
    k = bisect.bisect_left(x,lst1[i][0]-2*d) #手前側にあるダメージ量を確認

    r = query(k,i) #kからiまでの合計ダメージを取得

    if lst1[i][1] > r:
        need = math.ceil((lst1[i][1]-r)/a)
        ans += need
        update(i,need*a)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import sys

# スペース区切りの整数入力
n,d,a = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
e = []
for i in range(n):
    e.append([int(x) for x in input().split()])
e.sort(key=itemgetter(0))

atk_times_sum = 0

for i in range(n):
    if e[i][1] <= 0:
        continue
    atk_l = e[i][0]
    atk_u = e[i][0] + d*2
    if e[i][1] % a == 0:
        atk_times = e[i][1] // a
    else:
        atk_times = e[i][1] // a + 1
    atk_times_sum += atk_times
    for j in range(i,n):
        if atk_l <= e[j][0] and e[j][0] <= atk_u:
            e[j][1] -=  a * atk_times
        else:
            break

print(atk_times_sum)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import sys

# スペース区切りの整数入力
n,d,a = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
e = []
for i in range(n):
    e.append([int(x) for x in input().split()])
e.sort(key=itemgetter(0))

atk_times_sum = 0

while len(e) > 0:
    atk_l = e[0][0]
    atk_u = e[0][0] + d*2
    if e[0][1] % a == 0:
        atk_times = int(e[0][1] / a)
    else:
        atk_times = int(e[0][1] / a) + 1
    atk_times_sum += atk_times
    for i in range(len(e)-1,-1,-1):
        if atk_l <= e[i][0] and e[i][0] <= atk_u:
            e[i][1] -=  a * atk_times
            if e[i][1] <=  0:
                del(e[i])

print(atk_times_sum)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import sys

# スペース区切りの整数入力
n,d,a = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
e = []
for i in range(n):
    e.append([int(x) for x in input().split()])
e.sort(key=itemgetter(0))

atk_times_sum = 0

while len(e) > 0:
    atk_l = e[0][0]
    atk_u = e[0][0] + d*2
    if e[0][1] % a == 0:
        atk_times = int(e[0][1] / a)
    else:
        atk_times = int(e[0][1] / a) + 1
    atk_times_sum += atk_times
    for i in range(len(e)):
        if atk_l <= e[i][0] and e[i][0] <= atk_u:
            e[i][1] -=  a * atk_times
        else:
            break
    for i in range(len(e)-1,-1,-1):
        if e[i][1] <= 0:
            del(e[i])

print(atk_times_sum)

Submission status: Time Limit Exceeded

Solution code:
N,D,A=[int(i) for i in input().split()]
XH=[]
for _ in range(N):
    x,h=[int(i) for i in input().split()]
    XH.append((x,h))
XH.sort()

def problemA(H):
    if H%A==0:
        ans=H//A
    else:
        ans=H//A+1
    return ans

ans=0
cnt=[0]*N
for i in range(N):
    H=XH[i][1]-cnt[i]*A
    if H>0:
        ans+=problemA(H)
        for j in range(i+1,N):
            if XH[i][0]+2*D>=XH[j][0]:
                cnt[j]+=problemA(H)
            else:
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A=[int(i) for i in input().split()]
XH=[]
for _ in range(N):
    x,h=[int(i) for i in input().split()]
    XH.append([x,h])
XH.sort()

def problemA(H):
    if H%A==0:
        ans=H//A
    else:
        ans=H//A+1
    return ans

ans=0
cnt=[0]*N
for i in range(N):
    H=XH[i][1]
    if H>0:
        a=problemA(H)
        ans+=a
        for j in range(i+1,N):
            if XH[i][0]+2*D>=XH[j][0]:
                XH[j][1]-=a*A
            else:
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A=[int(i) for i in input().split()]
XH=[]
for _ in range(N):
    x,h=[int(i) for i in input().split()]
    XH.append([x,h])
XH.sort()

def problemA(H):
    if H%A==0:
        ans=H//A
    else:
        ans=H//A+1
    return ans

ans=0
cnt=[0]*N
for i in range(N):
    H=XH[i][1]
    if H>0:
        ans+=problemA(H)
        for j in range(i+1,N):
            if XH[i][0]+2*D>=XH[j][0]:
                XH[j][1]-=problemA(H)*A
            else:
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A=[int(i) for i in input().split()]
XH=[]
for _ in range(N):
    x,h=[int(i) for i in input().split()]
    XH.append((x,h))
XH.sort()

def problemA(H):
    if H%A==0:
        ans=H//A
    else:
        ans=H//A+1
    return ans

ans=0
cnt=[0]*N
for i in range(N):
    H=XH[i][1]-cnt[i]*A
    if H>0:
        ans+=problemA(H)
        for j in range(i+1,N):
            if XH[i][0]+2*D>=XH[j][0]:
                cnt[j]+=problemA(H)
            else:
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,d,a=map(int,input().split())
    xh=[list(map(int,input().split())) for _ in range(n)]
    xh.sort()

    b=0
    now=0
    stronger=now

    while True:
        _next=False
        now_h=xh[now][1]
        stronger=now
        included=0

        use_bomb=now_h//a+1
        if now_h%a==0:
            use_bomb-=1
        b+=use_bomb

        for i in range(now+1,n):
            if xh[i][0]>xh[now][0]+2*d:
                break
            else:
                included+=1
                xh[i][1]-=use_bomb*a
                if xh[i][1]>0 and _next is False:
                    stronger=i
                    _next=True

        if stronger==now:
            now+=included+1
        else:
            now=stronger
        if now>=n:
            break
    print(b)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
xh.sort()

b=0
now=0
stronger=now

for _ in range(2*10**5+1):
    _next=False
    now_h=xh[now][1]
    stronger=now
    included=0

    use_bomb=now_h//a+1
    if now_h%a==0:
        use_bomb-=1
    b+=use_bomb

    for i in range(now+1,n):
        if xh[i][0]>xh[now][0]+2*d:
            break
        else:
            included+=1
            xh[i][1]-=use_bomb*a
            if xh[i][1]>0 and _next is False:
                stronger=i
                _next=True

    if stronger==now:
        now+=included+1
    else:
        now=stronger
    if now>=n:
        break
print(b)

Submission status: Time Limit Exceeded

Solution code:
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
xh.sort()

b=0
now=0
stronger=now

while True:
    _next=False
    now_h=xh[now][1]
    stronger=now
    included=0

    use_bomb=now_h//a+1
    if now_h%a==0:
        use_bomb-=1
    b+=use_bomb

    for i in range(now+1,n):
        if xh[i][0]>xh[now][0]+2*d:
            break
        else:
            included+=1
            xh[i][1]-=use_bomb*a
            if xh[i][1]>0 and _next is False:
                stronger=i
                _next=True

    if stronger==now:
        now+=included+1
    else:
        now=stronger
    if now>=n:
        break
print(b)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,D,A=map(int,input().split())
    li=[]
    for i in range(N):
        li.append(tuple(map(int,input().split())))
    li.sort()
    X,H=[0]*N,[0]*N
    for i,t in enumerate(li):
        X[i],H[i]=t
    S=[0]*(N+1)
    x=0
    ans=0
    l=D*2
    while True:
        f=True
        index=bisect_right(X,X[x]+l)
        d=-(-H[x]//A)*A
        ans+=-(-H[x]//A)
        for i in range(x,index):
            if H[i]<=d and f:
                if i==N-1:
                    print(ans)
                    exit()
            else:
                if f:
                    x=i
                H[i]-=d
                f=False
        if f:
            x=index

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
import sys
import numpy as np
input = sys.stdin.readline
N,D,A=map(int, input().split())
mg = [None]*N
X = [None]*N
H = [None]*N
XD = [None]*N
for i in range(N):
  mg[i]=list(map(int, input().split()))
mg.sort(key=lambda x:x[0])
mg = (np.array(mg)).T
X = mg[0]
H = mg[1]
for i in range(N):
  XD[i] = bisect_right(X[i+1:],X[i]+2*D) + (i+1)
XD = np.array(XD)
i = 0
ans = 0
while i<N:
  if H[i]>0:
    k = (H[i]+A-1)//A
    ans +=k
    H[i:XD[i]]=np.maximum(0,H[i:XD[i]]-k*A)
  i+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
import sys
import numpy as np
input = sys.stdin.readline
N,D,A=map(int, input().split())
mg = [None]*N
X = [None]*N
H = [None]*N
XD = [None]*N
for i in range(N):
  mg[i]=list(map(int, input().split()))
mg.sort(key=lambda x:x[0])
mg = (np.array(mg)).T
X = mg[0]
H = mg[1]
for i in range(N):
  XD[i] = bisect_right(X,X[i]+2*D)
XD = np.array(XD)
i = 0
ans = 0
while i<N:
  if H[i]>0:
    k = (H[i]+A-1)//A
    ans +=k
    H[i:XD[i]]=np.maximum(0,H[i:XD[i]]-k*A)
  i+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for i in range(N)]
XH.sort()
X = []
H = []
for x,h in XH:
    h = (h+A-1)//A
    X.append(x)
    H.append(h)
if D == 0:
    print(sum(H))
else:
    area = []
    for i in range(N):
        area.append(bisect.bisect_right(X,X[i]+2*D))
    count = 0
    suma = [0 for i in range(N+1)]
    for i in range(N):
        if suma[i] >= H[i]:
            continue
        rem = H[i] -suma[i]
        count += rem
        suma[i] = H[i]
        for j in range(i+1,area[i]):
            suma[j] += rem
    print(count)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
import sys
import numpy as np
input = sys.stdin.readline
N,D,A=map(int, input().split())
mg = [None]*N
X = [None]*N
H = [None]*N
XD = [None]*N
for i in range(N):
  mg[i]=list(map(int, input().split()))
mg.sort(key=lambda x:x[0])
for i in range(N):
  X[i],H[i]=mg[i]
for i in range(N):
  XD[i] = bisect_right(X,mg[i][0]+2*D)
X = np.array(X)
H = np.array(H)
XD = np.array(XD)
i = 0
ans = 0
while i<N:
  k = (H[i]+A-1)//A
  ans +=k
  H[i:XD[i]]=np.maximum(0,H[i:XD[i]]-k*A)
  i+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A=map(int,input().split())
XH=[]
for _ in range(N):
  x,h=map(int,input().split())
  XH.append([x,h])
XH=sorted(XH, key=lambda x:x[0])
X=[XH[i][0] for i in range(N)]
H=[XH[i][1] for i in range(N)]

import numpy as np
from bisect import bisect_right

H=np.array(H)
ans=0

for i in range(N):
  if H[i]<=0:
    continue
  else:
    xj=2*D+X[i]
    j=bisect_right(X, xj)
    att=[H[i]//A if H[i]%A==0 else H[i]//A+1]
    H[i:j]-=A*att[0]
    ans+=att[0]
#print(H)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A=map(int,input().split())
XH=[]
for _ in range(N):
  x,h=map(int,input().split())
  XH.append([x,h])
XH=sorted(XH, key=lambda x:x[0])
X=[XH[i][0] for i in range(N)]
H=[XH[i][1] for i in range(N)]

import numpy as np
from bisect import bisect_right

H=np.array(H)
ans=0
import math
for i in range(N):
  if np.all(H<=0):
    break
  if H[i]<=0:
    continue
  else:
    xj=2*D+X[i]
    j=bisect_right(X, xj)
    att=math.ceil(H[i]/A)
    H[i:j]-=A*att
    ans+=att
#print(H)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  from heapq import heappush, heappop, heapify
  input = sys.stdin.readline
  
  N,D,A = map(int,input().split())
  hq = []
  for i in range(N):
    x,h = map(int,input().split())
    hq.append((x,0,h))
  heapify(hq)

  ans = 0
  b = 0
  while(len(hq) > 0):
    x,a,h = heappop(hq)
    if a == 0:
      if b < h:
        cnt = ((h-b)+A-1)//A
        ans += cnt
        b += A*cnt
        heappush(hq, (x+2*D,1,A*cnt))
    else:
      b -= h
  
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  from heapq import heappush, heappop
  input = sys.stdin.readline
  
  N,D,A = map(int,input().split())
  hq = []
  for i in range(N):
    x,h = map(int,input().split())
    heappush(hq, (x,0,h))

  ans = 0
  b = 0
  while(len(hq) > 0):
    x,a,h = heappop(hq)
    if a == 0:
      if b < h:
        cnt = ((h-b)+A-1)//A
        ans += cnt
        b += A*cnt
        heappush(hq, (x+2*D,1,A*cnt))
    else:
      b -= h
  
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
def getVal(i):  # get value of node (i,i)
    v = T[(i,i)][0]
    cur = (i,i)
    cur = T[cur][1]
    while cur[0]>=0:
        v += T[cur][0]
        cur = T[cur][1]
    return v
def udT(i,j,x,node):  # add x between [i,j] where current node is given
    l,r = node[0],node[1]
    if i<=l and r<=j:
        T[node][0] += x
    elif i>r or j<l:
        return
    else:
        udT(i,j,x,T[node][2])
        udT(i,j,x,T[node][3])
N,D,A = map(int,input().split())
X = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
n = 0
m = N
while m>0:
    m = m//2
    n += 1
if N==2**(n-1):
    n -= 1
for i in range(N,2**n):  # fill in the remainder of N
    X.append([X[-1][0]+1,0])
# Construction of Tree
Y = [X[i][0] for i in range(N)]  # Tree structure
if N>1:
    T = {(i,i):[X[i][1],(i,i+1) if i%2==0 else (i-1,i),(-1,-1),(-1,-1)] for i in range(2**n)}  # T[node] = [value,parent,left_child,right_child]
else: # N==1
    T = {(i,i):[X[i][1],(-1,-1),(-1,-1),(-1,-1)] for i in range(2**n)}  # T[node] = [value,parent,left_child,right_child]
for h in range(n):
    for i in range(2**h):
        d = 2**(n-h)  # interval length of each node
        if h==0:
            T[(i*d,(i+1)*d-1)] = [0,(-1,-1),(i*d,i*d+d//2-1),((i+1)*d-d//2,(i+1)*d-1)]
        else:
            T[(i*d,(i+1)*d-1)] = [0,(i*d,i*d+2*d-1) if (i*d)%2**(n-h+1)==0 else ((i+1)*d-2*d,(i+1)*d-1),(i*d,i*d+d//2-1),((i+1)*d-d//2,(i+1)*d-1)]
cnt = 0
cur = 0
while cur<N:
    x = Y[cur]
    v = getVal(cur)
    if v%A==0:
        k = v//A
    else:
        k = v//A+1
    ind = bisect_right(Y,x+2*D)
    udT(cur,ind-1,-k*A,(0,2**n-1))
    cnt += k
    flag = 0
    for i in range(cur+1,N):
        if getVal(i)>0:
            cur = i
            flag = 1
            break
    if flag==0:
        cur = N
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n, d, a = map(int, input().split())
lst = []
for i in range(n):
    xi, hi = map(int, input().split())
    if hi % a == 0:
        hi = hi // a
    else:
        hi = hi // a + 1
    lst.append([xi, hi])
lst.sort(key=lambda x: x[0])
x, h = [], []
for i in range(n):
    x.append(lst[i][0])
    h.append(lst[i][1])

x.append(10**11)
h.append(0)

# 攻撃に巻き込めるインデックスを求める
left = 0 # 可能
right = n # 不可能
while left+1 < right:
    mid = (left + right) // 2
    if x[mid] - x[0] <= 2*d:
        left = mid
    else:
        right = mid
makikomi = [left]
right = left
for i in range(1, n):
    while x[right] - x[i] <= 2*d:
        right += 1
    right -= 1
    makikomi.append(right)

cnt = 0
for i in range(n):
    if h[i] > 0:
        cnt += h[i]
        hiku = h[i]
        for j in range(i, makikomi[i]+1):
            h[j] -= hiku

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N,D,A=map(int,input().split())
D*=2 # 爆発の長さ
X=[None]*N
for i in range(N):
  X[i]=list(map(int,input().split()))

X=sorted(X,key=lambda x:x[0])
lastX=X[-1][0] # 最後のモンスターの場所
from collections import defaultdict
damage=defaultdict(int)
ans=0
for i in range(len(X)):
  x=X[i][0]
  h=X[i][1]
  if h>0:
    dele=set()
    for d in damage.items():
      if d[0]<x:
        dele.add(d[0])
      else:
        h-=d[1]
    for p in dele:
      del damage[p]
  if h>0:
    turn=(h+A-1)//A
    damage[x+D]=turn*A
    ans+=turn
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

n,d,a = map(int,input().split())
x = [0]*n
h = [0]*n
for i in range(n):
    x[i] , h[i] = map(int, input().split())
    
itv = [[0 for i in range(2)] for j in range(n)]
for i in range(n):
    itv[i][0] = x[i]
    itv[i][1] = h[i]
itv.sort()
ans = 0
    
for i in range(n):
    atk = 0
    if itv[i][1] > 0:
        atk = math.ceil(itv[i][1]/a)
        itv[i][1] = 0
        for j in range(i+1,n):
            if itv[j][0] <= itv[i][0] + (2*d):
                if itv[j][1] > 0:
                    itv[j][1] -= atk * a
            else:
                break
    ans += atk
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

n,d,a = map(int,input().split())
x = [0]*n
h = [0]*n
for i in range(n):
    x[i] , h[i] = map(int, input().split())
    
itv = [[0 for i in range(2)] for j in range(n)]
for i in range(n):
    itv[i][0] = x[i]
    itv[i][1] = h[i]
itv.sort()
ans = 0
    
for i in range(n):
    atk = 0
    if itv[i][1] > 0:
        atk = math.ceil(itv[i][1]/a)
        itv[i][1] = 0
        for j in range(i+1,n):
            if itv[j][0] <= itv[i][0] + (2*d):
                itv[j][1] -= atk * a
            else:
                break
    ans += atk
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]


class BIT:
    def __init__(self, n):
        # 1-index
        self.n = n
        self.dat = [[0] * self.n for _ in range(2)]
        
    def _add_body(self, p, i, x):
        while i < self.n:
            self.dat[p][i] += x
            i += i & -i

    def add(self, a, b, x):
        # Add x to [a, b)
        self._add_body(0, a, x * -(a - 1))
        self._add_body(1, a, x)
        self._add_body(0, b, x * (b - 1))
        self._add_body(1, b, x * -1)

    def _query_body(self, p, i):
        res = 0
        while i > 0:
            res += self.dat[p][i]
            i -= i & -i
        return res
        
    def query(self, a, b):
        # Return sum of [a, b)
        res = (self._query_body(0, b - 1)
               + self._query_body(1, b - 1) * (b - 1)
               - self._query_body(0, a - 1)
               - self._query_body(1, a - 1) * (a - 1))
        return res

    def __repr__(self):
        return ", ".join([str(self.query(i, i + 1)) for i in range(self.n)])


X, H = zip(*sorted(XH))
bit = BIT(N + 10)

# 初期化
for i, h in enumerate(H):
    bit.add(i + 1, i + 2, h)
    
# 処理
res = 0
for i in range(N):
    cur = bit.query(i + 1, i + 2)
    if cur <= 0:
        continue

    need = -(-cur // A)
    idx = bisect.bisect_right(X, X[i] + 2 * D)
    bit.add(i + 1, idx + 1, -need * A)
    res += need
    
print(res)

Submission status: Time Limit Exceeded

Solution code:
import math
N,D,A=map(int,input().split())
l=[]
for i in range(N):
  k=list(map(int,input().split()))
  l.append(k)
l.sort()
ma=[0]*N
tmp=1
for i in range(N):
  x=l[i][0]
  h=l[i][1]
  tmp=max(tmp,i+1)
  for j in range(tmp,N):
    if abs(l[j][0]-(x+D))>D:
      ma[i]=j
      tmp=j
      break
  else:
    ma[i]=N
    tmp=N
ans=0
for i in range(N):
  h=l[i][1]
  if h<=0:continue
  d=l[i][0]+D
  time=math.ceil(h/A)
  for j in range(i,ma[i]):
    l[j][1]-=time*A
  ans+=time
print(ans)