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 sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
N,D,A = map(int,readline().split())
m = map(int,read().split())
XH = np.array(list(zip(m,m)), np.int64)
sortlist = np.argsort(XH[:,0])
XH = XH[sortlist]

ans = 0
while True:
	place = np.where(XH[:,1] > 0)
	if len(place[0]) == 0:
		break
	ind_cp = place[0][0]
	cp = XH[ind_cp,0]
	R = cp + (2*D)
	ind = np.searchsorted(XH[:,0],R, side='right')
	attack = -(-XH[ind_cp,1]//A)
	ans += attack
	XH[ind_cp:ind,1] -= attack*A

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
input = sys.stdin.readline
N, D, A = map(int,input().split())
XH = [list(map(int,input().split())) for i in range(N)]
XH.sort()
ans = 0
for i in range(N):
    if XH[i][1] > 0:
        p = XH[i][0]
        t = A*math.ceil(XH[i][1] / A)
        ans += math.ceil(XH[i][1] / A)
        for l in range(i, N):
            if XH[l][0] <= p + 2 * D:
                XH[l][1] -= t
            else:
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, D,A = map(int, input().split())
R = [ list(map(int,input().split(" "))) for i in range(N)]
P = sorted(R)
cnt = 0
k = 0
for i in range(N):
    if P[i][1]>0:
        k = -(-P[i][1]//A)
        cnt += k 
        for j in range(1,N-i):
            if P[i][0]<P[i+j][0]<=P[i][0]+2 * D:
                P[i+j][1] += -k*A
            else:
                break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math
def bisect_right(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] <= x: lo = mid+1
        else: hi = mid
    return lo

n, d, a = map(int,input().split())
xhlist=[]
for i in range(n):
    x, h = map(int,input().split())
    h=math.ceil(h/a)
    xhlist.append([x, h])

xhlist=sorted(xhlist)
xlist=[]
hlist=[]
for xhl in xhlist:
    xlist.append(xhl[0])
    hlist.append(xhl[1])

now=0
turn=0
memory=0

while now<n:
    swit=0
    pos=xlist[now]+d
    atk=hlist[now]
    if memory>0:
        hani=bisect_right(xlist, pos+d, lo=memory)
        memory=hani
    else:
        hani=bisect_right(xlist, pos+d)
        memory=hani
    tasu=0
    turn+=atk
    sa=hani-now
    for i in range(sa):
        if now+i<n:
            if hlist[now+i]>0:
                hlist[now+i]-=atk
            if swit==0:
                if hlist[now+i]<=0:
                    tasu+=1
                else:
                    swit=1
    now+=tasu
    
print(turn)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from math import ceil
N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort(key = lambda x:x[0])
X,H = map(list, zip(*XH))

ans = 0
for i,xh in enumerate(XH):
    X = xh[0]
    H = xh[1]
    if H > 0:
        num = ceil(H/A)
        for j in range(i,N):
            if XH[j][0] <= X+2*D:
                XH[j][1] -= A*num
            else:
                break
        ans += num
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A = map(int, input().split())
P=[]
for i in range(N):
    L = list(map(int, input().split()))
    if(L[1]%A==0):
        L[1]=int(L[1]/A)
    else:
        L[1]=int(L[1]/A)+1
    L.append(L[0]-D)
    L.append(L[0]+D)
    P.append(L)
P.sort()
#print(P)
ans=0
for i in range(N):
    while(P[i][1]>0):
        ans+=1
        P[i][1]-=1
        for j in range(i+1,N):
            if(P[i][3]>=P[j][2]):
                P[j][1]-=1
            else:
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

N, D, A = map(int, input().split())

L = list()

for i in range(N):
  X, H = map(int, input().split())
  L.append([X,H])

L.sort()
s = 0

for i,(x, h) in enumerate(L):
  num = math.ceil(h/A)
  s += num
  if i+1 != len(L) and num != 0:
    for j,(jx,jh) in enumerate(L[i+1:]):
      if jx > x+D+D:
        break
      else:
        L[i+j+1][1] = max(0,jh - num*A)
print(s)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math

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

ans = 0
for i, (xi, hi) in enumerate(monsters):
  if (hi > 0):
    times = math.ceil(hi / a) 
    dmg= times * a
    ans += times
    index_r = bisect.bisect_right(monsters, [xi + 2 * d, float("inf")], lo=i, hi=n)
    if (i < n - 1):
      for monster in monsters[i + 1: index_r]:
        monster[1] = max(0, monster[1] - dmg)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def inpl():
    return list(map(int, input().split()))


N, D, A = inpl()
XH = [inpl() for i in range(N)]
XH.sort()
# print(XH)

bomb = [(h + A - 1) // A for x, h in XH]

ans = 0
queue = []
s_i = 0
for i in range(N):
    tmp = 0
    for b, last in queue[s_i:]:
        if XH[i][0] > last:
            s_i += 1
        else:
            tmp += b
            break

    bomb[i] -= tmp
    if bomb[i] <= 0:
        pass
    else:
        ans += bomb[i]
        for j in range(s_i, len(queue)):
            queue[j][0] += bomb[i]
        queue.append([bomb[i], XH[i][0] + 2 * D])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A = map(int,input().split())
X = []
for _ in range(N):
    x,h = map(int,input().split())
    X.append([x,h])
X.sort()
ans = 0
for i in range(N):
    h = int(X[i][1])
    if h != 0:
        x = int(X[i][0])
        if h % A == 0:
            count = h // A
        else:
            count = h // A + 1
        ans += count
        dmg = A * count
    #print(ans,dmg)
        for j in range(i+1,N):
            x2 = int(X[j][0])
            h2 = int(X[j][1])
            if  x + (2 * D) < x2:
                break
            else:
                X[j][1] = max(0,h2-dmg)
                #print(X[j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a = inp()
        a -= 1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    n,d,a = inpm()
    xh = []
    for _ in range(n):
        x,h = inpm()
        key = h//a
        if h%a != 0:
            key += 1
        xh.append((x,key))
    xh.sort()
    ans = xh[0][1]
    r = deque()
    r.append((xh[0][0]+d,xh[0][1]))
    for i in range(1,n):
        [x,h] = xh[i]
        while r:
            if r[0][0]<x-d:
                r.popleft()
            else:
                break
        if r:
            num = len(r)
            index = 0
            while index < num and h > 0:
                h -= r[index][1]
                index += 1
            if h > 0:
                ans += h
                r.append((x+d,h))
        else:
            r.append((x+d,h))
            ans += h
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

n, d, a = map(int, input().split())
monster = [[0, 0] for i in range(n)]

for i in range(n):
  x, h = map(int, input().split())
  monster[i] = [x, h]

monster.sort(key = lambda x : x[0])
x = [0 for i in range(n)]
h = [0 for i in range(n)]
for i in range(n):
  x[i] = monster[i][0]
  h[i] = monster[i][1]

ans = 0
idx = 0
while True:
  if idx == n:
    break
  if h[idx] > 0:
    idx2 = bisect.bisect_right(x, x[idx] + d * 2) - 1
    bomb = (h[idx] + a - 1) // a
    ans += bomb
    for i in range(idx, idx2 + 1):
      h[i] = max(h[i] - a * bomb, 0)
  idx += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
fastinput = sys.stdin.readline
N,D,A = [int(i) for i in fastinput().split()]
preXH = [[int(i) for i in fastinput().split()] for j in range(N)]
preXH.sort()
XH = [[x,h//A + bool(h%A)] for x,h in preXH]
X = [x for x,h in XH]+[100000000000000000]
Diff = [X[m+1]-X[m] for m in range(N)]
reach = []
count = 0
l = X[0]
r = X[0]+2*D
for m in range(1,N+1):
    while r<X[m]:#l一個すすめる
        reach.append(m-1)
        r += Diff[count]
        count += 1

ans = 0
DP = [0]*N#ダメイジの合計
for n,d in enumerate(DP):
    if d<XH[n][1]:#殺しきれてない
        bonu = XH[n][1]-d
        ans += bonu
        for m in range(n,reach[n]+1):
            DP[m] += bonu
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math


def main():
        
    N,D,A = map(int, input().split())

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

    xh.sort()

    ans = 0
    for i in range(N):
        if xh[i][1] <= 0:
            continue
        
        cnt = math.ceil(xh[i][1] / A)
        ans += cnt
        xh[i][1] = 0

        if cnt == 0:
            continue

        for j in range(i+1, N):

            if xh[j][0] > xh[i][0] + 2*D:
                break
            xh[j][1] -= cnt*A

        #print(ans, xh)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,d ,a = map(int,input().split())
xh = []
for _ in range(n):
    x,y = map(int,input().split())
    kaisuu = y // a if y % a == 0 else y//a +1
    xh.append([x,kaisuu])
xh.sort()
migihasi = xh[0][0] + (2*d)
ans = 0
hidarindex = 0
bombs = [(xh[0][1],migihasi)] #[はぜる回数、右端]
for i in range(1,n):
    needkaisuu = xh[i][1]
    zahyo = xh[i][0]
    for cnt,migi in bombs:
        if zahyo <= migi and zahyo >= migi - (2*d):
            needkaisuu -= cnt
        if needkaisuu <=0:break
    if needkaisuu >0:
        bombs.append((needkaisuu,zahyo+(2*d)))
for x,y in bombs:
    ans+= x
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
input = sys.stdin.buffer.readline
N,D,A= map(int,input().split())
XH = [list(map(int,input().split())) for i in range(N)]
XH.sort()
X,H = [list(x) for x in zip(*XH)]

ans = 0
for i in range(N):
    x = X[i]
    if H[i] <= 0:
        continue
    cnt_bom = -(-H[i] // A)
    ans += cnt_bom
    damage = cnt_bom * A
    ind = bisect.bisect_right(X,x+2*D)
    for j in range(i,ind):
        H[j] -= damage
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a = inp()
        a -= 1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    n,d,a = inpm()
    xh = []
    for _ in range(n):
        x,h = inpm()
        key = h//a
        if h%a != 0:
            key += 1
        xh.append([x,key])
    xh.sort()
    ans = xh[0][1]
    r = deque()
    r.append([xh[0][0]+d,xh[0][1]])
    for i in range(1,n):
        [x,h] = xh[i]
        while r:
            if r[0][0]<x-d:
                r.popleft()
            else:
                break
        if r:
            num = len(r)
            index = 0
            while index < num and h > 0:
                h -= r[index][1]
                index += 1
            if h > 0:
                ans += h
                r.append([x+d,h])
        else:
            r.append([x+d,h])
            ans += h
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque
input = sys.stdin.readline
N, D, A = map(int,input().split())
XH = [list(map(int,input().split())) for i in range(N)]
XH.sort()
ans = 0
for i in range(N):
    if XH[i][1] > 0:
        p = XH[i][0]
        t = A*math.ceil(XH[i][1] / A)
        ans += math.ceil(XH[i][1] / A)
        for l in range(i, N):
            if XH[l][0] <= p + 2 * D:
                XH[l][1] -= t
            else:
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

N, D, A = map(int, input().split())
M = [tuple(map(int, input().split())) for i in range(N)]

M.sort()
X = [M[i][0] for i in range(N)]
H = [M[i][1] for i in range(N)]
ans = 0
for i in range(N):
    if H[i] <= 0:
        continue
    blast_r = X[i] + 2 * D
    max_j = bisect_right(X, blast_r, i + 1)
    c = (H[i] + A - 1) // A
    ans += c
    if i + 1 < max_j:
        H[i + 1:max_j] = [H[j] - A * c for j in range(i + 1, max_j)]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect
    def _add(data,k,x):
        while k<=N:
            data[k]+=x
            k+=k&-k
    def add(l,r,x):
        _add(data0,l,-x*(l-1))
        _add(data0,r,x*(r-1))
        _add(data1,l,x)
        _add(data1,r,-x)
    def _get(data,k):
        s=0
        while k:
            s+=data[k]
            k-=k&-k
        return s
    def query(l,r):
        return _get(data1,r-1)*(r-1)+_get(data0,r-1)-_get(data1,l-1)*(l-1)-_get(data0,l-1)
    N,d,a,*t=map(int,open(0).read().split())
    data0=[0]*(N+1)
    data1=[0]*(N+1)
    z=sorted(zip(*[iter(t)]*2))
    y=[x for x,_ in z]
    c=0
    for i,(x,h)in enumerate(z,1):
        h-=query(i,i+1)
        t=0--max(0,h)//a
        j=bisect(y,x+d+d)
        add(1,j+1,t*a)
        c+=t
    print(c)
main()

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()
    result = 0
    for i in range(N):
        x, h = XH[i]
        if h < 0:
            continue
        c = (h + (A - 1)) // A
        result += c
        for j in range(i + 1, N):
            if XH[j][0] > x + 2 * D:
                break
            XH[j][1] -= c * A
    print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
[N,D,A] = list(map(int,input().split()))
XH = []
for i in range(N):
    XH.append(list(map(int,input().split())))

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

output = 0
s = 0
while s<N:
    if XH[s][1]<0:
        s+=1
        continue
    X = XH[s][0]
    L = X
    H = XH[s][1]
    B = H//A+1*(H%A!=0)
    output += B
    flag = 0
    s+=1
    while (s<N)and(XH[s][0]<=L+2*D):
        if XH[s][1]>0:
            XH[s][1]+= -1*B*A
        if (XH[s][1]>0)and(flag==0):
            start=s
            flag = 1
        s+=1
    if flag ==1:
        s=start

print(output)

Submission status: Time Limit Exceeded

Solution code:
n, d, a = map(int, input().split())

enemy = []

for i in range(n):
    enemy.append(list(map(int, input().split())))

enemy = sorted(enemy)

ans = 0

for i in range(len(enemy)):
    if enemy[i][1] > 0:
        hp = enemy[i][1]
    else:
        continue
    
    attack = -(-hp//a)
    ans += attack

    pos = enemy[i][0] + d * 2
    dam = a * attack
    for j in range(i+1, len(enemy)):
        if enemy[j][0] <= pos:
            enemy[j][1] -= dam
        else:
            break


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
ans=0
while xh:
    tmp=xh.pop()
    # print(tmp)
    if tmp[1]<=0:
        continue
    zahyo=tmp[0]-d*2
    kaisu=math.ceil(tmp[1]/a)
    ans+=kaisu
    # print(zahyo,kaisu)
    for i in range(len(xh)):
        if xh[-1-i][0]>=zahyo:
            xh[-1-i][1]-=kaisu*a
        else:
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n, d, a = map(int, input().split())
monster = [[0, 0] for i in range(n)]

for i in range(n):
  x, h = map(int, input().split())
  monster[i] = [x, h]

monster.sort(key = lambda x : x[0])
x = [0 for i in range(n)]
for i in range(n):
  x[i] = monster[i][0]

ans = 0
idx = 0
for idx in range(n):
  if monster[idx][1] > 0:
    idx2 = bisect.bisect_right(x, x[idx] + d * 2) - 1
    bomb = (monster[idx][1] + a - 1) // a
    ans += bomb
    for i in range(idx, idx2 + 1):
      monster[i][1] -= a * bomb

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, D, A=(int(i) for i in input().split())
P=[[int(i) for i in input().split()] for  _ in range(N)]
P=sorted(P, key=lambda x:x[0])

ans=0

for i in range(N):
    if P[i][0]>0:
        if P[i][1]%A==0:
            bomb=P[i][1]//A
        else:
            bomb=P[i][1]//A+1
        ans+=bomb
        for j in range(N):
            if P[j][0]<=P[i][0]+2*D:
                P[j][1]-=A*bomb
            else:
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from math import ceil
    from bisect import bisect_right
    N, D, A = map(int, input().split())
    Monsters = [list(map(int, input().split())) for i in range(N)]
    Monsters = sorted([[x, ceil(h / A)] for x, h in Monsters])


    class BIT2:
        """ 区間加算BIT(区間加算・区間合計取得) """

        def __init__(self, N):
            self.N = N
            self.data0 = [0] * N
            self.data1 = [0] * N

        def _add(self, data, k, x):
            while k < self.N:
                data[k] += x
                k += k & -k

        def _get(self, data, k):
            s = 0
            while k:
                s += data[k]
                k -= k & -k
            return s

        def add(self, l, r, x):
            """ 区間[l,r)に値xを追加 """

            self._add(self.data0, l, -x*(l-1))
            self._add(self.data0, r, x*(r-1))
            self._add(self.data1, l, x)
            self._add(self.data1, r, -x)

        def query(self, l, r):
            """ 区間[l,r)の和を取得 """

            return self._get(self.data1, r-1) * (r-1) + self._get(self.data0, r-1) \
                 - self._get(self.data1, l-1) * (l-1) - self._get(self.data0, l-1)


    RUQ = BIT2(2 * N)
    for i, (x, h) in enumerate(Monsters, start=1):
        RUQ.add(i, i + 1, h)


    i = 0
    ans = 0
    while i < N:
        cost = RUQ.query(i + 1, i + 2)
        if cost > 0:
            index = bisect_right(Monsters, [Monsters[i][0] + 2 * D, float('inf')])
            RUQ.add(i + 1, index + 1, -cost)
            ans += cost
        i += 1
        #
        # check = []
        # for j in range(1, N + 1):
        #     check.append(str(RUQ.query(j, j + 1)))
        # print(' '.join(check))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, D, A = [int(s) for s in input().split()]
d = D*2
mons = []
for i in range(N):
    X, H = [int(s) for s in input().split()]
    H = (H-1)//A + 1
    mons.append([X,H])
mons.sort()
# print(mons)
ans = 0
mons.append([-d-1,0])  # for conv
for end in range(len(mons)-1,-1,-1):
    right, att = mons[end]
    if att <= 0:
        continue
    ans += att
    bar = right - d
    j = end-1
    while mons[j][0] >= bar:
        mons[j][1] -= att
        j -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import*
def _add(data,k,x):
    while k<=N:
        data[k]+=x
        k+=k&-k
def add(l,r,x):
    _add(data0,l,-x*(l-1))
    _add(data0,r,x*(r-1))
    _add(data1,l,x)
    _add(data1,r,-x)
def _get(data,k):
    s=0
    while k:
        s+=data[k]
        k-=k&-k
    return s
def query(l,r):
    return _get(data1,r-1)*(r-1)+_get(data0,r-1)-_get(data1,l-1)*(l-1)-_get(data0,l-1)
N,d,a,*t=map(int,open(0).read().split())
data0=[0]*(N+1)
data1=[0]*(N+1)
z=sorted(zip(*[iter(t)]*2))
y=[x for x,_ in z]
c=0
for i,(x,h)in enumerate(z,1):
    h-=query(i,i+1)
    t=0--max(0,h)//a
    j=bisect(y,x+d+d)
    add(1,j+1,t*a)
    c+=t
print(c)

Submission status: Time Limit Exceeded

Solution code:
N,D,A = map(int,input().split())
X = []
for _ in range(N):
    x,h = map(int,input().split())
    X.append([x,h])
X.sort()
ans = 0
for i in range(N):
    x = int(X[i][0])
    h = int(X[i][1])
    if h % A == 0:
        count = h // A
    else:
        count = h // A + 1
    ans += count
    dmg = A * count
    #print(ans,dmg)
    for j in range(i+1,N):
        x2 = int(X[j][0])
        h2 = int(X[j][1])
        if  x + (2 * D) < x2:
            break
        else:
            X[j][1] = max(0,h2-dmg)
            #print(X[j])
print(ans)

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)

kougeki_start = 0
kougeki_end = 0
cnt = 0
for i in range(n):
    if h[i] > 0:
        left = i # 可能
        right = n # 不可能
        while left+1 < right:
            mid = (left + right) // 2
            if x[mid] - x[i] <= 2*d:
                left = mid
            else:
                right = mid
        cnt += h[i]
        hiku = h[i]
        for j in range(i, left+1):
            h[j] -= hiku

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N, D, A = map(int, input().split())
M = [tuple(map(int, input().split())) for i in range(N)]

M.sort()
X = [M[i][0] for i in range(N)]
H = [M[i][1] for i in range(N)]
ans = 0
for i in range(N):
    if H[i] <= 0:
        continue
    blast_r = X[i] + 2 * D
    max_j = N
    for j in range(i + 1, N):
        if X[j] > blast_r:
            max_j = j
            break
    c = (H[i] + A - 1) // A
    ans += c
    if i + 1 < max_j:
        H[i + 1:max_j] = [H[j] - A * c for j in range(i + 1, max_j)]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from math import ceil
N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort(key = lambda x:x[0])
X,H = map(list, zip(*XH))

ans = 0
for i in range(N):
    if H[i] > 0:
        num = ceil(H[i]/A)
        for j in range(i,N):
            if X[j] <= X[i]+2*D:
                H[j] -= A*num
            else:
                break
        ans += num
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def inpl():
    return list(map(int, input().split()))


N, D, A = inpl()
XH = [inpl() for i in range(N)]
XH.sort()
# print(XH)

bomb = [(h + A - 1) // A for x, h in XH]

ans = 0
queue = []
s_i = 0
for i in range(N):
    tmp = 0
    for b, last in queue[s_i:]:
        if XH[i][0] > last:
            s_i += 1
        else:
            tmp += b

    bomb[i] -= tmp
    if bomb[i] <= 0:
        pass
    else:
        ans += bomb[i]
        queue.append([bomb[i], XH[i][0] + 2 * D])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    from bisect import bisect_left, bisect_right
    import sys
    input = sys.stdin.readline

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def setInit(As):
        for iB, A in enumerate(As, 1):
            data[iB] = A
        for iB in range(1, numPow2):
            i = iB + (iB & -iB)
            data[iB] -= data[i]
    def addValue(iA, A):
        iB = iA + 1
        while iB > 0:
            data[iB] += A
            iB -= iB & -iB
    def getValue(iA):
        iB = iA + 1
        ans = 0
        while iB <= numPow2:
            ans += data[iB]
            iB += iB & -iB
        return ans
    def addRangeValue(iFr, iTo, A):
        addValue(iTo, A)
        if iFr > 0:
            addValue(iFr-1, -A)

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

    XHs.sort()
    Xs = [X for X, H in XHs]
    Hs = [H for X, H in XHs]

    data, numPow2 = makeBIT(N)
    setInit(Hs)

    ans = 0
    for iL in range(N):
        H = getValue(iL)
        if H <= 0: continue
        iR = bisect_right(Xs, Xs[iL]+2*D) - 1
        num = -(-H // A)
        addRangeValue(iL, iR, -num*A)
        ans += num

    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
n, d, a = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
m.sort()
r = 1
d *= 2
for i in range(n):
    while r < n and m[i][0] + d >= m[r][0]:
        r += 1
    m[i].append(r - 1)
    m[i][1] = (m[i][1] + a - 1) // a
res = 0
for i in range(n):
    if m[i][1] > 0:
        res += m[i][1]
        for j in range(i + 1, m[i][2] + 1):
            m[j][1] -= m[i][1]
print(res)

Submission status: Time Limit Exceeded

Solution code:
[N,D,A] = list(map(int,input().split()))
XH = []
for i in range(N):
    XH.append(list(map(int,input().split())))

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

output = 0
s = 0
while s<N:
    if XH[s][1]<0:
        s+=1
        continue
    X = XH[s][0]
    L = X
    H = XH[s][1]
    B = H//A+1*(H%A!=0)
    output += B
    flag = 0
    s+=1
    while (s<N)and(XH[s][0]>=L-2*D):
        XH[s][1]+= -1*B*A
        if (XH[s][1]>0)and(flag==0):
            start=s
            flag = 1
        s+=1
    if flag ==1:
        s=start

print(output)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
import numpy as np
import sys
input = sys.stdin.readline
N, D, A = map(int,input().split())
xx = []
hh = []
for i in range(N):
    x1, h1 = map(int,input().split())
    h2 = h1 // A
    if h1 % A != 0:
        h2 += 1
    xx.append(x1)
    hh.append(h2)

u = np.argsort(xx)
x = []
h = []
for i in u:
    x.append(xx[i])
    h.append(hh[i])
    
ans = 0
for i in range(N):
    if h[i] > 0:
        d = h[i]
        ans += d
        idx = bisect_left(x, x[i]+(2 * D))
        if idx != N and x[idx] == x[i] + (2 * D):
            idx += 1
        for j in range(i,idx):
            h[j] -= d
    else:
        continue
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

N, D, A = map(int, input().split())

L = list()

for i in range(N):
  X, H = map(int, input().split())
  L.append([X,H])

L.sort()
s = 0

for i,(x, h) in enumerate(L):
  num = math.ceil(h/A)
  s += num
  if i+1 == len(L):
    pass
  else:
    for j,(jx,jh) in enumerate(L[i+1:]):
      if jx > x+D+D:
        break
      else:
        L[i+j+1][1] = max(0,L[i+j+1][1] - num*A)
print(s)

Submission status: Time Limit Exceeded

Solution code:
import math
def bisect_right(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] <= x: lo = mid+1
        else: hi = mid
    return lo

n, d, a = map(int,input().split())
xlist=[]
xhlist=[]
for i in range(n):
    x, h = map(int,input().split())
    h=math.ceil(h/a)
    xhlist.append([x, h])
    xlist.append(x)

xhlist=sorted(xhlist)
xlist=sorted(xlist)

now=0
turn=0
memory=0

while now<n:
    swit=0
    pos=xhlist[now][0]+d
    atk=xhlist[now][1]
    if memory>0:
        hani=bisect_right(xlist, pos+d, lo=memory)
        memory=hani
    else:
        hani=bisect_right(xlist, pos+d)
        memory=hani
    tasu=0
    turn+=atk
    sa=hani-now
    for i in range(sa):
        if now+i<n:
            if xhlist[now+i][1]>0:
                xhlist[now+i][1]-=atk
            if swit==0:
                if xhlist[now+i][1]<=0:
                    tasu+=1
                else:
                    swit=1
    now+=tasu
    
print(turn)

Submission status: Time Limit Exceeded

Solution code:
import math
n,d,a = map(int,input().split())
if d == 0:
  d += 1
e = []
for i in range(n):
  x,h = map(int,input().split())
  e.append([x/d,math.ceil(h/a)])
e.sort()
ans = 0
for i in range(n):
  at = e[i][1]
  if at > 0:
    ans += at
    hani = e[i][0] + 2
    for j in range(i,n):
      if e[j][0] <= hani:
        e[j][1] -= at
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, d, a = map(int, input().split())

enemy = []

for i in range(n):
    enemy.append(list(map(int, input().split())))

enemy = sorted(enemy)

ans = 0

for i in range(len(enemy)):
    if enemy[i][1] > 0:
        hp = enemy[i][1]
    else:
        continue
    
    attack = -(-hp//a)
    ans += attack

    pos = enemy[i][0] + d * 2
    for j in range(i+1, len(enemy)):
        if enemy[j][0] <= pos:
            enemy[j][1] -= a * attack
        else:
            break


print(ans)