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 bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import Counter
import bisect
from decimal import *
def main():
    N, D, A = MI()
    Enemy = []
    for i in range(N):
        x, h = MI()
        Enemy.append([x, h])
    Enemy.sort(key=lambda list: list[0])
    Enemy_Ran = []
    for ene in Enemy:
        Enemy_Ran.append(ene[0])


    cnt = 0
    for i in range(N):
        if Enemy[i][1] <= 0:
            continue
        else:
            ata = math.ceil(Decimal(Enemy[i][1]) / Decimal(A))
            cnt += ata
            ran = Enemy[i][0] + 2 * D
            ran_i = bisect.bisect_right(Enemy_Ran, ran)
            dam = ata * A
            for j in range(i + 1, ran_i):
                if Enemy[j][1] <= 0:
                    continue
                else:
                    Enemy[j][1] -= dam

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import Counter
import bisect
from decimal import *
def main():
    N, D, A = MI()
    Enemy = []
    for i in range(N):
        x, h = MI()
        Enemy.append([x, h])
    Enemy.sort(key=lambda list: list[0])
    Enemy_Ran = []
    for ene in Enemy:
        Enemy_Ran.append(ene[0])


    cnt = 0
    for i in range(N):
        if Enemy[i][1] <= 0:
            continue
        else:
            ata = math.ceil(Decimal(Enemy[i][1]) / Decimal(A))
            cnt += ata
            ran = Enemy[i][0] + 2 * D
            ran_i = bisect.bisect_right(Enemy_Ran, ran)
            dam = ata * A
            for j in range(i + 1, ran_i):
                Enemy[j][1] -= dam

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect
from functools import reduce
from decimal import *
def main():
    N, D, A = MI()
    Enemy = []
    for i in range(N):
        x, h = MI()
        Enemy.append([x, h])
    Enemy.sort(key=lambda list: list[0])
    cnt = 0
    for i in range(N):
        if Enemy[i][1] <= 0:
            continue
        else:
            ata = math.ceil(Decimal(Enemy[i][1]) / Decimal(A))
            cnt += ata
            ran = Enemy[i][0] + 2 * D
            for j in range(i + 1, N):
                if Enemy[j][0] <= ran:
                    Enemy[j][1] -= ata * A
                else:
                    break
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(self.n+1) # 1-indexed

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

    def add(self, i, x):
        # i: 0-indexed
        i += 1 # to 1-indexed
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    def sum(self, i, j):
        # return sum of [i, j)
        # i, j: 0-indexed
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        # return sum of [0, i)
        # i: 0-indexed
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & (-i)
        return res

class RangeAddBIT:
    def __init__(self, n):
        self.n = n
        self.bit1 = BIT(n)
        self.bit2 = BIT(n)

    def init(self, init_val):
        self.bit2.init(init_val)

    def add(self, l, r, x):
        # add x to [l, r)
        # l, r: 0-indexed
        self.bit1.add(l, x)
        self.bit1.add(r, -x)
        self.bit2.add(l, -x*l)
        self.bit2.add(r, x*r)

    def sum(self, l, r):
        # return sum of [l, r)
        # l, r: 0-indexed
        return self._sum(r) - self._sum(l)

    def _sum(self, i):
        # return sum of [0, i)
        # i: 0-indexed
        return self.bit1._sum(i)*i + self.bit2._sum(i)

import sys
import io, os
#input = sys.stdin.buffer.readline
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

def main():
    n, d, a = map(int, input().split())
    XH = []
    for i in range(n):
        x, h = map(int, input().split())
        XH.append((x-d, h))
    XH.sort()
    X = []
    H = []
    for x, h in XH:
        X.append(x)
        H.append(h)

    bit = RangeAddBIT(n+1)
    bit.init(H)
    import bisect
    ans = 0
    for i in range(n):
        h = bit.sum(i, i+1)
        if h > 0:
            q = (h+a-1)//a
            ans += q
            j = bisect.bisect_right(X, X[i]+2*d)
            bit.add(i, j, -q*a)
    print(ans)

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 i in range(N)]
XH.sort()
from math import ceil
times = ceil(XH[0][1]/A)
ans = times
damege = [times*A]
coor = [XH[0][0]+2*D]
start = 0
end = 1
for i in range(1,N):
    while start < end and coor[start] < XH[i][0]:
        start += 1
    H = XH[i][1] - sum(damege[start:end])
    if H > 0:
        times = ceil(H/A)
        ans += times
        damege.append(times*A)
        coor.append(XH[i][0]+2*D)
        end += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
[N, D, A] = [int(i) for i in input().split()]
X = [-1, 10**9+1]
H = []
P = []

for k in range(N):
    [x, h] = [int(i) for i in input().split()]
    for j in range(k+1):
        if X[j] < x < X[j+1]:
            X.insert(j+1, x)
            H.insert(j, h)
            if int(h/A) != h/A:
                t = 1
            else:
                t = 0
            p = int(h/A) + t
            P.insert(j, p)
X.pop(0)
X.pop(-1)


ans = 0
for i in range(N):
    p = P[i]
    if p >= 1:
        ans += p
        for j in range(i, N):
            if X[j] - X[i] <= 2*D:
                q = P[j] - p
                P[j] = q

print(ans)

Submission status: Time Limit Exceeded

Solution code:
(N,D,A) = map(int,input().split())
l = []
for i in range(N):
    l.append([int(x) for x in input().split()])
    l.sort()
k = [0 for i in range(N)]
for i in range(N):
    k[i] = -((-l[i][1])//A)

m = [0] * N
ub = 0
cnt = 1
for i in range(N):
    if ub < N-1:
        while l[ub + 1][0]-l[i][0] <= 2*D:
            cnt += 1
            ub += 1
            if ub == N - 1:
                break
        m[i] = cnt
    else:
        m[i] = cnt
    cnt -= 1

ans = 0
al = 0
s = [0 for i in range(N)]
j = 0
for i in range(N):
    s[i] = max(k[i]-al,0)
    ans += s[i]
    al += s[i]
    if i < N-1:
        while j+m[j]-1 < i+1:
            al -= s[j]
            if j < N-1:
                j += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#TLEしてしまう…
(N,D,A) = map(int,input().split())
l = []
for i in range(N):
    l.append([int(x) for x in input().split()])
    l.sort()
k = [0 for i in range(N)]
for i in range(N):
    k[i] = -((-l[i][1])//A)

m = [0] * N
ub = 0
cnt = 1
for i in range(N):
    if ub < N-1:
        while l[ub + 1][0]-l[i][0] <= 2*D:
            cnt += 1
            ub += 1
            if ub == N - 1:
                break
        m[i] = cnt
    else:
        cnt -= 1
        m[i] = cnt
    cnt -= 1

ans = 0
for i in range(N):
    if  k[i] != 0:
        for p in range(1,m[i]):
            if k[i+p] >= k[i]:
                k[i+p] -= k[i]
            else:
                k[i+p] = 0
        ans += k[i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#TLEしてしまう…
(N,D,A) = map(int,input().split())
l = []
for i in range(N):
    l.append([int(x) for x in input().split()])
    l.sort()
k = [0 for i in range(N)]
for i in range(N):
    k[i] = -((-l[i][1])//A)

m = []
for i in range(N):
    cnt = 0
    j = i
    while l[j][0]-l[i][0] <= 2*D:
        cnt += 1
        j += 1
        if j >= N:
            break
    m.append(cnt)

ans = 0
for i in range(N):
    if  k[i] != 0:
        for p in range(1,m[i]):
            if k[i+p] >= k[i]:
                k[i+p] -= k[i]
            else:
                k[i+p] = 0
        ans += k[i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
(N,D,A) = map(int,input().split())
l = []
for i in range(N):
    l.append([int(x) for x in input().split()])
    l.sort()
for i in range(N):
    l[i][1] = -((-l[i][1])//A)

m = []
for i in range(N):
    cnt = 0
    j = i
    while l[j][0]-l[i][0] <= 2*D:
        cnt += 1
        j += 1
        if j >= N:
            break
    m.append(cnt)

ans = 0
for i in range(N):
    if  l[i][1] != 0:
        for p in range(1,m[i]):
            if l[i+p][1] >= l[i][1]:
                l[i+p][1] -= l[i][1]
            else:
                l[i+p][1] = 0
    ans += l[i][1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, math


def solve_greedy(N, D, A, XH):
    ret = 0
    for i, (x, h) in enumerate(XH):
        if h <= 0:
            continue
        tmp = math.ceil(h / A)
        ret += tmp
        for j in range(i + 1, N):
            if XH[j][0] > x + 2 * D:
                break
            XH[j][1] -= A * tmp
    return ret


input = sys.stdin.readline
N, D, A = map(int, input().split())
XH = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
ans = solve_greedy(N, D, A, XH)
print(ans)

Submission status: Time Limit Exceeded

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

from bisect import bisect_left, bisect_right
import numpy as np

n, d, a = map(int, input().split())
xh=[list(map(int, input().split())) for _ in range(n)]
xh.sort()
xh = np.array(xh)
xh = xh.T
x = xh[0][:]
h = xh[1][:]
l = 0
ret = 0
while l < n:
    xl = x[l]
    hl = h[l]
    l += 1
    if hl <= 0:
        continue
    r = bisect_right(x, xl+2*d)
    k = (hl+(a-1))//a
    ret += k
    h[l:r] -= k * a
print(ret)

Submission status: Time Limit Exceeded

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

from bisect import bisect_left, bisect_right
import numpy as np

n, d, a = map(int, input().split())
xh=[list(map(int, input().split())) for _ in range(n)]
xh.sort()
xh = [list(x) for x in zip(*xh)]
l = 0
ret = 0
while l < n:
    xl = xh[0][l]
    hl = xh[1][l]
    l += 1
    if hl <= 0:
        continue
    r = bisect_right(xh[0], xl+2*d)
    k = (hl+(a-1))//a
    ret += k
    for i in range(l, r):
        xh[1][i] -= k * a
print(ret)

Submission status: Time Limit Exceeded

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

from bisect import bisect_left, bisect_right

n, d, a = map(int, input().split())
x = []
xh =dict()
for _ in range(n):
    xi, hi = map(int, input().split())
    x.append(xi)
    xh[xi] = hi
x.sort()

l = 0
ret = 0
while l < n:
    xl = x[l]
    hl = xh[xl]
    l += 1
    if hl <= 0:
        continue
    r = bisect_right(x, xl+2*d)
    k = (hl+(a-1))//a
    ret += k
    for i in range(l, r):
        xh[x[i]] -= k * a
print(ret)

Submission status: Time Limit Exceeded

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

from bisect import bisect_left, bisect_right

n, d, a = map(int, input().split())
x = []
xh =dict()
for _ in range(n):
    xi, hi = map(int, input().split())
    x.append(xi)
    xh[xi] = hi
x.sort()

l = 0
ret = 0
while l < n:
    xl = x[l]
    hl = xh[xl]
    l += 1
    if hl <= 0:
        continue
    r = bisect_right(x, xl+2*d)
    k = (hl+(a-1))//a
    ret += k
    for i in range(l, r):
        xh[x[i]] -= k * a
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
monster = {}
x = []
for i in range(n):
    xx, hh = MAP()
    monster[xx] = hh
    x.append(xx)
x.sort()
cnt = 0
for i in range(n):
    cx, ch = x[i], monster[x[i]]
    if ch <= 0:
        continue
    cn = (ch + a - 1) // a
    cnt += cn
    tmp = []
    j = i + 1
    while j < n:
        nx = x[j]
        if nx <= cx + 2*d:
            monster[nx] -= cn * a
            j += 1
        else:
            break
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
monster = {}
x = []
for i in range(n):
    xx, hh = MAP()
    monster[xx] = hh
    x.append(xx)
x.sort()
cnt = 0
for i in range(n):
    cx, ch = x[i], monster[x[i]]
    if ch <= 0:
        continue
    cn = (ch + a - 1) // a
    cnt += cn
    tmp = []
    j = i + 1
    while j < n:
        nx = x[j]
        if nx <= cx + 2*d:
            if monster[nx] > 0:
                monster[nx] -= cn * a
            j += 1
        else:
            break
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
monster = {}
x = []
for i in range(n):
    xx, hh = MAP()
    monster[xx] = hh
    x.append(xx)
x.sort()
cnt = 0
for i in range(n):
    cx, ch = x[i], monster[x[i]]
    if ch <= 0:
        continue
    cn = (ch + a - 1) // a
    cnt += cn
    tmp = []
    j = i + 1
    while j < n:
        nx = x[j]
        if nx <= cx + 2*d:
            monster[nx] -= cn * a
            j += 1
        else:
            break
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
xh = [LIST() for i in range(n)]

xh = sorted(xh, key=lambda x:(x[0]))
cnt = 0
for i in range(n):
    cx, ch = xh[i][0], xh[i][1]
    if ch <= 0:
        continue
    cn = (ch + a - 1) // a
    cnt += cn
    tmp = []
    j = i + 1
    while xh and j < len(xh):
        nx = xh[j][0]
        if nx <= cx + 2*d:
            xh[j][1] -= cn * a
            j += 1
        else:
            break
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
xh = [LIST() for i in range(n)]

xh = sorted(xh, key=lambda x:(x[0], x[1]))
cnt = 0
for i in range(n):
    cx, ch = xh[i][0], xh[i][1]
    if ch <= 0:
        continue
    cn = (ch + a - 1) // a
    cnt += cn
    tmp = []
    j = i + 1
    while xh and j < len(xh):
        nx = xh[j][0]
        if nx <= cx + 2*d:
            xh[j][1] -= cn * a
            j += 1
        else:
            break
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
xh = [LIST() for i in range(n)]

xh = sorted(xh, key=lambda x:(x[0], x[1]))
xh = deque(xh)
cnt = 0
while xh:
    c = xh.popleft()
    cx, ch = c[0], c[1]
    if ch <= 0:
        continue
    cn = (ch + a - 1) // a
    cnt += cn
    tmp = []
    i = 0
    while xh and i < len(xh):
        nx = xh[i][0]
        if nx <= cx + 2*d:
            xh[i][1] -= cn * a
            i += 1
        else:
            break
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
xh = [LIST() for i in range(n)]

heapq.heapify(xh)
cnt = 0
while xh:
    c = heapq.heappop(xh)
    cx, ch = c[0], c[1]
    cn = (ch + a - 1) // a
    cnt += cn
    tmp = []
    while xh:
        ne = heapq.heappop(xh)
        nx, nh = ne[0], ne[1]
        if nx <= cx + 2*d:
            nh -= cn * a
            if nh > 0:
                tmp.append([nx, nh])
        else:
            tmp.append([nx, nh])
            break
    for i in range(len(tmp)):
        heapq.heappush(xh, tmp[i])
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n,d,a=map(int,input().split())
num=[]
for i in range(n):
    num.append(list(map(int,input().split())))
num.sort(key=lambda x: x[0])
for i in range(n):
    num[i][1]=-(num[i][1]//-a)
cnt=0
cnt2=0
num2=num[0][0]+(d*2)
ans=0
for i in range(n):
    yn=0
    for j in range(cnt,n):
        if num2<num[j][0]:
            cnt2=j-1
            yn=1
            break
    if yn==0:
        cnt2=n-1
    else:
        yn=0
    num3=num[cnt][1]
    ans+=num3
    for j in range(cnt,cnt2+1):
        num[j][1]-=num3
        if num[j][1]>0 and yn==0:
            cnt=j
            yn=1
    if yn==0:
        if cnt2+1!=n:
            cnt=cnt2+1
        else:
            break
    num2=num[cnt][0]+(d*2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,d,a=map(int,input().split())
num=[]
for i in range(n):
    num.append(list(map(int,input().split())))
num.sort(key=lambda x: x[0])
cnt=0
cnt2=0
num2=num[0][0]+(d*2)
ans=0
for i in range(n):
    yn=0
    for j in range(cnt,n):
        if num2<num[j][0]:
            cnt2=j-1
            yn=1
            break
    if yn==0:
        cnt2=n-1
    else:
        yn=0
    num3=-(num[cnt][1]//-a)
    ans+=num3
    num4=a*num3
    for j in range(cnt,cnt2+1):
        num[j][1]-=num4
    for j in range(cnt,min(n,cnt2+2)):
        if num[j][1]>0:
            yn=1
            cnt=j
            break
    if yn==0:
        break
    num2=num[cnt][0]+(d*2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,d,a=map(int,input().split())
num=[]
for i in range(n):
    num.append(list(map(int,input().split())))
num.sort(key=lambda x: x[0])
cnt=0
cnt2=0
num2=num[0][0]+d
ans=0
for i in range(n):
    yn=0
    for j in range(cnt,n):
        if num2+d<num[j][0]:
            cnt2=j-1
            yn=1
            break
    if yn==0:
        cnt2=n-1
    else:
        yn=0
    num3=-(num[cnt][1]//-a)
    ans+=num3
    num4=a*num3
    for j in range(cnt,cnt2+1):
        num[j][1]-=num4
    for j in range(cnt,min(n,cnt2+2)):
        if num[j][1]>0:
            yn=1
            cnt=j
            break
    if yn==0 and num[-1][1]>0:
        yn=1
        cnt=n-1
    if yn==0:
        break
    num2=num[cnt][0]+d
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,d,a=map(int,input().split())
num=[]
for i in range(n):
    num.append(list(map(int,input().split())))
num.sort(key=lambda x: x[0])
cnt=0
cnt2=0
num2=num[0][0]+d
ans=0
for i in range(n):
    yn=0
    for j in range(cnt,n):
        if num2+d<num[j][0]:
            cnt2=j-1
            yn=1
            break
    if yn==0:
        cnt2=n-1
    else:
        yn=0
    num3=-(num[cnt][1]//-a)
    ans+=num3
    for j in range(cnt,cnt2+1):
        num[j][1]-=a*num3
    for j in range(cnt,n):
        if num[j][1]>0:
            yn=1
            cnt=j
            break
    if yn==0 and num[-1][1]>0:
        yn=1
        cnt=n-1
    if yn==0:
        break
    num2=num[cnt][0]+d
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, D, A = MAP()
XH = [LIST() for _ in range(N)]

XH.sort(key = lambda x: x[0])

X, H = zip(*XH)

right = [0]*N
for i, x in enumerate(X):
	right[i] = bisect(X, x+2*D)

damage = [0]*(N+1)
ans = 0

for i in range(N):
	for i, (X, H) in enumerate(XH):
		if i != 0:
			damage[i] += damage[i-1]
		H -= damage[i]
		if 0 < H:
			n = -(-H//A)
			ans += n
			d = A*n
			damage[i] += d
			damage[right[i]] -= d
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def waru(a,b):
  if a%b==0:
    return a
  else:
    return ((a//b)+1)*b
strong=list()
place=list()
N,D,A=map(int,input().split())
for i in range(N):
  x,h=map(int,input().split())
  place.append(x)
  strong.append(h)
c = zip(place, strong)
c=sorted(c)
place, strong= zip(*c)
s=0
while True:
  c=[(x,y-waru(strong[0],A)) if x<=place[0]+2*D else (x,y) for (x,y) in c]
  c=[(x,y) for (x,y) in c if y>0]
  s+=waru(strong[0],A)//A
  if len(c)==0:
    break
  place, strong= zip(*c)
print(s)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, D, A = map(int, input().split())
monster = []
for k in range(N):
  monster.append(list(map(int, input().split())))
monster.sort(key = lambda x: x[0])
for k in range(N):
  monster[k][1] = int((monster[k][1]-0.1)//A + 1)
ans = 0
monster = deque(monster)
final = monster[-1][0]
ruiseki = 0
minuslist = deque()

while len(monster) > 0:
  while len(minuslist) > 0:
    if monster[0][0] >= minuslist[0][0]:
      ruiseki -= minuslist.popleft()[1]
    else:
      break
  if ruiseki < monster[0][1]:
    ans += monster[0][1] - ruiseki
    if monster[0][0] + 2*D +1 <= final:
      minuslist.append([monster[0][0]+2*D+1, monster[0][1] - ruiseki])
    ruiseki = monster.popleft()[1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, D, A = map(int, input().split())
monster = []
for k in range(N):
  monster.append(list(map(int, input().split())))
monster.sort(key = lambda x: x[0])
ans = 0
k = 0
while k < len(monster):
  if monster[k][1] > 0:
    nowx = monster[k][0]
    damage = ((monster[k][1]-0.1)//A)*A + A
    ans += int((monster[k][1]-0.1)//A + 1)
    j = 0 + k
    nextk = N
    while(j +1 < len(monster)):
      j += 1
      if monster[j][0] <= nowx + 2*D:
        monster[j][1] -= damage
        if monster[j][1] > 0:
          nextk = min(j, nextk)
          continue
      else:
        nextk = min(nextk, j)
        break
    k = nextk

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, D, A = map(int, input().split())
monster = []
for k in range(N):
  monster.append(list(map(int, input().split())))
monster.sort(key = lambda x: x[0])
monster = deque(monster)
ans = 0
while len(monster) > 0:
  if monster[0][1] > 0:
    nowx = monster[0][0]
    damage = ((monster[0][1]-0.1)//A)*A + A
    ans += int((monster[0][1]-0.1)//A + 1)
    j = 0
    while(j<len(monster)):
      if monster[j][0] <= nowx + 2*D:
        monster[j][1] -= damage
        if monster[j][1] > 0:
          j += 1
        else:
          monster.remove(monster[j])
        continue
      else:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, D, A = map(int, input().split())
monster = []
for k in range(N):
  monster.append(list(map(int, input().split())))
monster.sort(key = lambda x: x[0])
ans = 0
while len(monster) > 0:
  if monster[0][1] > 0:
    nowx = monster[0][0]
    damage = ((monster[0][1]-0.1)//A)*A + A
    ans += int((monster[0][1]-0.1)//A + 1)
    j = 0
    while(j<len(monster)):
      if monster[j][0] <= nowx + 2*D:
        monster[j][1] -= damage
        if monster[j][1] > 0:
          j += 1
        else:
          del monster[j]
        continue
      else:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, D, A = map(int, input().split())
monster = []
for k in range(N):
  monster.append(list(map(int, input().split())))
monster.sort(key = lambda x: x[0])
ans = 0
for k in range(N):
  if monster[k][1] > 0:
    nowx = monster[k][0]
    damage = ((monster[k][1]-0.1)//A)*A + A
    ans += int((monster[k][1]-0.1)//A + 1)
    for j in range(k, N):
      if monster[j][0] <= nowx + 2*D:
        monster[j][1] -= damage
        continue
      else:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,d,a=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
arr.sort()
hp=[arr[i][1] for i in range(n)]
loc=[arr[i][0] for i in range(n)]
ans=0
for i in range(n):
  if hp[i]>0:
    tmp=(hp[i]-1)//a+1
    ans+=tmp
    tmp*=a
    for j in range(i,bisect.bisect_right(loc,loc[i]+2*d)):
      hp[j]-=tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,d,a=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
arr.sort()
hp=[arr[i][1] for i in range(n)]
loc=[arr[i][0] for i in range(n)]
ans=0
for i in range(n):
  if hp[i]>0:
    tmp=(hp[i]-1)//a+1
    ans+=tmp
    for j in range(i,bisect.bisect_right(loc,loc[i]+2*d)):
      hp[j]-=tmp*a
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,d,a=map(int,input().split())
arr=[]
for _ in range(n):
  arr.append(list(map(int,input().split())))
arr.sort()
hp=[arr[i][1] for i in range(n)]
loc=[arr[i][0] for i in range(n)]
ans=0
for i in range(n):
  if hp[i]>0:
    tmp=(hp[i]-1)//a+1
    ans+=tmp
    for j in range(i,bisect.bisect_right(loc,loc[i]+2*d)):
      hp[j]-=tmp*a
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,d,a=map(int,input().split())
arr=[]
ans,i=0,0
for _ in range(n):
  arr.append(list(map(int,input().split())))
arr.sort()
hp=[arr[i][1] for i in range(n)]
arr=[arr[i][0] for i in range(n)]
for i in range(n):
  if hp[i]>0:
    tmp=(hp[i]-1)//a+1
    ans+=tmp
    for j in range(i,bisect.bisect_right(arr,arr[i]+2*d)):
      hp[j]-=tmp*a
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,d,a=map(int,input().split())
arr=[]
ans,i=0,0
for _ in range(n):
  arr.append(list(map(int,input().split())))
arr.sort()
hp=[arr[i][1] for i in range(n)]
arr=[arr[i][0] for i in range(n)]
while True:
  if hp[i]>0:
    tmp=(hp[i]-1)//a+1
    tmp_i=i
    ans+=tmp
    for j in range(i,bisect.bisect_right(arr,arr[i]+2*d)):
      hp[j]-=tmp*a
  if i<n-1:
    i+=1
  if max(hp)<=0:
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, D, A = map(int, input().split())
    XH = [None] * N

    for i in range(N):
        XH[i] = tuple(map(int, input().split()))

    XH.sort()
    
    # 何回爆弾を当てれば倒せるか
    nums = [(XH[i][1]+A-1)//A  for i in range(N)]
    
    ans = 0
    for i in range(N):
        if nums[i] == 0:
            continue
        ans += nums[i]
        for j in range(i+1,N):
            if XH[j][0] - XH[i][0] <= 2*D:
                nums[j] = max(0,nums[j]-nums[i])
            else:
                break
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
xh = [LIST() for i in range(n)]
xh = sorted(xh, key=lambda x:(x[0]))
if d == 0:
    di = 0
else:
    di = 1 + 2*d
cnt = 0
while xh:
    c = xh.pop(0)
    cx, ch = c[0], c[1]
    if ch <= 0:
        continue
    if ch % a == 0:
        cn = ch // a
    else:
        cn = 1 + ch // a
    cnt += copy.deepcopy(cn)
    for nx in range(cx+1, cx+di+1):
        for i in range(len(xh)):
            if xh[i][0] == nx:
                xh[i][1] -= a * cn
print(cnt)