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:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,d,a = inm()
xh = []
for i in range(n):
    xx,hh = inm()
    xh.append((xx,(hh+a-1)//a))
xh.sort()
xhl = [ [z[0], z[1]] for z in xh ]
cnt = 0
i = 0
while i<n:
    x = xhl[i][0]
    h = xhl[i][1]
    if h<=0:
        i += 1
        continue
    j = i
    while j<n-1 and xhl[j+1][0]<=x+2*d:
        j += 1
    for k in range(i,j+1):
        xhl[k][1] -= h
    cnt += h
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
import numpy as np

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:
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 = X[i][0]
    h = 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):
        if  x + (2 * D) < X[j][0]:
            break
        else:
            X[j][1] = max(0,X[j][1]-dmg)
            #print(X[j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n, d, a = [int(v) for v in input().strip().split()]
mobs = [tuple(int(v) for v in input().strip().split()) for _ in range(n)]
mobs = sorted(mobs, key=lambda m: m[0])

count = 0
for s in range(len(mobs)):
    left = mobs[s]
    if left[1] <= 0:
        continue
    e = s
    bom_range = left[0] + 2 * d
    for ec in range(s, len(mobs)):
        if mobs[ec][0] > bom_range:
            break
        else:
            e = ec
    cnt = left[1] // a + min(left[1] % a, 1)
    count += cnt
    dmg = cnt * a
    for i in range(s, e + 1):
        m = mobs[i]
        mobs[i] = (m[0], m[1] - dmg)

print(count)

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
for i in range(N):
	if XH[i,1] <= 0:
		continue
	cp = XH[i,0]
	R = cp + (2*D)
	ind = np.searchsorted(XH[:,0],R, side='right')
	attack = -(-XH[i,1]//A)
	ans += attack
	XH[i:ind,1] -= attack*A

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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)

h = np.array(h)

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]
        h[i:left+1] -= h[i]

print(cnt)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

def solve():
    from bisect import bisect_right

    N,D,A = II()
    X,H = Line(N,2)
    #Binary Indexed Tree（区間加算）
    #1-indexed
    class Range_BIT():
        def __init__(self, N):
            self.size = N
            self.data0 = [0]*(N+1)
            self.data1 = [0]*(N+1)

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

        # 区間[l,r)にxを加算
        def add(self, 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 _get(self, data, k):
            s = 0
            while k:
                s += data[k]
                k -= k & -k
            return s

        # 区間[l,r)の和を求める
        def query(self, 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)

    #インデックス付きソート
    #(index,value)の順に格納
    from operator import itemgetter
    def index_sort(A):
        return sorted(enumerate(A),key=itemgetter(1))

    num = [math.ceil(H[i]/A) for i in range(N)]
    temp = index_sort(X)

    X2 = [temp[i][1] for i in range(N)]
    num = [num[t[0]] for t in temp]

    bit = Range_BIT(N)
    for i in range(1,N+1):
        bit.add(i,i+1,num[i-1])

    ans = 0
    for i in range(1,N+1):
        if bit.query(i,i+1)<=0:
            continue
        p = bisect_right(X2,X2[i-1]+2*D)
        c = bit.query(i,i+1)
        bit.add(i,p+1,-c)
        ans += c

    print(ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
n,d,a = map(int, input().split())
xh = []
ans = 0
for i in range(n):
    x,h = map(int, input().split())
    xh.append([x,h])

xh.sort()

def hani(a):
    r = a + 2 * d
    for i in range(n):
        if xh[i][0] > r:
            return i - 1
    return n - 1


while n != 0:
    z = (xh[0][1] - 1) // a + 1
    ans += z
    m = z * a
    for j in range(hani(xh[0][0]), -1, -1):
        if xh[j][1] <= m:
            del xh[j]
            n -= 1
        else:
            xh[j][1] -= m
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,d,a = map(int,input().split())
    l = [list(map(int,input().split())) for i in range(n)]
    l.sort()
    count = 0
    import math

    i = 0
    

    while True:
        sn = i
        s = l[i][0]
        s += 2*d
        mi = math.ceil(l[i][1]/a)
        count += mi
        b = mi*a
        l1 = 0
        while i < n and l[i][0] <= s:
            
            l[i][1] -= b
            if l[i][1] > 0:
                if l1 == 0:
                    l1 = i
            i += 1
            
        if l1 > 0:
            i = l1
        else:
            if i == n:
                print(count)
                exit()
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from math import ceil
from bisect import bisect
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:
        tmp = bisect(X,X[i]+2*D)
        num = ceil(H[i]/A)
        for j in range(i,tmp):
            H[j] -= A*num
        ans += num
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, D,A = map(int, input().split())
R =[] * N
for i in range(N):
    v, w = map(int, input().split())
    R.append([v,w])
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 sys
n, D, a = map(int, input().split())
tg = []
for _ in range(n):
    x, h = map(int, sys.stdin.readline().split())
    c = h // a
    if h % a > 0:
        c+=1
    tg.append([x, c])


tg = sorted(tg, key=lambda x:x[0])
result = 0
for i in range(n):
    c = tg[i][1]
    d = tg[i][0]
    if c <= 0:
        continue
    result += c
    wd = d + 2*D
    for j in range(i, n):
        if tg[j][0] <= wd:
            tg[j][1] -= c
        else:
            break
print(result)

Submission status: Time Limit Exceeded

Solution code:
n,d,a=map(int,input().split())
x=[]
h=[]
xh=[]
for _ in range(n):
    i,j = map(int,input().split())
    xh.append((i,j))
xh = sorted(xh, key=lambda x: x[0])
c=[]
ans=0
max_=[]
for i in range(n):
    value = xh[i][1]
    for ii,m in enumerate(max_):
        if m>=xh[i][0]:
            value -= a * c[ii]
    #print(xh[i][0],value)
    temp = max(0,-(-value//a))
    ans += temp
    c.append(temp)
    max_.append(xh[i][0]+2*d)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n,d,a=map(int,input().split())
  l=[[0,0] for _ in range(n)]
  for i in range(n):
    x,h=map(int,input().split())
    l[i]=[x,h]
  l.sort()
  ans=0
  for i in range(n):
    [x,h]=l[i]
    if h>=0:
      c=(h+a-1)//a
      for j in range(i+1,n):
        if l[j][0]>x+2*d:
          break
        else:
          l[j][1]-=c*a
      ans+=c
  print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter


def solve():
    N, D, A = map(int, input().split())
    XH = [[0, 0] for _ in range(N)]
    for i in range(N):
        XH[i][0], XH[i][1] = map(int, input().split())
    XH.sort(key=itemgetter(0))
    
    ans = 0
    for i in range(N):
        if XH[i][1] <= 0:
            continue
        
        p = XH[i][0] + 2 * D
        if XH[i][1] % A == 0:
            n = XH[i][1] // A
        else:
            n = XH[i][1] // A + 1
        for j in range(i + 1, N):
            if p < XH[j][0]:
                break
            XH[j][1] -= A * n
        ans += n
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

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

    for i in range(N):
        x, h = map(int, input().split())
        B.append((x,h))

    B.sort()
    X = [0] * N
    H = [0] * N
    for i in range(N):
        X[i], H[i] = B[i]
    ans = 0
    ok = [False] * N
    for i in range(N):
        if ok[i]:
            continue
        cnt = H[i] // A if H[i] % A == 0 else H[i] // A + 1
        ans += cnt
        ok[i] = True
        search_max = bisect_right(X, X[i] + 2 * D) - 1
        for j in range(min(i+1,N),min(search_max+1,N)):
            if ok[j]:
                continue
            H[j] -= cnt * A
            if H[j] <= 0:
                ok[j] = True
    
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import bisect
    import math
    n,d,a=map(int,input().split())
    xh=[list(map(int,input().split())) for i in range(n)]
    xh.sort()
    x=[xh[i][0] for i in range(n)]
    h=[xh[i][1] for i in range(n)]
    cnt=0
    for i in range(n):
        if h[i]>0:
            m=math.ceil(h[i]/a)
            cnt+=m
            k=bisect.bisect_right(x,x[i]+2*d,lo=i)
            for j in range(i,k):
                h[j]-=(m*a)
    print(cnt)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,d,a = map(int,input().split())
    l = [list(map(int,input().split())) for i in range(n)]
    l.sort()
    count = 0
    import math

    i = 0
    

    while True:
        sn = i
        s = l[i][0]
        mi = math.ceil(l[i][1]/a)
        count += mi
        
        l1 = 0
        while i < n and l[i][0] <= s+2*d:
            
            l[i][1] -= mi*a
            if l[i][1] > 0:
                if l1 == 0:
                    l1 = i
            i += 1
            
        if l1 > 0:
            i = l1
        else:
            if i == n:
                print(count)
                exit()
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N):
    if XH[i][1] > 0:
        n_bomb = -(-XH[i][1]//A)
        ans += n_bomb
        j = i
        while j <= N-1 and XH[j][0] <= XH[i][0] + 2*D:
            XH[j][1] -= n_bomb * A
            j += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A=map(int,input().split())
L=[]
for i in range(N):
    x,h=map(int,input().split())
    L.append([x,h])
L.sort()
ans=0
R=0
F=0
import math
for i in range(N):
    if L[i][1]>0:
        R=L[i][0]+2*D
        ans+=math.ceil(L[i][1]/A)
        F=math.ceil(L[i][1]/A)*A
        for j in range(i+1,N):
            if L[j][0]<=R:
                L[j][1]-=F
    #print(L)
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]
ans = 0
DP = [0]*N#ダメイジの合計
for n,d in enumerate(DP):
    if d<XH[n][1]:#殺しきれてない
        bonu = XH[n][1]-d
        ans += bonu
        reach = XH[n][0] + 2*D
        for m in range(n,N):
            if XH[m][0] <= reach:
                DP[m] += bonu
            else:break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

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())
    xhlist.append([x, h])
    xlist.append(x)

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


hlist2=np.asarray(hlist)

now=0
turn=0
memory=0
arr = np.asarray([1,2,3])

while now<n:
    swit=0
    pos=xhlist[now][0]+d
    atk=math.ceil(hlist2[now]/a)*a
    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//a
    hlist2-=np.asarray([atk]*hani+[0]*(n-hani))
    while now<n and swit==0:
        if hlist2[now]<=0:
            now+=1
        else:
            swit=1
    
print(turn)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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)

h = np.array(h)

kougeki_start = 0
kougeki_end = 0
cnt = 0
for i in range(n):
    if h[i] > 0:
        j = i + 1
        while x[j] - x[i] <= 2*d:
            j += 1
        j -= 1
        cnt += h[i]
        h[i:j+1] -= h[i]

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def find_threshold(monster, D):
    start = 0
    end = len(monster)
    while True:
        test = (start + end)//2
        if monster[test][0] <= monster[0][0] + 2*D:
            start = test
        else:
            end = test
        if end-start == 1:
            break
    return end


def attack(monster, D, A):
    num = (monster[0][1]-1)//A + 1
    new_monster = []
    sep = find_threshold(monster, D)
    
    monster_attacked = monster[:sep]
    if sep < len(monster):
        monster_remain = monster[sep:]
    else:
        monster_remain = []
    
    for elem in monster_attacked:
        if elem[1] > num*A:
            new_monster.append([elem[0], elem[1] - num*A])
    new_monster += monster_remain
    
    if len(new_monster) == 0:
        flag=True
    else:
        flag=False
    #print(num, new_monster, flag)
    return num, new_monster, flag



N, D, A = map(int,input().split())
monster = []
for i in range(N):
    x, h = map(int,input().split())
    monster.append([x,h])
    
monster = sorted(monster, key=lambda x: x[0])

total = 0
while True:
    num, monster, flag = attack(monster, D, A)
    total += num 
    if flag == True:
        break

print(total)

Submission status: Time Limit Exceeded

Solution code:
N,D,A = map(int, input().split())
L = [[int(l) for l in input().split()] for _ in range(N)]

L.sort()
ans = 0
for i in range(N):
    if L[i][1] <= 0:
        continue
    num = L[i][1]//A+min(1, L[i][1]%A)
    ans += num
    j = i+1
    while j < N and L[j][0] <= L[i][0]+2*D:
        L[j][1] -= num*A
        j += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, D, A = map(int, input().split(' '))
X_H_pairs = [list(map(int, input().split(' '))) for _ in range(N)]

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

import math
i, ans = 0, 0
while i < N:
    x, h = X_H_pairs[i]
    if h <= 0:
        i += 1
        continue
    else:
        times = int(math.ceil(h / A))
        ans += times

        dh = times * A
        dx = x + 2*D
        j = i
        while j < N and X_H_pairs[j][0] <= dx:
            X_H_pairs[j][1] -= dh
            j += 1
        i += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,D,A = [int(i) for i in input().split()]
preXH = [[int(i) for i in input().split()] for j in range(N)]
preXH.sort()
XH = [[x,h//A + bool(h%A)] for x,h in preXH]
Xs = [xxx[0] for xxx in XH]
ans = 0
DP = [0]*N#ダメイジの合計
for n,d in enumerate(DP):
    if d<XH[n][1]:#殺しきれてない
        bonu = XH[n][1]-d
        ans += bonu
        reach = XH[n][0] + 2*D
        for m in range(n,N):
            if XH[m][0] <= reach:
                DP[m] += bonu
            else:break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, d, a = [int(v) for v in input().split()]
mobs = [tuple(int(v) for v in input().split()) for _ in range(n)]
mobs = sorted(mobs, key=lambda m: m[0])

count = 0
for s in range(len(mobs)):
    left = mobs[s]
    if left[1] <= 0:
        continue
    e = s
    bom_range = left[0] + 2 * d
    for ec in range(s, len(mobs)):
        if mobs[ec][0] > bom_range:
            break
        else:
            e = ec
    cnt = left[1] // a + min(left[1] % a, 1)
    count += cnt
    dmg = cnt * a
    for i in range(s, e + 1):
        m = mobs[i]
        mobs[i] = (m[0], m[1] - dmg)

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

cnt = 0
arr = []
for i in range(n):
    x,h = map(int,input().split())
    arr.append([x,h])
arr.sort(key=lambda x:x[0])

# print("input finish")




class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = defaultdict(int)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


bit = Bit(10**9+1)
edge = 10**9+1

# print("bit_prepared")

ans = 0
for i in range(n):
    x,h = arr[i]
    x += 1
    corr_left = max(1,x-d-1)
    corr_right = min(edge,x+d)
    # print(corr_left,corr_right)
    corr_cnt = bit.sum(corr_right)-bit.sum(corr_left)
    if corr_cnt*a >= h:
        continue
    else:
        rest = h-corr_cnt*a
        sup_cnt = (rest + (a - 1)) // a
        bit.add(corr_right,sup_cnt)
        ans += sup_cnt
    # print(ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, d, a = map(int, input().split())
M = []
total_hp = 0
for i in range(n):
  M.append(list(map(int, input().split())))
M.sort(key=lambda pos: pos[0])
X = [x[0] for x in M]
H = [x[1] for x in M]

import math
import bisect
counter = 0
for i in range(n):
#  print(M)
  target_hp = H[i]
  if target_hp <= 0:
    n += 1
    continue
  else:
    target_x = X[i]
    bom_x = target_x + d
    bom_n = math.ceil(target_hp / a)
    #爆破範囲
    left = bom_x - d
    right = bom_x + d
    #ダメージ範囲
    id_left = bisect.bisect_left(X, left)
    id_right = bisect.bisect_right(X, right)
    for j in range(id_left, id_right):
      H[j] -= bom_n * a

    n += 1
    counter += bom_n
#    print(n, target_x, counter)
print(counter)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
import bisect
N, D, A = map(int, input().split())
monsters = []
for i in range(N):
    row = list(map(int, input().split()))
    monsters.append(row)
xh = np.array(monsters)
xh = xh[xh[:,0].argsort()]

ans = 0

for i in range(N):
    if xh[i][1] <= 0:
        # print("pass ", i)
        continue
    else:
        xi, hi = xh[i]
        # print(i,xi,hi)

        # xi + 2Dで爆撃
        # xj <= xi + 2*D なる最大のjを求める
        # j = index_right - 1
        index_right = bisect.bisect_right(xh[:,0], xi+2*D)
        # print("ir",index_right)
        # 爆撃回数 d
        d = math.ceil(hi/A) 
        # print("爆撃回数 d", d)
        # i ~ jまで -dA
        # xh[i:j+1,1] -= d*A
        xh[i:index_right,1] -= d*A
        # print(xh)
        ans += d

print(ans)

Submission status: Time Limit Exceeded

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

X = [XH[i][0] for i in range(N)]

ans = 0
for i in range(N):
    if XH[i][1] > 0:
        n_bomb = -(-XH[i][1]//A)
        ans += n_bomb
        j = i
        while j <= N-1 and XH[j][0] <= XH[i][0] + 2*D:
            XH[j][1] -= n_bomb * A
            j += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_left,bisect_right

N,D,A = II()
X,H = Line(N,2)

#Binary Indexed Tree（区間加算）
#1-indexed
class Range_BIT():
    def __init__(self, N):
        self.size = N
        self.data0 = [0]*(N+1)
        self.data1 = [0]*(N+1)

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

    # 区間[l,r)にxを加算
    def add(self, 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 _get(self, data, k):
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s

    # 区間[l,r)の和を求める
    def query(self, 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)

#インデックス付きソート
#(index,value)の順に格納
from operator import itemgetter
def index_sort(A):
    return sorted(enumerate(A),key=itemgetter(1))

num = [math.ceil(H[i]/A) for i in range(N)]
temp = index_sort(X)

X2 = [temp[i][1] for i in range(N)]
index = [temp[i][0] for i in range(N)]
num = [num[i] for i in index]

bit = Range_BIT(N)
for i in range(1,N+1):
    bit.add(i,i+1,num[i-1])


ans = 0
for i in range(1,N+1):
    if bit.query(i,i+1)<=0:
        continue
    p = bisect_right(X2,X2[i-1]+2*D)
    c = bit.query(i,i+1)
    bit.add(i,p+1,-c)
    ans += c

print(ans)

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
end = len(mons)-1
mons.append([-d-1,0])  # for conv
while end >= 0:
    right, att = mons[end]
    if att <= 0:
        end -= 1
        continue
    ans += att
    bar = right - d
    j = end-1
    while mons[j][0] >= bar:
        mons[j][1] -= att
        j -= 1
    end -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,d,a=map(int,input().split())
s=sorted([list(map(int,input().split()))+[1]for i in range(n)])
c=0
for i in range(n):
    if s[i][2]:
        s[i][2]=0
        t=((s[i][1]-1)//a+1)
        c+=t
        for j in range(i+1,n):
            if s[j][0]<=s[i][0]+2*d:
                s[j][1]-=t*a
                if s[j][1]<=0:
                    s[j][2]=1
print(c)

Submission status: Time Limit Exceeded

Solution code:
import collections
import math
import operator as op
from functools import reduce
import numpy as np
import math
import bisect
import heapq


MOD = 1000000007


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd(a, b)


def get_inputs(cast_func=None):
    if cast_func is None:
        return input().split()
    else:
        return list(map(cast_func, input().split()))


def get_input(cast_func=None):
    if cast_func is None:
        return input()
    else:
        return cast_func(input())


def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


def main():
    N, D, A = get_inputs(int)
    X = np.empty(N, dtype=np.int32)
    H = np.empty(N, dtype=np.int32)
    for i in range(N):
        x, h = get_inputs(int)
        X[i] = x
        H[i] = h
    idx = np.argsort(X)
    X = X[idx]
    H = H[idx]

    cnt = 0
    head = 0
    while head < N:
        if H[head] <= 0:
            head += 1
            continue
        pos = X[head] + D
        _cnt = math.ceil(H[head] / A)
        dmg = _cnt * A
        i = head
        while i < N and X[i] <= pos + D:
            H[i] -= dmg
            i += 1

        cnt += _cnt
        head += 1

    print(cnt)


if __name__ == '__main__':
    main()

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 heapq

N, D, A = map(int, readline().split())
m = map(int,read().split())
XH = list(zip(m,m))
heapq.heapify(XH)
width = 2*D

ans = 0
while len(XH) != 0:
  xh_min = heapq.heappop(XH)
  # left + D の位置で攻撃する
  left = xh_min[0]
  right = left + width
  nAttack = (xh_min[1] + A - 1) // A
  ans += nAttack
  damage = nAttack * A
  target = []
  while len(XH) != 0:
    xh = heapq.heappop(XH)
    if xh[0] <= right:
      if xh[1] > damage:
        target.append(xh)
    else:
      heapq.heappush(XH, xh)
      break
  for t in target:
    heapq.heappush(XH, (t[0], t[1] - damage))
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,d,a = map(int,input().split())
    l = [list(map(int,input().split())) for i in range(n)]
    l.sort()
    count = 0
    import math
    import bisect
    i = 0
    l1 = []

    while i < n:
        sn = i
        s = l[i][0]
        mi = math.ceil(l[i][1]/a)
        count += mi
        l1 =[]
        while i < n and l[i][0] <= s+2*d:
            
            l[i][1] -= mi*a
            if l[i][1] > 0:
                l1.append(i)
            i += 1
            
        if len(l1) > 0:
            i = l1[0]
        else:
            if i == n:
                print(count)
                exit()
    
if __name__ == "__main__":
    main()