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: Accepted

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

import sys
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class StarrySkyTree:
    """ Starry Sky Tree(区間加算・区間最小(大)値取得) """

    def __init__(self, N, func, intv):
        self.intv = intv
        self.func = func
        LV = (N-1).bit_length()
        self.N0 = 2**LV
        self.data = [0]*(2*self.N0)
        self.lazy = [0]*(2*self.N0)

    # 伝搬される区間のインデックス(1-indexed)を全て列挙するgenerator
    def gindex(self, l, r):
        L = l + self.N0; R = r + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L:
            yield L
            L >>= 1

    # 遅延評価の伝搬処理
    def propagates(self, *ids):
        # 1-indexedで単調増加のインデックスリスト
        for i in reversed(ids):
            v = self.lazy[i-1]
            if not v:
                continue
            self.lazy[2*i-1] += v; self.lazy[2*i] += v
            self.data[2*i-1] += v; self.data[2*i] += v
            self.lazy[i-1] = 0

    def update(self, l, r, x):
        """ 区間[l,r)の値にxを加算 """

        # 1. lazyの値は伝搬させない
        # 2. 区間[l,r)のdata, lazyの値を更新
        L = self.N0 + l; R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] += x; self.data[R-1] += x
            if L & 1:
                self.lazy[L-1] += x; self.data[L-1] += x
                L += 1
            L >>= 1; R >>= 1
        # 3. 更新される区間を部分的に含んだ区間のdataの値を更新 (lazyの値を考慮)
        for i in self.gindex(l, r):
            self.data[i-1] = self.func(self.data[2*i-1], self.data[2*i]) + self.lazy[i-1]

    def query(self, l, r):
        """ 区間[l,r)の最小(大)値を取得 """

        # 1. トップダウンにlazyの値を伝搬
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r

        # 2. 区間[l, r)の最小(大)値を求める
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.func(s, self.data[R-1])
            if L & 1:
                s = self.func(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

N, D, K = MAP()

XH = []
for i in range(N):
    x, h = MAP()
    XH.append((x, h))

XH.sort()
X, H = zip(*XH)
D = D * 2

sst = StarrySkyTree(N+1, max, 0)
ans = 0
for i, (x, h) in enumerate(XH):
    h -= sst.query(i, i+1) * K
    if h <= 0:
        continue
    cnt = ceil(h, K)
    idx = bisect_right(X, x+D) - 1
    sst.update(i, idx+1, cnt)
    ans += cnt
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n, d, a = [int(v) for v in input().split()]

X = []
for i in range(n):
    xh = [int(v) for v in input().split()]
    X.append(xh)

X.sort()


q = deque()

bomb = 0
d2 = d * 2
attack = 0
for xh in X:
    x, h = xh

    while len(q) > 0 and q[0][0] < x:
        x1, h1 = q.popleft()
        attack -= h1

    if h > attack:
        diff = h - attack
        bomb1 = diff // a
        if diff % a != 0:
            bomb1 += 1
        bomb += bomb1

        attack1 = bomb1 * a
        q.append((x+d2, attack1))
        attack += attack1

print(bomb)

Submission status: Accepted

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

from bisect import bisect_right

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

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

check = [0] * (N + 1)


index = 0
pt = XH[index][0] + 2 * D
ht = (-(-XH[index][1] // A)) * A
minus = ht
answer = -(-XH[index][1] // A)
bi = bisect_right(X, pt)
check[bi] += ht

while 1:
  flag = 1
  for i in range(index, N):
    minus -= check[i]
    XH[i][1] -= minus
    check[i] = 0
    if XH[i][1] > 0:
      index = i
      flag = 0
      break
  if flag:
    break
  pt = XH[index][0] + 2 * D
  ht = (-(-XH[index][1] // A)) * A
  minus += ht
  answer += -(-XH[index][1] // A)
  bi = bisect_right(X, pt)
  check[bi] += ht
                 
print(answer)

Submission status: Accepted

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


ans = 0
bomb_effect = 0
bomb_i = 0
bombs = []
for x, h in XH:
    while (bomb_i < len(bombs)) and (x > bombs[bomb_i][0]):
        bomb_effect -= bombs[bomb_i][1] * A
        bomb_i += 1

    tairyoku = h - bomb_effect
    if tairyoku > 0:
        new_bomb = -((-tairyoku) // A)
        ans += new_bomb
        bombs.append((x + 2 * D + 0.5, new_bomb))
        bomb_effect += new_bomb * A

print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,d,a = LI()
    p = LIR(n)
    s = [0]*(n+1)
    p.sort()
    ans = 0
    X = [p[i][0] for i in range(n)]
    for i in range(n):
        x,h = p[i]
        j = bisect.bisect_left(X,x-2*d)
        if i != j:
            su = s[i-1]
            if j > 0:
                su -= s[j-1]
            h -=  su
        if h > 0:
            l = x
            k = math.ceil(h/a)
            ans += k
            s[i] = k*a
        s[i] += s[i-1]
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

ans = 0
P = 0
hist = []
j = 0
for i in range(N):
    X, H = XH[i]
    while True:
        if j >= len(hist):
            break
        if hist[j][0] >= X:
            break
        if hist[j][0] < X:
            P -= hist[j][1]
            j += 1
    
    if H - P > 0:
        if (H - P) % A == 0:
            bomb = (H - P) // A
        else:
            bomb = (H - P) // A + 1
        ans += bomb
        P += bomb * A
        hist.append((X + 2 * D, bomb * A))
    

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def add(i,s):
        while i <= n:
            bit[i] += s
            i += i&-i

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res

    n,d,a = LI()
    p = LIR(n)
    bit = [0]*(n+1)
    p.sort()
    ans = 0
    X = [p[i][0] for i in range(n)]
    for i in range(n):
        x,h = p[i]
        j = bisect.bisect_left(X,x-2*d)
        if i != j:
            su = sum(i+1)
            if j > 0:
                su -= sum(j)
            h -=  su
        if h > 0:
            l = x
            k = math.ceil(h/a)
            ans += k
            add(i+1,k*a)
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
class SegmentTreeDual():
    def __init__(self,arr,op=lambda x,y:y if y != -1 else x,ie=-1):
        self.h = (len(arr)-1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.op = op
        self.val = [ie for _ in range(self.n)]
        self.laz = [ie for _ in range(2*self.n)]
        for i in range(len(arr)):
            self.val[i] = arr[i]
    def propagate(self,k):
        if self.laz[k] == self.ie:
            return
        if self.n <= k:
            self.val[k-self.n] = self.op(self.val[k-self.n],self.laz[k])
            self.laz[k] = self.ie
        else:
            self.laz[(k<<1)] = self.op(self.laz[(k<<1)],self.laz[k])
            self.laz[(k<<1)+1] = self.op(self.laz[(k<<1)+1],self.laz[k])
            self.laz[k] = self.ie
    def update(self,left,right,f):
        left += self.n
        right += self.n
        for i in range(self.h)[::-1]:
            self.propagate(left>>i)
            self.propagate(right>>i)
        while right - left > 0:
            if right & 1:
                right -= 1
                self.laz[right] = self.op(self.laz[right],f)
            if left & 1:
                self.laz[left] = self.op(self.laz[left],f)
                left += 1
            left >>= 1
            right >>= 1
    def get(self,index):
        res = self.val[index]
        index += self.n
        while index>0:
            res = self.op(res,self.laz[index])
            index //= 2
        return res

import sys
input = sys.stdin.readline

import bisect

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

monster.sort()
ans = 0
X = []
H = []
for i in range(N):
    X.append(monster[i][0])
    H.append(monster[i][1])

hani = [0 for _ in range(N)]
for i in range(N):
    hani[i] = bisect.bisect_left(X,X[i]+2*D+1)

sg = SegmentTreeDual(H,lambda x,y:x+y,0)

for i in range(N):
    hp = sg.get(i)
    if hp <= 0:
        continue
    cnt = -(-hp//A)
    sg.update(i,hani[i],-A*cnt)
    ans += cnt

print(ans)

Submission status: Accepted

Solution code:
# coding=utf-8
# Date: 2020-01-08
# Author: lee215

import heapq
get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: map(int, raw_input().strip().split())
getss = lambda n: [gets() for _ in xrange(n)]


N, D, A = gets()
XH = sorted(getss(N))

bombs = []
res = cur_b = 0
for x, h in XH:
    while bombs and bombs[0][0] < x - D:
        bx, bn = heapq.heappop(bombs)
        cur_b -= bn
    h -= cur_b * A
    if h <= 0: continue
    bn = (h + A - 1) / A if A > 1 else h
    cur_b += bn
    res += bn
    heapq.heappush(bombs, [x + D, bn])
print res

Submission status: Accepted

Solution code:
from bisect import*
def _add(data, k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)

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

Submission status: Accepted

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

from heapq import heappush, heappop

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

XH.sort()

ret = 0
hp = []
s = 0
for i, (x, h) in enumerate(XH) :
  while len(hp) > 0 and hp[0][0] < x - D :
    s -= heappop(hp)[1]
    
  if s > h :
    continue
  
  cnt = (h - s + A - 1) // A
  ret += cnt
  heappush(hp, (x + D, cnt * A))
  s += cnt * A

print(ret)

Submission status: Accepted

Solution code:
n, d, a = map(int, input().split())
loans = []
bar = 0
ans = 0
xh = sorted([tuple(map(int, input().split())) for _ in range(n)])

for x, h in xh:
    while len(loans) > 0:
        xx, dd = loans[0]
        if xx < x:
            loans.pop(0)
            bar -= dd
        else:
            break

    h -= bar
    if h > 0:
        c = h // a if h % a == 0 else ((h // a) + 1)
        ans += c
        dd = c * a
        bar += dd
        loans.append((x + 2 * d, dd))

print(ans)

Submission status: Accepted

Solution code:
N,D,A = map(int,input().split())
XH = []
X = []

for i in range(N):
    x,h = map(int,input().split())
    XH.append([x,h,0])
    X.append(x)
    
XH.sort(key = lambda a:a[0])
XH.append([float('inf'),0,0])
X.sort()
X.append(float('inf'))

import bisect
ans = 0

for i in range(N):
    x,h,k = XH[i]
    dk = max(-(-(h-k*A)//A),0)
    #print(x,h,k,dk)
    ans += dk
    
    XH[i][2] += dk
    j = bisect.bisect_right(X,x+2*D)
    XH[j][2] -= dk

    XH[i+1][2] += XH[i][2]
    
print(ans)

Submission status: Accepted

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

p = 0
j = 0
data = []
for i in range(n):
    while XH[i][0] > XH[j][0] + 2*d:
        p -= data[j]
        j += 1
    if XH[i][1] > p:
        data.append(XH[i][1]-p)
        ans += XH[i][1]-p
        p = XH[i][1]
    else:
        data.append(0)

print(ans)

Submission status: Accepted

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
po = []
for i in range(n):
    on = aaa[i]
    for j in range(ll,n):
        if lll[j][1] < aaa[i][0] and i > j:
            c -= po[j]
        else:
            ll = j
            break
    if on[1] <= c:
        po.append(0)
        continue
    else:
        co += on[1]-c
        po.append(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: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq
from math import ceil
n,d,a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]
xh.sort()

res = 0
b = []
heapq.heapify(b)
r = 0
for i in range(n):
    x,h = xh[i]

    while len(b)>0 and b[0][0]<=x:
        r += b[0][1]
        heapq.heappop(b)
    c = max(ceil((h-r)/a), 0)
    res += c
    r += c*a
    
    if c>0:
        heapq.heappush(b, (x+2*d+1, -c*a))

print(res)

Submission status: Accepted

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 += ceil(hi,A)
        # 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: Accepted

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
        nx = Input[bisect_right(Input, x+2*D)-1]
        bit.add(nx, A*count)

print(ans)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict
import bisect

INF = float("inf")
con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, D, A = getlist()
	XH = []
	for i in range(N):
		X, H = getlist()
		XH.append([X, H])
	XH = sorted(XH)
	X = []
	H = []
	for i in range(N):
		X.append(XH[i][0])
		H.append(XH[i][1])

	X.append(INF)

	#回数に変換
	for i in range(N):
		h = H[i]
		if h % A == 0:
			H[i] = int(h // A)
		else:
			H[i] = int(h // A) + 1

	imos = [0] * (N + 1)
	ans = 0
	x = bisect.bisect_right(X, X[0] + 2 * D)
	imos[0] -= H[0]
	imos[x] += H[0]
	ans += H[0]
	for i in range(N - 1):
		imos[i + 1] += imos[i]
		if H[i + 1] + imos[i + 1] > 0:
			x = bisect.bisect_right(X, X[i + 1] + 2 * D)
			ans += H[i + 1] + imos[i + 1]
			imos[x] += H[i + 1] + imos[i + 1]
			imos[i + 1] = -H[i + 1]
	
	print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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 = [XH[i][0] for i in range(N)]
ans = 0
res = 0
from bisect import bisect_left
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_left(XH, [x+D*2+1, -1])
    cnt[j] += n*A
    res += n*A
    ans+=n
print(ans)

Submission status: Accepted

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]
    h[i] = (h[i] - 1) // a + 1
t = 0
r = 0
ans = 0
for l in range(n):
    tmp = 0
    while r < n and x[r] - x[l] <= d:
        h[r] -= t
        t += max(h[r], 0)
        tmp += max(h[r], 0)
        r += 1
    t -= max(h[l], 0)
    ans += tmp
print(ans)

Submission status: Accepted

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: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


from collections import deque


def main():
    n, d, a = map(int, input().split())
    x, h = [0] * n, [0] * n
    for i in range(n):
        x[i], h[i] = map(int, input().split())

    order = sorted(range(n), key=lambda idx: x[idx])
    res = 0
    sub = 0
    bounds = deque()
    for idx in order:
        while bounds and x[idx] > bounds[0][0]:
            bound, count = bounds.popleft()
            sub -= count
        h[idx] -= sub
        if h[idx] > 0:
            bound = x[idx] + 2 * d
            count = (h[idx] + a - 1) // a
            sub += count * a
            bounds.append((bound, a * count))
            res += count

    print(res)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    from bisect import bisect_left
    from operator import itemgetter

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

    xh = []
    xs = set()
    for _ in range(N):
        x, h = map(int, input().split())
        xh.append((x, h))
        xs.add(x)
        xs.add(x + D)
        xs.add(x + D * 2)

    xh.sort(key=itemgetter(0), reverse=True)

    *xs, = sorted(xs)

    imos = [0] * (len(xs) + 10)
    mons = [0] * (len(xs) + 10)
    for x, h in xh:
        i = bisect_left(xs, x)
        mons[i] += h

    ret = 0
    for i in range(len(xs) + 1):
        d = (mons[i] - imos[i] + A - 1) // A
        if d > 0:
            ret += d
            imos[i] += d * A
            imos[bisect_left(xs, xs[i] + D * 2) + 1] -= d * A
        imos[i + 1] += imos[i]

    print(ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

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: Accepted

Solution code:
import sys
input = sys.stdin.readline
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_left
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_left(XH, [x+D*2+1, -1])
    cnt[j] += n*A
    res += n*A
    ans+=n
print(ans)