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:
n,d,a= map(int, input().split( ))
ms = []
for i in range(n):
    xi,hi = map(int, input().split( ))
    tmp = 0
    if hi%a:
        tmp+=1
    ms.append([xi,hi//a+tmp])

ms.sort()
ans = ms[0][1]
tmp = ms[0][1]
from collections import deque

Q = deque()
Q.append(0)

for i in range(1,n):

    while Q:###ifから変更
        tmp2 = Q.popleft();
        if ms[tmp2][0]+2*d<ms[i][0]:###tmpじゃないわms[tmp2][0]だわ
            tmp -= ms[tmp2][1]
        else:
            Q.appendleft(tmp2)
            break###
    ms[i][1]-=tmp###
    ms[i][1] = max(ms[i][1],0)###

    if ms[i][1]>0:
        ms[i][1]-=tmp
        ans += ms[i][1]
        Q.append(i)
        tmp += ms[i][1]
print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a= map(int, input().split( ))
ms = []
for i in range(n):
    xi,hi = map(int, input().split( ))
    tmp = 0
    if hi%a:
        tmp+=1
    ms.append([xi,hi//a+tmp])

ms.sort()
ans = ms[0][1]
tmp = ms[0][1]
from collections import deque

Q = deque()
Q.append(0)

for i in range(1,n):

    while Q:###ifから変更
        tmp2 = Q.popleft();
        if tmp2+2*d<ms[i][0]:
            tmp -= ms[tmp2][1]
        else:
            Q.appendleft(tmp2)
            break###
    ms[i][1]-=tmp###
    ms[i][1] = max(ms[i][1],0)###

    if ms[i][1]>0:
        ms[i][1]-=tmp
        ans += ms[i][1]
        Q.append(i)
        tmp += ms[i][1]

   
print(ans)

Submission status: Wrong Answer

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)]
for i in range(n):
    xh[i][1]=-(-xh[i][1]//a)
xh.sort()
ans=0
cnt=0
X=-float("inf")
for i in range(n):
    x,h=xh[i]
    if x<=X:
        if h>cnt:
            cnt=h-cnt
            ans+=cnt
            X=x+2*d
    else:
        cnt=h
        ans+=h
        X=x+2*d
print(ans)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys


mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

N, D, A = LI()
xh = []
for i in range(N):
    xh.append(LI())
X = []
for i in range(N):
    X.append(xh[i][0])

bomb = [0 for i in range(N)]
ans = 0
now_dm = 0
for i in range(N):
    x,H = xh[i]
    now_dm += bomb[i]
    if now_dm >= H:
        pass
    else:
        ans += math.ceil((H - now_dm)/A)
        dm = math.ceil((H-now_dm)/A) * A
        ind = bisect.bisect_right(X, x+2*D)
        if i + 1 < N:
            bomb[i+1] += dm
        if ind < N:
            bomb[ind] -= dm

print(ans)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys


mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

N, D, A = LI()
xh = []
for i in range(N):
    xh.append(LI())
X = []
for i in range(N):
    X.append(xh[i][0])

bomb = [0 for i in range(N)]
ans = 0
now_dm = 0
for i in range(N):
    x,H = xh[i]
    now_dm += bomb[i]
    if now_dm >= H:
        pass
    else:
        ans += math.ceil((H - bomb[i])/A)
        dm = math.ceil((H-bomb[i])/A) * A
        ind = bisect.bisect_right(X, x+2*D)
        if i + 1 < N:
            bomb[i+1] += dm
        if ind < N:
            bomb[ind] -= dm

print(ans)

Submission status: Wrong Answer

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

mon.sort()

def f(h):
    if h <= 0:
        return 0
    ans = h // a
    if h %a !=0:
        ans +=1
    return ans

cnt_sum =0
cnt = [0]*n
l = 0 
for i in range(n):
    while mon[i][0] + 2*d < mon[i][0]:
        cnt_sum -= cnt[i]
        i +=1
    already = cnt_sum*a 
    cnt[i] = f(mon[i][1]- already)
    cnt_sum += cnt[i]
print(sum(cnt))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

class DualSegmentTree:
    def __init__(self, n) :
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [0] * (self.N0*2)

    def update(self, l, r, val) :
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] = self.data[l] + val
                l += 1
            if r & 1:
                self.data[r-1] = self.data[r-1] + val
                r -= 1
            l //= 2
            r //= 2

    def query(self, i):
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = ret + self.data[i]
        return ret




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

    enemy = []
    for i in range(N):
        x,h = list(map(int,input().split()))
        if h%A==0:
            enemy.append([x,h//A])
        else:
            enemy.append([x,h//A+1])

    enemy.sort(key=lambda x:x[0])
    def bisect(index):
        x = enemy[index][0]
        if enemy[N-1][0] <= x + 2*D:
            return N-1
        l = index
        r = N-1
        while r-l>1:
            if enemy[(r+l)//2][0] <= x + 2*D:
                l = (r+l)//2
            else:
                r = (r+l)//2
        return l
    ST = DualSegmentTree(N)

    for i in range(N):
        ST.update(i,i+1,enemy[i][1])

    count = 0
    for i in range(N):
        v = ST.query(i)
        count += v
        j = bisect(i)
        ST.update(i,j+1,-v) 

    print(count)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
import bisect

N,D,A=map(int,input().split())
List=[list(map(int,input().split())) for i in range(N)]
List.sort()
  
cnt = 0
for i in range(len(List)):
  x = List[i][0]
  h = List[i][1]
  while List[i][1] > 0:
    a = bisect.bisect_right(List, [int(x)+2*D,999999999999999999999])
    T = math.ceil(h/A)
    for j in range((a-i)):
      List[i+j][1] -= int(T)
    cnt += int(T)
print(int(cnt))

Submission status: Wrong Answer

Solution code:
from collections import deque
N, D, A = map(int, input().split())

ys = []
hs = []
for i in range(N):
    X, H = map(int, input().split())
    ys.append((X,i))
    hs.append(-(-H//A))

ys = sorted(ys, key=lambda x : x[0])
l = ys[0][0] + 2*D
li = 0
dmg = 0
r = 0
for y, i in ys:
    while l < y:
        li += 1
        l = ys[li][0] + 2*D
        dmg -= hs[ys[li][1]]
    tr = max(0, hs[i]-dmg)
    hs[i] = tr
    dmg += tr
    r += tr
print(r)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,D,A = map(int,input().split(" "))
line = [[] for _ in range(N)]
for i in range(N):
    line[i] = list(map(int,input().split(" ")))
line.sort()
rng = line[-1][0] - line[0][0]
if rng <= 2*D:
    hp = 0
    for i in range(N):
        hp = max(line[i][1],hp)
    ans = hp//A
    if hp%A != 0:
        ans += 1
else:
    ans = 0
    for i,v in enumerate(line):
        x,h = v
        cnt = h//A
        if h % A != 0:
            cnt += 1
        for j in range(i,N):
            if line[j][0] <= x+2*D:
                line[j][1] -= cnt*A
            else:
                break
        ans += cnt
        if line[-1][1] <= 0:
            break

print(ans)

Submission status: Wrong Answer

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()
ans=0
cnt=0
X=-float("inf")
for i in range(n):
    x,h=xh[i]
    if x<=X:
        if h<=cnt*a:
            continue
        else:
            cnt=-(-(h-cnt*a)//a)
            ans+=cnt
            X=x+2*d
    else:
        cnt=-(-h//a)
        ans+=cnt
        X=x+2*d
    #print(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,D,A = map(int,input().split(" "))
line = [[] for _ in range(N)]
for i in range(N):
    line[i] = list(map(int,input().split(" ")))
line.sort()
rng = line[-1][0] - line[0][0]
if rng <= 2*D:
    hp = 0
    for i in range(N):
        hp = max(line[i][1],hp)
    ans = hp//A
    if hp%A != 0:
        ans += 1
else:
    ans = 0
    for i,v in enumerate(line):
        x,h = v
        cnt = h//A
        if h % A != 0:
            cnt += 1
        for j in range(i,N):
            if line[j][0] <= x+2*D:
                line[j][1] -= cnt*A
        ans += cnt
        if line[-1][1] <= 0:
            break

print(ans)

Submission status: Wrong Answer

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()
ans=0
cnt=0
X=float("inf")
for i in range(n):
    x,h=xh[i]
    if x<=X:
        if h<=cnt*a:
            continue
        else:
            cnt=-(-(h-cnt*a)//a)
            ans+=cnt
            X=x+2*d
    else:
        cnt=-(-h//a)
        ans+=cnt
        X=x+2*d
    #print(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a= map(int, input().split( ))
ms = []
for i in range(n):
    xi,hi = map(int, input().split( ))
    tmp = 0
    if hi%a:
        tmp+=1
    ms.append([xi,hi//a+tmp])

ms.sort()
ans = ms[0][1]
tmp = ms[0][1]

from collections import deque

Q = deque()
Q.append(0)

for i in range(1,n):
    while Q:###ifから変更
        tmp2 = Q.popleft();
        if tmp2+2*d<ms[i][0]:
            tmp -= ms[tmp2][1]
        else:
            Q.appendleft(tmp2)
            break###
    
    if ms[i][1]>tmp:
        ms[i][1]-=tmp
        ans += ms[i][1]
        Q.append(i)
        tmp += ms[i][1]
   
print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a= map(int, input().split( ))
ms = []
for i in range(n):
    xi,hi = map(int, input().split( ))
    tmp = 0
    if hi%a:
        tmp+=1
    ms.append([xi,hi//a+tmp])

ms.sort()
ans = ms[0][1]
tmp = ms[0][1]

from collections import deque

Q = deque()
Q.append(0)

for i in range(1,n):
    if Q:
        tmp2 = Q.popleft();
        if tmp2+2*d<ms[i][0]:
            tmp -= ms[tmp2][1]
        else:
            Q.appendleft(tmp2)
    
    if ms[i][1]>tmp:
        ms[i][1]-=tmp
        ans += ms[i][1]
        Q.append(i)
        tmp += ms[i][1]
   
print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a= map(int, input().split( ))
ms = []
for i in range(n):
    xi,hi = map(int, input().split( ))
    tmp = 0
    if hi%a:
        tmp+=1
    ms.append([xi,hi//a+tmp])

ms.sort()
ans = ms[0][1]
tmp = ms[0][1]

from collections import deque

Q = deque()
Q.append(0)

for i in range(1,n):
    if Q:
        tmp2 = Q.popleft();
        if tmp2+2*d<ms[i][0]:
            tmp -= ms[tmp2][1]
        else:
            Q.appendleft(tmp2)
    ms[i][1]-=tmp
    if ms[i][1]>0:
        ans += ms[i][1]
        Q.append(i)
        tmp += ms[i][1]
   
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, D, A, XH):
    XH.sort()
    X = [x for x, _ in XH]
    H = [h for _, h in XH]

    ans = 0
    for i in range(N):
        if H[i] <= 0:
            continue
        x = X[i]
        h = H[i]
        n = -(-h // A)
        ans += n
        r = bisect.bisect_right(X, x+2*D)
        for j in range(i, min(r+1, N)):
            H[j] -= n*A

    return ans


def main():
    N, D, A = read_int_n()
    XH = [read_int_n() for _ in range(N)]
    print(slv(N, D, A, XH))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
N, D, A = map(int, input().split())

ys = []
hs = []
for i in range(N):
    X, H = map(int, input().split())
    ys.append((X,i))
    hs.append(-(-H//A))

ys = sorted(ys, key=lambda x : x[0])
l = ys[0][0] + 2*D
li = 0
dmg = 0
ls = []
c = 0
r = 0
for y, i in ys:
    while l < y:
        li += 1
        l = ys[li][0] + 2*D
        dmg -= hs[ys[li][1]]
    tr = max(0, hs[i]-dmg)
    dmg += tr
    r += tr
print(r)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
n,d,a=map(int,input().split())
x,h=zip(*sorted(tuple(map(int,input().split())) for _ in range(n)))
x=np.array(x)
h=np.array(h)
q=deque()
res=0
s=0
for i,xi in enumerate(x):
    while q:
        q0=q[0]
        if q0[0] < xi:
            s-=q0[1]
            q.popleft()
        else:
            break
    hi=h[i]-s
    if hi < 0:
        break
    ci=-(-hi//a)
    res+=ci
    q.append((xi+2*d,hi))
    s+=hi
    
print(res)

Submission status: Wrong Answer

Solution code:
import sys,math
sr = sys.stdin.readline
def I(i=0):return [int(x)-i for x in sr().split()]
L1,L2 = [],[]

N,D,A = I()
for i in range(N):
    X,H = I()
    L1.append([X,math.ceil(H/A)])
L2 = sorted(L1)
ans = 0
for i in range(N):
    x,h = L2[i] 
    if h > 0:
        ans += h
        L2[i][1] = 0
        lim = x + 2*D
        for j in range(1,N-i):
            if L2[i+j][0] <= lim:
                L2[i+j][1] -= h
            else:
                break
print(int(ans))

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
import bisect
import math

N,d,a = map(int, input().split())
xh = sorted([list(map(int, input().split())) for i in range(N)], key=itemgetter(0))
x = []
for X,h in xh:
  x.append(X)
data0 = [0]*(N+1)
data1 = [0]*(N+1)

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)

ans = 0

for L,(X,H) in enumerate(xh):
  L += 1
  R = bisect.bisect_right(x,X+2*d)
  res = math.ceil((H - query(L,L+1) * a) / a) #ansを変える
  ans += res
  add(L,R+1,res)
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
import bisect
import math

N,d,a = map(int, input().split())
xh = sorted([list(map(int, input().split())) for i in range(N)], key=itemgetter(0))
x = []
for X,h in xh:
  x.append(X)
data0 = [0]*(N+1)
data1 = [0]*(N+1)

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)

ans = 0

for L,(X,H) in enumerate(xh):
  L += 1
  R = bisect.bisect_right(x,X+2*d)
  res = math.ceil((H - query(L,L+1) * a) / a) #ansを変える
  ans += res
  add(L,R+1,res)
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()

import collections
pq=collections.deque()

ans = 0
totalDamage = 0


for i in range(n):
    x,h = xh[i]
    if len(pq) and pq[0][0] < x:
        totalDamage -= pq[0][1]
        pq.popleft()
    h -=totalDamage
    if h <= 0:
        continue
    num = (h + a -1) //a
    ans += num
    dam = num*a
    totalDamage += dam
    pq.append((x+2*d,dam))

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import math
n, d, a = map(int, input().split())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
data.sort()
dam = 0
ans = 0
q = deque()
for i in range(n):
    x,h = data[i]
    while q:
        k = q.popleft()
        if k[1] >= x:
            q.appendleft(k)
            break
        else:
            dam -= k[0]
    print(q)
    h -= dam
    h = max(h, 0)
    count = math.ceil(h / a)
    dam += count * a
    q.append([count * a, x + 2*d])
    ans += count
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappush, heappop
from math import ceil

REAL = 0
UNREAL = 1

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

hp = []
for x, h in xh:
    heappush(hp, [x, h, REAL])

bomb_acm = 0
ans = 0
while hp:
    x, h, r = heappop(hp)
    if r == REAL:
        if h > bomb_acm:
            left = h - bomb_acm
            bomb_cnt = ceil(left / a)
            hp_dis = a * bomb_cnt
            bomb_acm += hp_dis
            heappush(hp, [x + 2 * d, hp_dis, UNREAL])
            ans += bomb_cnt

    else: # r == UNREAL
        bomb_acm -= h

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappush, heappop
from math import ceil

REAL = 0
UNREAL = 1

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

hp = []
for x, h in xh:
    heappush(hp, [x, h, REAL])

bomb_acm = 0
ans = 0
while hp:
    x, h, r = heappop(hp)
    if r == REAL:
        if h >= bomb_acm:
            left = h - bomb_acm
            bomb_cnt = ceil(left / a)
            hp_dis = a * bomb_cnt
            bomb_acm += hp_dis
            heappush(hp, [x + 2 * d, hp_dis, UNREAL])
            ans += bomb_cnt

    else: # r == UNREAL
        bomb_acm -= h

print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a=map(int,input().split())
xh=[tuple(map(int,input().split())) for _ in range(n)]
xh.sort()
ans=0
while xh:
  x,h=xh.pop(-1)
  c=h//a+bool(h%a)
  b=a*c
  ans+=c
  t=x+2*d
  pool=[]
  pappend=pool.append
  while True:
    if not xh:
      break
    y,z=xh.pop(-1)
    if y <= t:
      if z>b:
        z-=b
        pappend((y,z))
    else:
      pappend((y,z))
      break
  for i in range(len(pool)):
    xh.append(pool.pop(-1))
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()

import collections
q=collections.deque()

ans = 0
totalDamage = 0


for i in range(n):
    x,h = xh[i]
    if len(q) and q[0][0] < x:
        totalDamage -= q[0][1]
        q.popleft()
    h -=totalDamage
    if h <= 0:
        continue
    num = (h + a -1) //a
    ans += num
    dam = num*a
    totalDamage += dam
    q.append((x+2*d,dam))

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
import bisect
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])
XH2 = [XH[i][0] for i in range(N)]
left = D
flag = True
count = 0


s = [0] * (N+1)
ans = 0
for i in range(N):
    s[i+1] = s[i] + XH[i][1]
while(s[N] > 0):
    x = 0
    h = 10**10
    for i in range(N):
        if h > XH[i][1]:
            if XH[i][1] <= 0:
                continue
            x = XH[i][0]
            h = XH[i][1]
    k = bisect.bisect_left(XH2,  x-2*D)
    n = bisect.bisect_right(XH2, x+2*D)

    tmp = 0
    r = -1
    l = -1
    for i in range(k, n):

        m = bisect.bisect_right(XH2, XH[i][0] + 2*D)
        if s[m] - s[i] > tmp:
            tmp = s[m] - s[i]
            r = i
            l = m
        # print(s[m] - s[i])

    ans += math.ceil(h / A)
    # print(math.ceil(h / A), r, l)
    for i in range(r, l):
        XH[i][1] -= A * math.ceil(h / A)
        XH[i][1] = max(XH[i][1], 0)

    s = [0] * (N+1)
    for i in range(N):
        s[i+1] = s[i] + XH[i][1]
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()

import collections
q=collections.deque()

ans = 0
totalDamage = 0


for i in range(n):
    x,h = xh[i]
    if len(q) and q[0][0] < x:
        _,dam = q.popleft()
        totalDamage -= dam
    h -=totalDamage
    if h <= 0:
        continue
    num = (h + a -1) //a
    ans += num
    dam = num*a
    totalDamage += dam
    q.append((x+2*d,dam))

print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a = list(map(int,input().split()))
teki = []
for i in range(n):
    x,h = list(map(int,input().split()))
    teki.append([x,h])
teki.sort(key=lambda x:x[0])
#print(teki)
cnt = 0
for i in range(n):
    if teki[i][1] > 0:
#        print(cnt,teki)
        damage = int(-teki[i][1]/a)*(-1)
        cnt += int(-teki[i][1]/a)*(-1)
        teki[i][1] = 0
        j=1
        while i+j < n:
            if teki[i+j][0] <= teki[i][0] + 2*d:
#                print(i,j,int(-teki[i][1]/a)*a*(-1))
                teki[i+j][1] -= damage*a
                j += 1
            else:
                break
            
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n, di, a = LI()
    xs = []
    d = {}
    q = []
    for i in range(n):
        x, h = LI()
        xs.append(x)
        if h % a == 0:
            d[x] = h // a
        else:
            d[x] = h // a + 1
    sorted_xs = sorted(xs)
    ans = 0
    for i in range(n):
        x = sorted_xs[i]
        if d[x] < 1:
            continue
        else:
            ans += d[x]
            j = 0
            while i + j < n:
                if sorted_xs[i + j] <= x + 2 * di:
                    d[sorted_xs[i + j]] -= d[x]
                else:
                    break
                j += 1
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
n, D, a = map(int, input().split())
tg = []
for _ in range(n):
    x, h = map(int, sys.stdin.readline().split())
    c = h // a
    if h % a > 0:
        c+=1
    tg.append([x, c])

class BIT:
    def __init__(self, n):
        self.n = n
        self.N = 1 << n.bit_length()
        self.data = [0] * (self.N +1)

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

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

    def search(self, w):
        if w <= 0:
            return 0
        x = 0
        k = self.N >> 1
        while k > 0:
            if x+k <= self.N and self.data[x+k] < w:
                w -= self.data[x+k]
                x += k
            k = k >> 1
        return x+1

    def len(self):
        return self.data[self.N]

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, D, A, XH):
    XH.sort()
    X = [x for x, _ in XH]
    H = [h for _, h in XH]

    ans = 0
    for i in range(N):
        if H[i] <= 0:
            continue
        x = X[i]
        h = H[i]
        n = -(-h // A)
        ans += n
        l = bisect.bisect_right(X, x)
        r = bisect.bisect_left(X, x+2*D)
        for j in range(l, min(r+1, N)):
            H[j] -= n*A

    return ans


def main():
    N, D, A = read_int_n()
    XH = [read_int_n() for _ in range(N)]
    print(slv(N, D, A, XH))


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
totalDamage = 0
import collections
q=collections.deque()
for i in range(n):
    x,h = xh[i]
    if q and q[0][0] < x:
        _,dam = q.popleft()
        totalDamage -= dam
    h -=totalDamage
    if h <= 0:
        continue
    num = (h + a -1) //a
    ans += num
    dam = num*a
    totalDamage += dam
    q.append((x+2*d,dam))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n, D, a = map(int, input().split())
tg = []
for _ in range(n):
    x, h = map(int, sys.stdin.readline().split())
    c = h // a
    if h % a > 0:
        c+=1
    tg.append([x, c])

class BIT:
    def __init__(self, n):
        self.n = n
        self.N = 1 << n.bit_length()
        self.data = [0] * (self.N +1)

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

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

    def search(self, w):
        if w <= 0:
            return 0
        x = 0
        k = self.N >> 1
        while k > 0:
            if x+k <= self.N and self.data[x+k] < w:
                w -= self.data[x+k]
                x += k
            k = k >> 1
        return x+1

    def len(self):
        return self.data[self.N]

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

Submission status: Wrong Answer

Solution code:
import heapq
n,d,a=map(int,input().split())
xh=[tuple(map(int,input().split())) for _ in range(n)]
xh.sort()
ans=0
while xh:
  x,h=heapq.heappop(xh)
  c=h//a+bool(h%a)
  b=a*c
  ans+=c
  t=x+2*d
  pool=[]
  while True:
    if not xh:
      break
    y,z=heapq.heappop(xh)
    if y < t:
      if z>b:
        z-=b
        pool.append((y,z))
    else:
      pool.append((y,z))
      break
  for i in pool:
    heapq.heappush(xh,i)
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
totalDamage = 0
import collections
q=collections.deque()
for i in range(n):
    x,h = xh[i]
    if q and q[0][0] < x:
        _,dam = q.popleft()
        totalDamage -= dam
    h -=totalDamage
    num = (h + a -1) //a
    ans += num
    dam = num*a
    totalDamage += dam
    q.append((x+2*d,dam))

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import bisect
import sys
input = sys.stdin.readline
from collections import defaultdict
class Bit:
  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
n,d,a = map(int,input().split())
xh = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
  xh[i][1] = (xh[i][1]+a-1)//a
xh.sort()
x = [xh[i][0] for i in range(n)]
remain = [xh[i][1] for i in range(n)]
ans = 0
bit = Bit(n+1)

for i in range(n):
  print(i,bit.sum(i+1),remain[i],ans)
  if bit.sum(i+1) >= remain[i]:
    continue
  br = bisect.bisect_right(x,x[i]+2*d)
  y = remain[i]-bit.sum(i+1)
  ans += y
  bit.add(i+1,y)
  bit.add(br+1,-y)
print(ans)