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: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

def ceil(x,y):
  return (x-1)//y+1


def solve_binary(mid,k):
    return k < XH[mid][0]

def binary_search(s,n,k):
    ok=n
    ng=s
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if solve_binary(mid,k):
            ok=mid
        else:
            ng=mid
    return ok

n,D,A=map(int,input().split())
XH=[tuple(map(int,input().split())) for i in range(n)]
XH.sort(key=lambda tup: tup[0])
XH.append((inf,0))
data=[0]*(n+1)
if D==0:
    for xi,hi in XH:
        count += hi
        # print(count)
    print(count)
    exit()
for i in range(n):
    xi,hi = XH[i]
    hi-=data[i]
    K=max(0,ceil(hi,A)*A); count += max(0,ceil(hi,A))
    data[i]+=K; data[binary_search(i,n,xi+2*D)]-=K
    data[i+1]+=data[i]
print(count)
# print(data)

Submission status: Wrong Answer

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

killed = 0
ans = 0
start = 0
nextstart = 0
while killed < N:
    x,h = XH[start]#左端の敵
    bonu = h#爆弾の回数
    hanni = x + 2*D
    XH[start][1] = 0
    killed += 1
    for m in range(start+1,N):
        x2,h2 = XH[m]
        if x2<=hanni and h2:
            XH[m][1] = max(0,h2-bonu)
            if h2<=bonu:killed+=1
            elif nextstart==start:#殺しきれなかった
                nextstart = m
        elif x2>hanni:break
    start = max(nextstart,start+1)
    ans += bonu
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n,d,a = m()

ppp = [0 for i in range(n)]

aaa = []
lll = []
rrr = []
co = 0
for i in range(n):
    p = l()
    aaa.append([p[0],-(-p[1]//a)])
aaa.sort()
for i in range(n):
    lll.append([aaa[i][0],aaa[i][0]+2*d])
c = 0
ll = 0
for i in range(n):
    on = aaa[i]
    for j in range(ll,n):
        if lll[j][1] < aaa[i][0]:
            c -= aaa[j][1]
        else:
            ll = j
            break
    if on[1] <= c:
        continue
    else:
        co += on[1]-c
        c += on[1]-c
        """
        for j in range(i+1,n):
            if aaa[j][0] <= lll[i][1]:
                aaa[j][1] -= on[1]
            else:
                break
        """
        

print(co)

Submission status: Wrong Answer

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

ans = 0
import queue
q=queue.Queue()


kaisuu = (xh[0][1] +a-1) // a
damege = kaisuu*a
ans += kaisuu
iti = xh[0][0] + 2*d
maedame = damege
for i in range(1,n):
    while(iti < xh[i][0]):
        damege -= maedame
        if q.empty():
            break
        iti,maidame = q.get()
    if xh[i][1] - damege <= 0:
        continue
    kaisuu = (xh[i][1] - damege +a-1) // a
    damege += kaisuu*a
    q.put((xh[i][1] + 2*d, damege))
    ans += kaisuu
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right, bisect_left
# instead of AVLTree
class BITbisect():
    def __init__(self, InputProbNumbers):
        # 座圧
        self.ind_to_co = [-10**18]
        self.co_to_ind = {}
        for ind, num in enumerate(sorted(list(set(InputProbNumbers)))):
            self.ind_to_co.append(num)
            self.co_to_ind[num] = ind+1
        self.max = len(self.co_to_ind)
        self.data = [0]*(self.max+1)
    
    def __str__(self):
        retList = []
        for i in range(1, self.max+1):
            x = self.ind_to_co[i]
            if self.count(x):
                c = self.count(x)
                for _ in range(c):
                    retList.append(x)
        return "[" + ", ".join([str(a) for a in retList]) + "]"
    
    def __getitem__(self, key):
        key += 1
        s = 0
        ind = 0
        l = self.max.bit_length()
        for i in reversed(range(l)):
            if ind + (1<<i) <= self.max:
                if s + self.data[ind+(1<<i)] < key:
                    s += self.data[ind+(1<<i)]
                    ind += (1<<i)
        if ind == self.max or key < 0:
            raise IndexError("BIT index out of range")
        return self.ind_to_co[ind+1]
    
    def __len__(self):
        return self._query_sum(self.max)
    
    def __contains__(self, num):
        if not num in self.co_to_ind:
            return False
        return self.count(num) > 0
    
    # 0からiまでの区間和
    # 左に進んでいく
    def _query_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # i番目の要素にxを足す
    # 上に登っていく
    def _add(self, i, x):
        while i <= self.max:
            self.data[i] += x
            i += i & -i
    
    def add(self, co, x):
        i = self.co_to_ind[co]
        while i > 0:
            self.data[i] += x
            i -= i & -i
    
    def now(self, x):
        i = self.co_to_ind[x]
        ret = 0
        while i <= self.max:
            ret += self.data[i]
            i += i & -i
        return ret
    
    # 値xを挿入
    def push(self, x):
        if not x in self.co_to_ind:
            raise KeyError("The pushing number didnt initialized")
        self._add(self.co_to_ind[x], 1)
            
    # 値xを削除
    def delete(self, x):
        if not x in self.co_to_ind:
            raise KeyError("The deleting number didnt initialized")
        if self.count(x) <= 0:
            raise ValueError("The deleting number doesnt exist")
        self._add(self.co_to_ind[x], -1)

    # 要素xの個数
    def count(self, x):
        return self._query_sum(self.co_to_ind[x]) - self._query_sum(self.co_to_ind[x]-1)
    
    # 値xを超える最低ind
    def bisect_right(self, x):
        if x in self.co_to_ind:
            i = self.co_to_ind[x]
        else:
            i = bisect_right(self.ind_to_co, x) - 1
        return self._query_sum(i)

    # 値xを下回る最低ind
    def bisect_left(self, x):
        if x in self.co_to_ind:
            i = self.co_to_ind[x]
        else:
            i = bisect_left(self.ind_to_co, x)
        if i == 1:
            return 0
        return self._query_sum(i-1)

import sys
input = sys.stdin.readline

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
if D == 0:
    ans = 0
    for x, h in XH:
        ans += (h+A-1)//A
else:
    XH.sort()
    Input = []
    for x, h in XH:
        Input.append(x)

    Input.sort()

    bit = BITbisect(Input)
    ans = 0
    for x, h in XH:
        now = bit.now(x)
        if now >= h: continue
        count = (h-now+A-1)//A
        ans += count
        ind = bisect_right(Input, x+2*D)
        if ind == N:
            nx = Input[-1]
        else:
            nx = Input[ind]
        bit.add(nx, A*count)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

n, d, a  = map(int,input().split())
x = []
h = []
for i in range(n):
    x_temp,h_temp = map(int,input().split())
    x.append(x_temp)
    h.append(h_temp)


print(h)
x = np.array(x, dtype=np.int64)
h = np.array(h, dtype=np.int64)
sort_ind = np.argsort(x)
x = x[sort_ind]
h = h[sort_ind]

ans = 0
for i in range(n):
    if (h[i] <= 0):
        continue
    at_num = ((h[i] -1 )// a) + 1
    ans += at_num
    h[i] -= at_num * a
    x_origin = x[i]
    while(True):
        i += 1
        if(i >= n):
            break
        if(x_origin + 2*d >= x[i]):
            h[i] -= at_num * a
        else:
            break

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
from numpy import array
from math import ceil

N,D,A = [int(zz) for zz in input().split()]
li = [[int(zz) for zz in input().split()] for _ in range(N)]
li.sort()

X = [i[0] for i in li]
H = array([i[1] for i in li])

ans = 0
for i in range(N):
    if H[i] > 0:
        rind = bisect_right(X,X[i]+2*D)
        dmg = ceil(H[i]/A)*A
        ans += ceil(H[i]/A)
        H[i:rind] -= H[i]
        
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n,d,a = m()

ppp = [0 for i in range(n)]

aaa = []
lll = []
rrr = []
co = 0
for i in range(n):
    p = l()
    aaa.append([p[0],-(-p[1]//a)])
aaa.sort()
for i in range(n):
    lll.append([aaa[i][0],aaa[i][0]+2*d])
c = 0
ll = 0
for i in range(n):
    on = aaa[i]
    for j in range(ll,n):
        if lll[j][1] < aaa[i][0]:
            c -= aaa[j][1]
        else:
            break
    if on[1] <= c:
        continue
    else:
        co += on[1]
        c += on[1]
        """
        for j in range(i+1,n):
            if aaa[j][0] <= lll[i][1]:
                aaa[j][1] -= on[1]
            else:
                break
        """
        

print(co)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_right
def main():
    N, D, A = map( int, input().split())
    XH = []
    X = []
    for _ in range(N):
        x, h = map( int, input().split())
        XH.append( (x, (h+(A-1))//A))
        X.append(x)
    XH.sort()
    X.sort()
    T = [0]*(N+1)
    j = 0
    now = 0
    ans = 0
    for i in range(N):
        x, h = XH[i]
        now -= T[i]
        if now >= h:
            continue
        else:
            T[ bisect_right(X,x+D*2)] = h-now
            ans += h - now
            now = h
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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()
    ans = 0
    for i in range(N):
        if B[i][1] <= 0:
            continue
        cnt = H // A if H % A == 0 else H // A + 1
        ans += cnt
        B[i][1] = 0
        for j in range(N):
            if B[j][0] <= B[i][0] + 2 * D:
                B[j][1] -= cnt * A
            else:
                break
    
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

ans = 0
import queue
q=queue.Queue()


kaisuu = (xh[0][1] +a-1) // a
damege = kaisuu*a
ans += kaisuu
iti = xh[0][0] + 2*d+1
maedame = damege
for i in range(1,n):
    while(iti < xh[i][0]):
        damege -= maedame
        if q.empty():
            break
        iti,maidame = q.get()
    if xh[i][1] - damege <= 0:
        continue
    kaisuu = (xh[i][1] - damege +a-1) // a
    damege += kaisuu*a
    q.put((xh[i][1] + 2*d+1, damege))
    ans += kaisuu
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

from bisect import bisect_left

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

XH.sort()
X = []
for x, h in XH :
  X.append(x)

# 添字が1から始まることに注意
class BinaryIndexedTree() :
  def __init__(self, N) :
    self.size = N
    self.tree = [0] * (N + 1)
      
  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

ret = 0
BIT = BinaryIndexedTree(N + 10)
for x, h in XH :
  a = bisect_left(X, x - D - 1) + 1
  b = bisect_left(X, x + D) + 1
  s = BIT.sum(b) - BIT.sum(a)
  if s >= h :
    continue
  
  cnt = (h - s + A - 1) // A
  ret += cnt
  BIT.add(b, cnt * A)

print(ret)

Submission status: Wrong Answer

Solution code:
from math import ceil

def resolve():
    N,D,A = (int(i) for i in input().split())
    XA=[[int(i) for i in input().split()] for j in range(N)]
    XA.sort()
    mn=0
    count=0
    while XA[-1][1]>0:
        pos=mn
        ucount=ceil(XA[mn][1]/A)
        count+=ucount
        dmg=ucount*A
        if ucount==0:
            continue
        while XA[pos][0]<=XA[mn][0]+2*D:
            XA[pos][1]=max(0,XA[pos][1]-dmg)
            pos+=1

            if pos==N:
                break
        mn+=1
    print(count)







if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    n,d,a = map(int,input().split())
    P = [list(map(int,input().split())) for i in range(n)]
    P2 = list(zip(*P))
    s = sum(P2[1])
    import math
    print(math.floor(s/(d+1)))
resolve()

Submission status: Wrong Answer

Solution code:
import bisect
import math

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)

now=0
turn=0

while now<n:
    swit=0
    pos=xhlist[now][0]+d
    atk=math.ceil(xhlist[now][1]/a)*a
    hani=bisect.bisect_right(xlist, pos+d)
    tasu=0
    turn+=atk//a
    for i in range(hani-now):
        if now+i<n:
            xhlist[now+i][1]-=atk
            if xhlist[now+i][1]<=0 and swit==0:
                tasu+=1
            elif swit==0:
                swit=1
            else:
                break
    now+=tasu
    
print(turn)

Submission status: Wrong Answer

Solution code:
N,D,A=map(int,input().split())
XH=sorted([list(map(int,input().split())) for i in range(N)])
l,r=0,0
a=0
dp=0
dm=[0]*(N+1)
while l<N:
    while r<N and XH[r][0]<=XH[l][0]+2*D:
        r+=1
    dp+=dm[l]
    x=max(0,-(-XH[l][1]+dp)//A)
    a+=x
    dp+=x*A
    dm[r]-=x*A
    l+=1
print(a)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

def ceil(x,y):
  return (x-1)//y+1


def solve_binary(mid,k):
    return k < XH[mid][0]

def binary_search(s,n,k):
    ok=n
    ng=s
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if solve_binary(mid,k):
            ok=mid
        else:
            ng=mid
    return ok

n,D,A=map(int,input().split())
XH=[tuple(map(int,input().split())) for i in range(n)]
XH.sort(key=lambda tup: tup[0])
XH.append((inf,0))
data=[0]*(n+1)
if D==0:
    for xi,hi in XH:
        count += hi
        # print(count)
    print(count)
    exit()
for i in range(n):
    xi,hi = XH[i]
    hi-=data[i]
    K=ceil(hi,A)*A; count += ceil(hi,A)
    data[i]+=K; data[binary_search(i,n,xi+2*D)]-=K
    data[i+1]+=data[i]
print(count)
# print(data)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

from bisect import bisect_left, bisect_right

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

XH.sort()
X = []
for x, h in XH :
  X.append(x)

# 添字が1から始まることに注意
class BinaryIndexedTree() :
  def __init__(self, N) :
    self.size = N
    self.tree = [0] * (N + 1)
      
  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

ret = 0
BIT = BinaryIndexedTree(N + 10)
for x, h in XH :
  x += 1
  a = bisect_left(X, x - D - 1)
  b = bisect_right(X, x + D)
  s = BIT.sum(b) - BIT.sum(a)
  if s >= h :
    continue
  
  cnt = (h - s + A - 1) // A
  ret += cnt
  BIT.add(b, cnt * A)

print(ret)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
n,d,a=[int(j) for j in input().split()]
xh=[[int(j) for j in input().split()] for i in range(n)]
xh.sort()
xh=np.array(xh)
ans=0
for i in range(n):
    if xh[i][1]>0:
        k=math.ceil(xh[i][1]/a)
        ind=np.searchsorted(xh[:,0],xh[i][0]+2*d+1,side="right")-1
        xh[i:ind+1,1]-=a*k
        ans+=k

print(ans)

Submission status: Wrong Answer

Solution code:

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
XH.sort()
X = [XH[i][0] for i in range(N)]
ans = 0
res = 0
from bisect import bisect
cnt = [0]*(N+1)
for i in range(N):
    x, h = XH[i]
    res-=cnt[i]
    h-=res
    if h<=0:
        continue
    n = ((h-1)//A+1)
    j = bisect(X, x+D*2+1)
    cnt[j]+=n*A
    res+= n*A
    ans+=n
print(ans)

Submission status: Wrong Answer

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

ans = 0
import queue
q=queue.Queue()


kaisuu = (xh[0][1] +a-1) // a
damege = kaisuu*a
q.put((xh[0][1] + 2*d+1, damege))
ans += kaisuu
iti = xh[0][1] + 2*d+1
for i in range(1,n):
    while(iti < xh[i][0]):
        iti,maidame = q.get()
        damege -=maidame
    if xh[i][1] - damege <= 0:
        continue
    kaisuu = (xh[i][1] - damege +a-1) // a
    damege += kaisuu*a
    q.put((xh[i][1] + 2*d+1, damege))
    ans += kaisuu
print(ans)

Submission status: Wrong Answer

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

ans = 0
i = 0
while True:
    alive = True
    for j in range(i, N):
        x, h = XH[j]
        if h-damage[j] <= 0:
            continue
        i = j
        pos = x
        explode = (h + A - 1) // A
        break
    else:
        alive = False
        break

    if not alive:
        break

    for j in range(i, N):
        x, _ = XH[j]
        if x <= pos+2 * D:
            damage[j] += explode * A
        else:
            break
    ans += explode

print(ans)

Submission status: Wrong Answer

Solution code:
n, d, a = map(int, input().split())
d *= 2
l = [list(map(int, input().split())) for _ in range(n)]
l.sort()
x = [0] * n
h = [0] * n
for i in range(n):
    x[i], h[i] = l[i]
t = 0
r = 1
ans = 0
for l in range(n):
    t = max((h[l] - 1) // a + 1, 0)
    ans += t
    h[l] = 0
    while r < n and x[r] - x[l] <= d:
        h[r] -= t * a
        r += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N, D, A = map(int, input().split())
a = []
b = []
res = 0
for _ in range(N):
  x, h = map(int, input().split())
  a.append([x, h])
  b.append(x)
a.sort(key = lambda x: x[0])
b.sort()
imos = [0] * (N + 2)
for i in range(N):
  a[i][1] += imos[i]
  imos[i + 1] += imos[i]
  if a[i][1] <= 0: continue
  l = a[i][0]
  r = a[i][0] + 2 * D
  t = bl(b, r)
  x = -(-a[i][1] // A)
  imos[i + 1] -= A * x
  imos[t + 1] += A * x
  a[i][1] = 0
  res += x
  #print(a, imos)
#print(imos)
#print(a)
print(res)

"""
AtCoderレートで全ての優劣が決定される異世界ベラルーシ。
ここでは他世界からの転生者は「旅行者 - tourist -」と呼ばれる。

不幸な交通事故から、社長 高橋直小はベラルーシに異世界転生してしまった。
"""

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


class BinaryIndexedTree:
  def __init__(self,N):
      self.N = N
      self.bit = [0]*(self.N+1)

  def add(self,a,w):
    x = a
    while x <= self.N:
      self.bit[x] += w
      x += x & -x

  def sum(self,a):
    if a <= 0:
        return 0
    tmp = 0
    x = a
    while x > 0:
      tmp += self.bit[x]
      x -= x & -x
      return tmp

N,D,A = inpl()
BIT = BinaryIndexedTree(N+1)

XHs = [inpl() for _ in range(N)]
XHs.sort()
xx = [X for X,H in XHs]
hh = [H for X,H in XHs]

ans = 0
all = 0
for i,(x,h) in enumerate(XHs):
    d = all - BIT.sum(i)
    n = max(0,(h-d*A-1)//A + 1)
    ans += n
    r = bisect.bisect_right(xx,x+2*D)
    BIT.add(r, n)
    all += n


print(ans)

Submission status: Wrong Answer

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

i=0
out=0
while i<N:
  if XH[i][0]<=0:
    i+=1
    continue
  tmp=XH[i][1]//A
  if XH[i][1]%A>0:
    tmp+=1
  
  out+=tmp
  j=i+1
  while j<N and XH[j][0]<=XH[i][0]+2*D:
    XH[j][1]-=tmp*A
    j+=1
  i+=1

print(out)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

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

for i in range(N):
    tX,tH=map(int,input().split())
    if tX in monster:
        monster[tX]=max(monster[tX],tH)
    else:
        monster[tX]=tH

monster_key=list(monster.keys())
monster_key.sort()

count=0

for x in monster_key:
    tmp=x+D
    while monster[x]>0:
        print(monster,tmp)
        for k in monster:
            if k<=tmp+D:
                monster[k]-=A
        count+=1

print(count)

Submission status: Wrong Answer

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
memo = [0]*N
t = 0
s = 0
while t<N:
    if XH[t][1]<0:
        t+=1
        continue
    X = XH[t][0]
    L = X
    H = XH[t][1]
    B = H//A+1*(H%A!=0)
    output += B
    while (t<N)and(XH[t][0]<=L+2*D):
        XH[t][1]+= -1*B*A
        if (XH[t][1]>0)and(s==0):
            s=t
        t+=1
    s=0

print(output)

Submission status: Wrong Answer

Solution code:
import math
N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for i in range(N)]
XH.sort(key=lambda x: x[0])
left = D
flag = True
count = 0
ans = 0
for i in range(N):
    # 爆発させるとき
    if i == 0 or pos + D < XH[i][0]:
        pos = XH[i][0] + D
        count = math.ceil(XH[i][1] / A)
        XH[i][1] = 0
        ans += count
    else:
        XH[i][1] -= count*A
        if XH[i][1] > 0:
            pos = XH[i][0] + D
            count = math.ceil(XH[i][1] / A)
            XH[i][1] = 0
            ans += count
        else:
            continue

print(ans)

Submission status: Wrong Answer

Solution code:
n, d, a = [int(i) for i in input().split()]
xh = [[int(i) for i in input().split()] for _ in range(n)]
xh.sort()
da = [0] * n
r = [0] * n
ru=0

ans = 0
j=0
for i in range(n):
    da[i]+=ru
    if xh[i][0] > da[i]:
        up = (xh[i][1] - da[i]) // a
        if (xh[i][1] - da[i]) % a != 0:
            up += 1
        ans+=up
        up *= a
        da[i] += up
        ru+=up
        
        while j!=n-1 and xh[j+1][0] <= xh[i][0] + 2 * d:
            j += 1
        r[j]+=up
    
    ru-=r[i]
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for i in range(N)]
XH.sort(key=lambda x: x[0])
left = D
flag = True
count = 0
ans = 0
for i in range(N):
    print(count)
    # 爆発させるとき
    if i == 0 or pos + D < XH[i][0]:
        pos = XH[i][0] + D
        count = math.ceil(XH[i][1] / A)
        XH[i][1] = 0
        ans += count
    else:
        XH[i][1] -= count*A
        if XH[i][1] > 0:
            pos = XH[i][0] + D
            count = math.ceil(XH[i][1] / A)
            XH[i][1] = 0
            ans += count
        else:
            continue

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect
def main():
    N, D, A = map( int, input().split())
    XH = []
    X = []
    for _ in range(N):
        x, h = map( int, input().split())
        XH.append( (x, (h+(A-1))//A))
        X.append(x)
    XH.sort()
    X.sort()
    T = [0]*(N+1)
    j = 0
    now = 0
    ans = 0
    tail = X[-1]
    for i in range(N):
        x, h = XH[i]
        now -= T[i]
        if now >= h:
            continue
        else:
            T[ bisect(X,x+D*2)] = h-now
            ans += h - now
            now = h
    print(ans)
            
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left,bisect_right
n,d,a=map(int,input().split())
xh=[list(map(int,input().split()))for _ in range(n)]
xh.sort()
x=[]
h=[]
for xx,hh in xh:
  x.append(xx)
  h.append(hh)
imos=[0]*(n+1)
mi=0
ans=0
for i in range(n):
  mi-=imos[i]
  h[i]=max(h[i]-mi,0)
  atk=0--h[i]//a
  ans+=atk
  mi+=atk
  point=x[i]+d*2
  index=bisect_right(x,point)
  imos[index]+=atk
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, D, A = map(int, input().split())
X = []
for _ in range(N):
    x, h = map(int, input().split())
    X.append((x, h))
X = sorted(X)[::-1]
L = [(1<<30, 0)]

ans = 0
k = 0
while X:
    if X[-1][0] <= L[-1][0]:
        x, h = X.pop()
        h = max(h - k * A, 0)
        a = (h + A - 1) // A
        ans += a
        k += a
        L.append((x + 2 * D, a))
    else:
        x, a = L.pop()
        k -= a

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    readline = sys.stdin.buffer.readline

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

    l = [0]*(n+1)
    ans = 0
    for i in range(n):
        if xh[i][1] <= 0:
            continue 
        c = -(-xh[i][1]//a)
        ans += c
        for j in range(i+1, n):
            if xh[j][0] <= xh[i][0] + d*2:
                xh[j][1] -= c*a
            else:
                break
    print(ans)

main()

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)])

l = [0]*(n+1)
ans = 0
for i in range(n):
    if xh[i][1] <= 0:
        continue 
    c = -(-xh[i][1]//a)
    ans += c
    for j in range(i+1, n):
        if xh[j][0] <= xh[i][0] + d*2:
            xh[j][1] -= c*a
        else:
            break
print(ans)

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 decimal import *
def main():
    N, D, A = MI()
    Enemy = defaultdict()
    Enemy_ran = []
    for i in range(N):
        x, h = MI()
        Enemy[x] = h
        Enemy_ran.append(x)
    Enemy_ran.sort()
    cnt = 0
    dam = [0] * N
    for i in range(N):
        x = Enemy_ran[i]
        HP = Enemy[x] - dam[i]
        if HP <= 0:
            continue
        else:
            ata = math.ceil(Decimal(Enemy[x] - dam[i]) / Decimal(A))
            cnt += ata
            ran = x + 2 * D
            y = bisect.bisect_right(Enemy_ran, ran)
            for j in range(i + 1, y):
                dam[j] += ata * A


    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])
    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
            dam = ata * A
            for j in range(i + 1, N):
                if Enemy[j][0] <= ran:
                    Enemy[j][1] -= dam
                else:
                    break
    print(cnt)


if __name__ == "__main__":
    main()