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.

Solution (Python):
from collections import deque
N, D, A = map(int, input().split())
ls = []
for i in range(N):
  x,h = map(int, input().split())
  h = h//A if h%A==0 else h//A+1
  ls += [(x,h)]
ls.sort(key=lambda x:x[0])
deq = deque([])
ans = 0
acc = 0
for i in range(N):
  x, h = ls[i]
  while deq and deq[0][0]<x:
    y, d = deq.popleft()
    acc -= d
  n = max(0,h-acc)
  ans += n
  acc += n
  if n:
    deq += [(x+2*D,n)]
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
import math


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

XH = []
for _ in range(n):
    x, h = map(int, input().split())
    XH.append((x, h))
XH.sort()

answer = 0
damage = 0
QUEUE = deque()
for x, h in XH:
    if QUEUE:
        while x > QUEUE[0][0]:
            damage -= QUEUE[0][1]
            QUEUE.popleft()
            if not QUEUE:
                break
    h -= damage
    if h <= 0:
        continue
    bomb = math.ceil(h / a)
    QUEUE.append((x + 2 * d, a * bomb))
    damage += a * bomb
    answer += bomb

print(answer)

Solution (Python):
N, D, A = map(int, input().split())
XH = sorted([tuple(map(int, input().split())) for _ in range(N)])
ans, r, S, R = 0, 0, [0] * (N + 2), []
for l in range(N):
    while r + 1 < N and XH[r + 1][0] - XH[l][0] <= 2 * D:
        r += 1
    S[l + 1] += S[l]
    bomb = (max(XH[l][1] - S[l + 1], 0) + A - 1) // A
    ans += bomb
    S[l + 1] += bomb * A
    S[r + 1 + 1] -= bomb * A
    R.append(r)
print(ans)

Solution (Python):
from math import ceil
from collections import deque

N, D, H = map(int, input().split())
Monsters = sorted([list(map(int, input().split())) for i in range(N)])
Monsters = [[x, ceil(h/H)] for x, h in Monsters]

ans = 0
acc = 0
deq = deque([])

for x, h in Monsters:
  while deq and x>deq[0][0]:
    lim, dam = deq.popleft()
    acc -= dam
  c = max(0, h-acc)
  ans += c
  acc += c
  if c:
    deq += [(x+2*D, c)]
    
print(ans)

Solution (Python):
from collections import deque

def updiv(a,b):
    if a % b == 0:
        return a // b
    else:
        return a // b + 1

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

XH = []

for i in range(N):

    x,h = map(int,input().split())
    XH.append([x,h])

XH.sort()

q = deque([])
qs = 0
ans = 0

for i in range(N):

    X = XH[i][0]
    H = XH[i][1]

 
    while len(q) > 0 and q[0][0] < X-D:
        po = q.popleft()
        qs -= po[1] * A

    if H - qs <= 0:
        continue
        
    else:
        pl = updiv(H-qs,A)
        qs += pl * A
        ans += pl
        q.append([X+D,pl])

print (ans)

Solution (Python):
from collections import deque


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

    XHN = []
    for _ in range(N):
        X, H = map(int, input().split())
        XHN.append([X, H, X + 2 * D])

    XHN.sort()

    q = deque()
    acc_damege = 0
    ans = 0
    for i in range(N):
        if 0 < XHN[i][1]:
            X, H, bomb_p = XHN[i]

            while q:
                acc_x, acc_d = q[0]
                if acc_x < X:
                    acc_damege -= acc_d
                    del q[0]
                else:
                    break

            H -= acc_damege

            if 0 < H:
                attack_count = H // -A * -1
                damege = A * attack_count
                ans += attack_count
                XHN[i][1] -= damege

                acc_damege += damege
                q.append((bomb_p, damege))

    print(ans)


main()

Solution (Python):
import sys
input = sys.stdin.readline

from heapq import heapify, heappop, heappush

N, D, A = map(int, input().split())
XH = []
XH_append = XH.append
for _ in range(N):
    x, h = map(int, input().split())
    XH_append((x, 0, h))

heapify(XH)
atk_cnt = 0
ans = 0
while XH:
    x, t, h = heappop(XH)
    if t == 0: 
        if atk_cnt * A >= h:
            continue
        
        remain = h - atk_cnt * A 
        new_atk = (remain + A - 1) // A
        heappush(XH, (x + 2 * D, 1, new_atk))

        ans += new_atk
        atk_cnt += new_atk
    
    else:
        atk_cnt -= h

print (ans)

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,d,a = mi()
lis = []
for  i in range(n):
    x,h = mi()
    h = (h + a - 1) // a
    lis.append([x,h])

lis.sort()
dis = []
hp = []
for i in range(n):
    dis.append(lis[i][0])
    hp.append(lis[i][1])

from collections import deque
hiku = deque()
sums = hp[0]
ans = hp[0]
hiku.append([dis[0] + 2 * d,hp[0]])
imadis,imahp = hiku.popleft()
for i in range(1,n):
    while True:
        if dis[i] <= imadis:
            break
        else:
            sums -= imahp
            imahp = 0
            if hiku:
                imadis,imahp = hiku.popleft()
            else:
                break
    diff = hp[i] - sums
    if diff > 0:
        ans += diff
        sums += diff
        hiku.append([dis[i] + 2 * d,diff])

print(ans)

Solution (Python):
from bisect import bisect_right

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*(N+2)
b = 0
for i, (x, h) in enumerate(xh, 1):
  ds[i] += ds[i-1]
  d = ds[i]
  if d>=h:
    continue
  h -= d
  times = h//A if h%A==0 else h//A+1
  ds[i] += times*A
  ds[bisect_right(xh, [x+2*D, float('inf')])+1] -= times*A
  b += times
print(b)

Solution (Python):
from math import ceil
from bisect import bisect_right

n, d, a = map(int, input().split())
l = []
l2 = []
l3 = []
l4 = [0 for i in range(n+1)]
l5 = [0 for i in range(n+1)]
ans = 0
for i in range(n):
  x, h = map(int, input().split())
  l.append([x, h])
  l2.append(x + 2 * d)
  l3.append(x)
l.sort(key=lambda x: x[0])
l2.sort()
l3.sort()
for i in range(n):
  cnt = ceil((l[i][1] - l4[i] * a) / a)
  if cnt > 0:
    ans += cnt
    ind = bisect_right(l3, l2[i])
    l5[ind] += cnt
    l4[i] += cnt
  l4[i+1] = l4[i] - l5[i+1]
    
print(ans)

Solution (Python):
from math import ceil
from bisect import bisect_right
n, d, a = (int(x) for x in input().split())
xh = []
for _ in range(n):
    x, h = (int(x) for x in input().split())
    xh.append([x, h])
xh = sorted(xh, key=lambda x: x[0])
cnt = 0
dmg = [0] * (n + 1)
for i, (x, h) in enumerate(xh):
    dmg[i] += dmg[i - 1]
    h -= dmg[i]
    if h <= 0:
        continue
    num = ceil(h / a)
    dmg[i] += num * a
    idx = bisect_right(xh, [x + 2 * d, float('inf')])
    dmg[idx] -= num * a
    cnt += num
print(cnt)

Solution (Python):
import heapq

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

for _ in range(n):
    x, h = map(int, input().split())
    bom.append([x, h])

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

ans = 0
tot = 0
q = []
for x, h in bom:
    while q:
        if q[0][0] >= x: break
        else:
            _, t = heapq.heappop(q)
            tot -= t
    
    r = max((h-tot-1)//a + 1, 0)
    ans += r
    tot += r * a
    heapq.heappush(q, (x+2*d, r*a))

print(ans)

Solution (Python):

import math
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 = [i[0] for i in xh]
h = [i[1] for i in xh]


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

for i in range(len(x)):
    damage[i] += damage[i-1]
    h[i] -= damage[i]
    if h[i]<=0: continue
    h_int =  math.ceil(h[i]/A)
    cnt+=h_int
    damage[i]+=h_int*A
    r=bisect(x,x[i]+2*D)
    
    damage[r]-= A*h_int
    

print(int(cnt))

Solution (Python):

import math
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 = [i[0] for i in xh]
h = [i[1] for i in xh]


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

for i in range(len(x)):
    damage[i] += damage[i-1]
    h[i] -= damage[i]
    if h[i]<=0: continue
    h_int =  math.ceil(h[i]/A)
    cnt+=h_int
    damage[i]+=h_int*A
    r=bisect(x,x[i]+2*D)
    
    damage[r]-= A*h_int
    

print(int(cnt))

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

D = True

pos = []
pos1 = []

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

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

bombs = 0
damage = 0
y, z = 0, 0


while y < n:
	x0 = pos[y][0]
	try:
		x1 = pos1[z][0]
	except IndexError:
		x1 = 1e16
	if x0 <= x1:
		health = pos[y][1]
		health -= damage
		number = max(0, (health-1) // a + 1)
		bombs += number
		damage += number*a
		pos1.append((x0+2*d, number*a))
		y+=1
	else:
		damage -= pos1[z][1]
		z += 1
	

print(bombs)

Solution (Python):
from operator import itemgetter
import bisect
N, D, A = map(int, input().split())
enemies = sorted([list(map(int, input().split())) for i in range(N)], key=itemgetter(0))
d_enemy = [enemy[0] for enemy in enemies]
b_left = bisect.bisect_left
logs = []
logs_S = [0, ]
ans = 0
for i, enemy in enumerate(enemies):
    X, hp = enemy

    start_i = b_left(logs, X-2*D)
    count = logs_S[-1] - logs_S[start_i]

    hp -= count * A
    if hp > 0:
        attack_num = (hp + A-1) // A
        logs.append(X)
        logs_S.append(logs_S[-1]+attack_num)
        ans += attack_num
print(ans)

Solution (Python):
import sys
from bisect import bisect_right
from operator import itemgetter

read = sys.stdin.read

N, D, A, *XH = map(int, read().split())
XH = sorted(zip(*[iter(XH)] * 2), key=itemgetter(0))
D *= 2
X = [i for i, _ in XH]

damages = [0] * (N + 2)
answer = 0

for i, (x, h) in enumerate(XH, 1):
    damages[i] += damages[i - 1]
    if damages[i] >= h:
        continue

    h -= damages[i]
    cnt = (h + A - 1) // A
    answer += cnt
    damage = A * cnt
    damages[i] += damage
    damages[bisect_right(X, x + D) + 1] -= damage

print(answer)

Solution (Python):
n,d,a = map(int,input().split())
attack = [0 for _ in range(n)]
event = []
for i in range(n):
  x,h = map(int,input().split())
  h = (h-1)//a+1
  event.append([x-d,0,h,i])
  event.append([x+d,1,h,i])
event.sort()

ans = 0
now = 0
for j in range(2*n):
  x,m,h,i = event[j]
  if m == 0:
    if h > now:
      attack[i] += h-now
      ans += h-now
      now = h
  else:
    now -= attack[i]
print(ans)

Solution (Python):
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


import heapq
def main():
    N, D, A = read_values()
    M = [read_list() for _ in range(N)]
    M.sort(key=lambda l: l[0])
    Q = []

    F = 0
    res = 0
    for x, h in M:
        while Q:
            if Q[0][0] >= x:
                break
            else:
                _, f = heapq.heappop(Q)
                F -= f
        R = max((h - F - 1) // A + 1, 0)
        res += R
        F += R * A
        heapq.heappush(Q, (x + 2 * D, R * A))

    print(res)
       

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque


def main():
    N, D, A = map(int, input().split())
    enemies = [None] * N
    for i in range(N):
        enemies[i] = tuple(map(int, input().split()))
    enemies.sort()
    q = deque()
    cur = 0
    ans = 0
    for x, h in enemies:
        while len(q) and q[0][0] < x:
            cur -= q.popleft()[1]
        remain = max(h - cur * A, 0)
        tmp = -(-remain//A)
        q.append((x + 2 * D, tmp))
        ans += tmp
        cur += tmp
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
from bisect import bisect_right

n, d, a = map(int, input().split())
xh = [tuple(map(int, input().split())) for _ in range(n)]
xh.sort()
x, h = zip(*xh)
h = list(map(lambda x: -(-x//a), h))

s = [0] * (n+1)
ans = 0

for i in range(n):
    add = max(0, h[i] - s[i])
    j = bisect_right(x, x[i]+d*2)
    if j < n: s[j] -= add
    s[i] += add
    ans += add
    s[i+1] += s[i]

print(ans)

Solution (Python):
from  bisect import bisect

n,d,a=map(int,input().split())
monster=[list(map(int,input().split())) for i in range(n)]
monster.sort(key=lambda i:i[0])
r=[monster[i][0] for i in range(n)]
hp=[monster[i][1] for i  in range(n)]


d=2*d
i,ans,damages=0,0,[0]*n
while i<n:
  if i>0:
    damages[i]+=damages[i-1]
    s=hp[i]+damages[i]
  else:
    s=hp[i]
  if s>0:
    cnt=(s+a-1)//a
    ans+=cnt
    
    damage=cnt*a
    damages[i]-=damage
    zone=bisect(r,r[i]+d)
    if zone<n:
      damages[zone]+=damage 
  i+=1
  
  
print(ans)

Solution (Python):
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][0] = x
  l[i][1] = h
  
l.sort()
from collections import deque
d = 2*d
q = deque([])
total = 0

ans = 0
for i in range(n):
  x = l[i][0]
  h = l[i][1]
  if q:
    while q[0][0] < x:
      total -= q[0][1]
      q.popleft()
      if not q:
        break
  h -= total
  if h > 0:
    num = (h+a-1)//a
    ans += num
    damage = num*a
    total += damage
    q.append([x+d, damage])

print(ans)

Solution (Python):
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][0] = x
  l[i][1] = h
  
l.sort()
from collections import deque
d = 2*d
q = deque([])
total = 0

ans = 0
for i in range(n):
  x = l[i][0]
  h = l[i][1]
  if q:
    while q[0][0] < x:
      total -= q[0][1]
      q.popleft()
      if not q:
        break
  h -= total
  if h > 0:
    num = (h+a-1)//a
    ans += num
    damage = num*a
    total += damage
    q.append([x+d, damage])

print(ans)

Solution (Python):
import sys
from operator import itemgetter
from collections import deque


def solve():
    N, D, A = map(int, sys.stdin.readline().split())
    m = map(int, sys.stdin.read().split())
    XH = sorted(list(zip(m, m)), key=itemgetter(0))
    H = deque()
    X = deque()
    h_popleft = H.popleft
    x_popleft = X.popleft
    h_append = H.append
    x_append = X.append
    count = 0
    num = 0
    for x, h in XH:
        while X and X[0] < x:
            x_popleft()
            num -= (h_popleft() + (A - 1)) // A
        h -= A * num
        if h > 0:
            count += (h + (A - 1)) // A
            x_append(x + D*2)
            h_append(h)
            num += (h + (A - 1)) // A
    return count


if __name__ == '__main__':
    answer = solve()
    print(answer)

Solution (Python):
import sys
import bisect
from math import ceil
from itertools import accumulate
n, d, a = [int(i) for i in sys.stdin.readline().split()]
monsters = []
max_x = 0
for i in range(n):
    x, h = [int(i) for i in sys.stdin.readline().split()]
    max_x = max(x, max_x)
    monsters.append([x, h])
monsters.sort(key=lambda x:x[0])
x, h = zip(*monsters)
x_ls = []
for i, (_x, _h) in enumerate(zip(x, h)):
    ind = bisect.bisect_right(x, _x + 2 * d)
    x_ls.append([i, ind, _h])

h = list(h) + [0]
ls = [0 for i in range(n+1)]
cur = 0
res = 0
for i, ind, _h in x_ls:
    if h[i] > 0:
        cur -= ls[i]
    h[i] -= cur
    if h[i] > 0:
        hoge = ceil(h[i] / a)
        res += hoge
        cur += hoge * a
        ls[ind] += hoge * a
print(res)

Solution (Python):
from collections import deque
N,D,A = map(int, input().split())
ps = []
def ceil(a,b):
    return -(-a//b)

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

ps.sort()
damage = 0
cnt = 0
q = deque([])
for x,h in ps:
    while len(q) > 0 and q[0][0] < x:
        
        _, d = q.popleft()
        damage -= d
    
    h_rest = h - damage
    if h_rest <= 0: continue
    num = ceil(h_rest, A)
    damage += num * A
    cnt += num
    r = x + 2*D
    q.append((r,num*A))
print(int(cnt))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,d,a = LI()
    xh = sorted([LI() for _ in range(n)])
    r = 0
    k = 0
    t = []
    ti = 0
    for x,h in xh:
        while len(t) > ti and t[ti][0] < x:
            k -= t[ti][1]
            ti += 1
        h -= k
        if h <= 0:
            continue
        u = (h+a-1) // a
        r += u
        k += u * a
        t.append((x+d*2, u*a))

    return r


print(main())

Solution (Python):
def wczytaj_liste():
    ciag = input()
    rozdzielona_lista = ciag.split()
    odp = []
    for wyraz in rozdzielona_lista:
        liczba = int(wyraz)
        odp.append(liczba)
    return odp

def F_symulacja():
    N, D, A = wczytaj_liste()
    monstery = []
    for i in range(N):
        x, h = wczytaj_liste()
        monstery.append((x, h))
    monstery.sort()
    wynik = 0
    while len(monstery) > 0:
        x, h = monstery[0]
        if h <= 0:
            monstery.pop(0)
            continue
        bomba_x = x + D
        wynik += 1
        for i in range(len(monstery)):
            x_i, h_i = monstery[i]
            if bomba_x - D <= x_i <= bomba_x + D:
                monstery[i] = (x_i, h_i - A)

    print(wynik)

def zabij(H, A):
    if H % A == 0:
        return H // A
    else:
        return H // A + 1

def F():
    N, D, A = wczytaj_liste()
    monstery = []
    for i in range(N):
        x, h = wczytaj_liste()
        monstery.append((x, h))
    monstery.sort()

    wynik = 0
    gdzie_sie_koncza_bomby = []
    skonczone = 0
    ile_tu_spadlo = 0
    for x, h in monstery:
        while len(gdzie_sie_koncza_bomby) > skonczone:
            bomby_do, ile_bomb = gdzie_sie_koncza_bomby[skonczone]
            if bomby_do < x:
                ile_tu_spadlo -= ile_bomb
                skonczone += 1
            else:
                break
        if h - ile_tu_spadlo * A > 0:
            zrzucam_tutaj = zabij(h - ile_tu_spadlo * A, A)
            wynik += zrzucam_tutaj
            ile_tu_spadlo += zrzucam_tutaj
            gdzie_sie_koncza_bomby.append((x + 2 * D, zrzucam_tutaj))
    print(wynik)

F()

Solution (Python):

import sys
from bisect import bisect_left, bisect_right

N,D,A=map(int, sys.stdin.readline().split())
XH=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
XH.sort()

bit=[ 0 for _ in range(N+1) ]


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

def sum(a):
    ret=0
    while 0<a:
        ret+=bit[a]
        a-=a&-a
    return ret


def range_add(l,r,w):
    add(l,w)
    add(r+1,w*-1)


def get_value(a):
    return sum(a)

X=[float("-inf")]
H=[float("-inf")]
for x,h in XH:
    X.append(x)
    H.append(h)

for i in range(1,N+1):
    if i==1:
        add(i,H[i])
    else:
        add(i,H[i]-H[i-1])  
    
ans=0

for i in range(1,N+1):
    h=get_value(i)
    if h<=0:    
        pass
    else:
        x=X[i]
        pos=bisect_right(X,x+2*D)-1 
        if h%A==0:   
            cnt=h/A
            range_add(i,pos,A*cnt*-1)
        else:
            cnt=h/A+1   
            range_add(i,pos,A*cnt*-1)
        ans+=cnt

print ans

Solution (Python):

import sys
from bisect import bisect_left, bisect_right

N,D,A=map(int, sys.stdin.readline().split())
XH=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
XH.sort()

bit=[ 0 for _ in range(N+1) ]


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

def sum(a):
    ret=0
    while 0<a:
        ret+=bit[a]
        a-=a&-a
    return ret


def range_add(l,r,w):
    add(l,w)
    add(r+1,w*-1)


def get_value(a):
    return sum(a)

X=[float("-inf")]
H=[float("-inf")]
for x,h in XH:
    X.append(x)
    H.append(h)

for i in range(1,N+1):
    if i==1:
        add(i,H[i])
    else:
        add(i,H[i]-H[i-1])  
    
ans=0

for i in range(1,N+1):
    h=get_value(i)
    if h<=0:    
        pass
    else:
        x=X[i]
        pos=bisect_right(X,x+2*D)-1 
        if h%A==0:   
            cnt=h/A
            range_add(i,pos,A*cnt*-1)
        else:
            cnt=h/A+1   
            range_add(i,pos,A*cnt*-1)
        ans+=cnt

print ans

Solution (Python):


import math

N,D,A = map(int, input().split())
XH = sorted(tuple(map(int, input().split())) for _ in range(N))

Q = []
qIdx = 0
s = 0
t = 0

for (x, h) in XH:
    while qIdx < len(Q) and  Q[qIdx][0] < x:
        s -= Q[qIdx][1]
        qIdx += 1

    if s < h:
        q = int(math.ceil((h-s)/A))
        Q.append((x+2*D, q*A))
        s += q*A
        t += q

print(t)

Solution (Python):

import sys
from collections import deque

N,D,A=map(int, sys.stdin.readline().split())
XH=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
XH.sort()

q=deque()   
ans=0
cnt=0

attack_point=0
for x,h in XH:
    while q:
        if x<q[0][0]:break  
        end_x,end_point=q.popleft()
        attack_point-=end_point 

    if h<=attack_point: 
        pass
    else:   
        if h%A==0:
            cnt=(h-attack_point)/A  
        else:
            cnt=(h-attack_point)/A+1
        attack_point+=cnt*A
        q.append((x+2*D+1,cnt*A))   
        ans+=cnt

print ans

Solution (Python):

import sys
from collections import deque

N,D,A=map(int, sys.stdin.readline().split())
XH=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
XH.sort()

q=deque()   
ans=0
cnt=0

attack_point=0
for x,h in XH:
    while q:
        if x<q[0][0]:break
        end_x,end_point=q.popleft()
        attack_point-=end_point

    if h<=attack_point:
        pass
    else:
        if h%A==0:
            cnt=(h-attack_point)/A
        else:
            cnt=(h-attack_point)/A+1
        attack_point+=cnt*A
        q.append((x+2*D+1,cnt*A))
        ans+=cnt

print ans

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

data = []
for _ in range(N):
	data.append(tuple(map(int, input().split())))

data.sort()

queue = []
i = 0
j = 0
total = 0
height = 0
while i < N:
	if j >= len(queue) or data[i][0] <= queue[j][0]:
		x, h = data[i]
		i += 1
		if height < h:
			count = (h - height + A - 1) // A
			total += count
			height += count * A
			queue.append((x + D * 2, count * A))
	else:
		height -= queue[j][1]
		j += 1

print(total)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, D, A = LI()
    X_H = []
    for _ in range(N):
        x, h = LI()
        X_H.append((x, h))
    X_H = sorted(X_H, key=lambda x:x[0])
    X = [elem[0] for elem in X_H]
    kaihuku = [0 for _ in range(N)]
    cur_damage = 0
    n_attack = 0
    cnt = 0
    for i in range(N):
        x, tairyoku = X_H[i]
        cur_damage = cur_damage - kaihuku[i]
        tairyoku -= cur_damage
        tairyoku = max(tairyoku, 0)
        n_attack = tairyoku // A + (tairyoku % A > 0)

        cur_damage += n_attack * A
        ins_pos = bisect.bisect_right(X, x + 2*D)
        if ins_pos < N:
            kaihuku[ins_pos] += n_attack * A
        cnt += n_attack

    print(cnt)

main()

Solution (Python):
import math
import sys
input = sys.stdin.readline
import heapq
def main():
    N,D,A=map(int,input().split())
    xh = [tuple(map(int,input().split())) for _ in range(N)]
    xh = sorted(xh, key = lambda x:x[0])
    x = [elem[0] for elem in xh]
    h = [elem[1] for elem in xh]
    res = 0
    buff = 0
    q = []
    heapq.heapify(q)
    for (X, H) in zip(x, h):
        while len(q)!=0:
            p = heapq.heappop(q)
            if p[0] < X:
                buff -= p[1]
            else:
                heapq.heappush(q,p)
                break
        nowhp = H - buff*A
        if nowhp <= 0:
            continue
        cnt = math.ceil(nowhp/A)
        res += cnt
        buff += cnt
        ins = (X+2*D, cnt)
        heapq.heappush(q,ins)
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    from collections import deque
    from operator import itemgetter
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    d*=2
    m=map(int,b.read().split())
    q=deque()
    popleft,append=q.popleft,q.append
    s=b=0
    for x,h in sorted(zip(m,m),key=itemgetter(0)):
        while q and q[0][0]<x:b-=popleft()[1]
        if h>b:
            t=(b-h)//a
            s-=t
            t*=a
            b-=t
            append((x+d,-t))
    print(s)
main()

Solution (Python):
def main():
    import sys
    from collections import deque
    from operator import itemgetter
    g=itemgetter(0)
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    q=deque()
    popleft,append=q.popleft,q.append
    s=b=0
    for x,h in sorted(zip(m,m),key=g):
        while q and g(g(q))<x:b-=popleft()[1]
        if h>b:
            t=(b-h)//a
            s-=t
            t*=a
            b-=t
            append((x+d+d,-t))
    print(s)
main()

Solution (Python):
def main():
    import sys
    from collections import deque
    from operator import itemgetter
    M=10**10
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    q=deque()
    popleft,append=q.popleft,q.append
    s=b=0
    for x,h in sorted(zip(m,m),key=itemgetter(0)):
        while q and q[0]//M<x:b-=popleft()%M
        if h>b:
            t=(b-h)//a
            s-=t
            t*=a
            b-=t
            append((x+d+d)*M-t)
    print(s)
main()

Solution (Python):
def main():
    import sys
    from collections import deque
    from operator import itemgetter
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    q=deque()
    popleft,append=q.popleft,q.append
    s=b=0
    for x,h in sorted(zip(m,m),key=itemgetter(0)):
        while q and q[0][0]<x:b-=popleft()[1]
        if h>b:
            t=(b-h)//a
            s-=t
            t*=a
            b-=t
            append((x+d+d,-t))
    print(s)
main()

Solution (Python):
from collections import deque

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

XH.sort()
q = deque()
damage = 0
result = 0
for x, h in XH:
    while q:
        if x <= q[0][0]:
            break
        damage -= q.popleft()[1]
    h -= damage
    if h <= 0:
        continue
    c = (h + A - 1) // A
    result += c
    damage += c * A
    q.append((x + 2 * D, c * A))
print(result)

Solution (Python):
from collections import deque

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

XH.sort()
q = deque()
t = 0
result = 0
for x, h in XH:
    while q:
        if x <= q[0][0]:
            break
        t -= q[0][1]
        q.popleft()
    h -= t
    if h <= 0:
        continue
    c = (h + A - 1) // A
    result += c
    t += c * A
    q.append((x + 2 * D, c * A))
print(result)

Solution (Python):
from math import ceil
from bisect import bisect_right
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
imos=[0]*(n+1)
x=[]
for i in range(n):
  x.append(xh[i][0])
ans,cnt=0,0
for i in range(n):
  cnt+=imos[i]
  hp=xh[i][1]-cnt*a
  if hp>0:
    cnt+=ceil(hp/a)
    ans+=ceil(hp/a)
    imos[bisect_right(x,x[i]+2*d)]-=ceil(hp/a)
print(ans)

Solution (Python):
def main():
    import sys
    from collections import deque
    from operator import itemgetter
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    q=deque()
    popleft,append=q.popleft,q.append
    s=b=0
    for x,h in sorted(zip(m,m),key=itemgetter(0)):
        while q and q[0][0]<x:b-=popleft()[1]
        h-=b
        t=-(-h//a)
        if t>0:
            s+=t
            t*=a
            b+=t
            append((x+d+d,t))
    print(s)
main()

Solution (Python):
import bisect, math
N,D,A = map(int,input().split())
enemy = list(list(map(int,input().split()))for i in range(N))
enemy.sort()

damege = [0]*N

ans = 0
p = 0
while p < N:
    if p>=1:
        damege[p] += damege[p-1]
    enemy[p][1] -= damege[p]
    if enemy[p][1] <= 0:
        p += 1 
        continue
    d = math.ceil(enemy[p][1]/A)
    ans += d
    d *= A
    r = bisect.bisect_right(enemy,[enemy[p][0]+D*2,10**9+7])
    if r!=N:
        damege[r]-=d
    damege[p] += d
    p+=1
print(ans)

Solution (Python):
def main():
  import sys
  from collections import deque
  from operator import itemgetter
  
  b = sys.stdin.buffer
  N,D,A = map(int, b.readline().split())
  m = map(int, b.read().split())
  ans = 0
  Q = deque()
  d = 0
  for x,h in sorted(zip(m,m), key=itemgetter(0)):
    while Q and Q[0][0] < x:
      _,d_ = Q.popleft()
      d += d_
    h = h+d
    if h <= 0: continue
    n = -(-h // A)
    d -= n * A
    ans += n
    Q.append((x+2*D,n * A))

  print(ans)
  
main()

Solution (Python):
def main():
    import sys
    from collections import deque
    from operator import itemgetter
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    p,q=deque(),deque()
    pl,ql=p.popleft,q.popleft
    pa,qa=p.append,q.append
    s=b=0
    for x,h in sorted(zip(m,m),key=itemgetter(0)):
        while p and p[0]<x:
            pl()
            b-=ql()
        h-=b
        t=-(-h//a)
        if t>0:
            s+=t
            t*=a
            b+=t
            pa(x+d+d)
            qa(t)
    print(s)
main()