Problem:


Score : 600 points

Problem Statement

Silver Fox is fighting with N monsters.

The monsters are standing in a row, and we can assume them to be standing on a number line. The i-th monster, standing at the coordinate X_i, has the health of H_i.

Silver Fox can use bombs to attack the monsters.
Using a bomb at the coordinate x decreases the healths of all monsters between the coordinates x-D and x+D (inclusive) by A.
There is no way other than bombs to decrease the monster's health.

Silver Fox wins when all the monsters' healths become 0 or below.

Find the minimum number of bombs needed to win.

Constraints

1 \leq N \leq 2 \times 10^5

0 \leq D \leq 10^9

1 \leq A \leq 10^9

0 \leq X_i \leq 10^9

1 \leq H_i \leq 10^9

X_i are distinct.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N D A
X_1 H_1
:
X_N H_N

Output

Print the minimum number of bombs needed to win.

Sample Input 1

3 3 2
1 2
5 4
9 2

Sample Output 1

2

First, let us use a bomb at the coordinate 4 to decrease the first and second monsters' health by 2.

Then, use a bomb at the coordinate 6 to decrease the second and third monsters' health by 2.

Now, all the monsters' healths are 0.
We cannot make all the monsters' health drop to 0 or below with just one bomb.

Sample Input 2

9 4 1
1 5
2 4
3 3
4 2
5 1
6 2
7 3
8 4
9 5

Sample Output 2

5

We should use five bombs at the coordinate 5.

Sample Input 3

3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000

Sample Output 3

3000000000

Watch out for overflow.



Sample input:
3 3 2
1 2
5 4
9 2


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

class segTree:
  inf = 1e10
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
    s.D = [0] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def get(s, l, r):
    s.down(l)
    if l != r:
      s.down(r)
    return s.gets(l, r, 0, 0, s.N - 1)
  def gets(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.gets(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.gets(l, r , 2 * k + 1, kl, t)
    return s.do(s.gets(l, r , 2 * k + 1, kl,t),
              s.gets(l, r , 2 * k + 2, t + 1, kr))
  def add(s, l, r, v):
    s.adds(l, r, v, 0, 0, s.N - 1)
  def adds(s, l, r, v, k, kl, kr):
    if k >= 2 * s.N - 1: return
    if l <= kl and kr <= r:
      s.D[k] += v
      return
    if kl <= r and l <= kr:
      t = (kl + kr) // 2
      s.adds(l, r, v, 2 * k + 1, kl, t)
      s.adds(l, r, v, 2 * k + 2, t + 1, kr)
  def down(s, x):
    k, kl, kr = 0, 0, s.N - 1
    while True:
      v = s.D[k]
      s.T[k] += v
      s.D[k] = 0
      t = (kl + kr) // 2
      if 2 * k + 1 >= 2 * s.N - 1: return
      s.D[2 * k + 1] += v
      s.D[2 * k + 2] += v
      if x <= t:
        k = 2 * k + 1
        kr = t
      else:
        k = 2 * k + 2
        kl = t + 1
  
N, D, A = list(map(int, input().split()))
XH = [list(map(int, input().split())) for _ in range(N)]

XH.sort()
H = [XH[i][1] for i in range(N)]

T = segTree(N)
T.set(H)

p = 0
ans = 0
for i in range(N):
  for j in range(p + 1, N):
    if XH[j][0] > XH[i][0] + D * 2:
      p = j - 1
      break
    else:
      p = N - 1
  t = (T.get(i, i) - 1) // A + 1
  if t <= 0: continue
  ans += t
  T.add(i, p, -t * A)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

class segTree:
  inf = 1e10
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
    s.D = [0] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def get(s, l, r):
    s.down(l)
    if l != r:
      s.down(r)
    return s.gets(l, r, 0, 0, s.N - 1)
  def gets(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.gets(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.gets(l, r , 2 * k + 1, kl, t)
    return s.do(s.gets(l, r , 2 * k + 1, kl,t),
              s.gets(l, r , 2 * k + 2, t + 1, kr))
  def add(s, l, r, v):
    s.adds(l, r, v, 0, 0, s.N - 1)
  def adds(s, l, r, v, k, kl, kr):
    if k >= 2 * s.N - 1: return
    if l <= kl and kr <= r:
      s.D[k] += v
      return
    if kl <= r and l <= kr:
      t = (kl + kr) // 2
      s.adds(l, r, v, 2 * k + 1, kl, t)
      s.adds(l, r, v, 2 * k + 2, t + 1, kr)
  def down(s, x):
    s.downs(x, 0, 0, s.N - 1)
  def downs(s, x, k, kl, kr):
    v = s.D[k]
    s.T[k] += v
    s.D[k] = 0
    t = (kl + kr) // 2
    if 2 * k + 1 >= 2 * s.N - 1: return
    s.D[2 * k + 1] += v
    s.D[2 * k + 2] += v
    if x <= t:
      s.downs(x, 2 * k + 1, kl, t)
    else:
      s.downs(x, 2 * k + 2, t + 1, kr)
      

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

XH.sort()
H = [XH[i][1] for i in range(N)]

T = segTree(N)
T.set(H)

p = 0
ans = 0
for i in range(N):
  for j in range(p + 1, N):
    if XH[j][0] > XH[i][0] + D * 2:
      p = j - 1
      break
    else:
      p = N - 1
  t = (T.get(i, i) - 1) // A + 1
  if t <= 0: continue
  ans += t
  T.add(i, p, -t * A)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N,D,A = map(int,input().split())
mons = []
X = []; H = []
need = [0]*N

for _ in range(N):
    x,h = map(int,input().split())
    mons.append([x,h])
mons = sorted(mons)

for i in range(N):
    X.append(mons[i][0]); H.append(mons[i][1])
    need[i] = mons[i][1] // A
    if mons[i][1] % A != 0: need[i] += 1

eliminated = 0
target = 0
ans = 0
while eliminated < N:
    for i in range(target,N):
        if need[i] > 0:
            target = i
            break
        else:
            eliminated += 1
    need_bomb = need[target]
    bomb_range = bisect.bisect_right(X,X[target] + 2*D)
    for i in range(target,bomb_range):
        need[i] -= need_bomb
    ans += need_bomb
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

class segTree:
  inf = 1e10
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
    s.D = [0] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def get(s, l, r):
    s.down(l)
    s.down(r)
    return s.gets(l, r, 0, 0, s.N - 1)
  def gets(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.gets(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.gets(l, r , 2 * k + 1, kl, t)
    return s.do(s.gets(l, r , 2 * k + 1, kl,t),
              s.gets(l, r , 2 * k + 2, t + 1, kr))
  def add(s, l, r, v):
    s.adds(l, r, v, 0, 0, s.N - 1)
  def adds(s, l, r, v, k, kl, kr):
    if k >= 2 * s.N - 1: return
    if l <= kl and kr <= r:
      s.D[k] += v
      return
    if kl <= r and l <= kr:
      t = (kl + kr) // 2
      s.adds(l, r, v, 2 * k + 1, kl, t)
      s.adds(l, r, v, 2 * k + 2, t + 1, kr)
  def down(s, x):
    s.downs(x, 0, 0, s.N - 1)
  def downs(s, x, k, kl, kr):
    v = s.D[k]
    s.T[k] += v
    s.D[k] = 0
    t = (kl + kr) // 2
    if 2 * k + 1 >= 2 * s.N - 1: return
    s.D[2 * k + 1] += v
    s.D[2 * k + 2] += v
    if x <= t:
      s.downs(x, 2 * k + 1, kl, t)
    else:
      s.downs(x, 2 * k + 2, t + 1, kr)
      

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

XH.sort()
H = [XH[i][1] for i in range(N)]

T = segTree(N)
T.set(H)

p = 0
ans = 0
for i in range(N):
  for j in range(p + 1, N):
    if XH[j][0] > XH[i][0] + D * 2:
      p = j - 1
      break
    else:
      p = N - 1
  t = (T.get(i, i) - 1) // A + 1
  if t <= 0: continue
  ans += t
  T.add(i, p, -t * A)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
from bisect import bisect_right

def update(x, v):
  while x <= N:
    fw[x] += v
    x += x & -x

def s(x):
  res = 0
  while x:
    res += fw[x]
    x -= x & -x
  return res


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

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

ans = 0
for i in range(N):
  h = s(i + 1) - s(0)
  if monsters[i][1] + h > 0:
    num_bomb = ceil((monsters[i][1] + h) / A)
    ans += num_bomb

    k = bisect_right(monsters, [monsters[i][0] + 2*D, 10**9])
    update(i + 1, -(num_bomb * A))
    update(k + 1, num_bomb * A)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
from operator import itemgetter
import bisect

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) 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 II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

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

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

    def reset(self):
        t = self.tree
        for i in range(len(t)):
            t[i] = 0

class RBit:
    def __init__(self, n, B0 = None):
        self.BI0 = B0 or Bit(n+10)
        self.BI1 = Bit(n+10)

    def add(self, x, left, right):
        self.BI0.add(left, -x*(left-1))
        self.BI1.add(left, x)
        self.BI0.add(right+1, x*right)
        self.BI1.add(right+1, -x)

    def sum(self, i):
        return self.BI1.sum(i)*i + self.BI0.sum(i)

    def get(self, i):
        return self.sum(i) - (i and self.sum(i-1))

N,D,A=LI()
# RB = RBit(N+10)
PS=[]
HPS=[]
INI=Bit(N+10)
LIN = [LI() for i in range(N)]
LIN.sort(key = itemgetter(0))
for i in range(N):
    pos, hp = LIN[i]
    PS.append(pos)
    INI.add(i, hp)

RB=RBit(N+10, INI)

res = 0
for i in range(N):
    hp = RB.get(i)
    # print(hp)
    if hp > 0:
        atc_cnt = hp // A + (1 if hp%A else 0)
        left = PS[i]
        right = bisect.bisect_right(PS, PS[i]+2*D)-1
        RB.add(-A*atc_cnt, i, right)
        res += atc_cnt

print(res)

Submission status: Time Limit Exceeded

Solution code:
def sol():
    import sys
    input=sys.stdin.readline
    n,d,a=map(int,input().split())
    dd=d*2+1
    w=[[0,0] for i in range(n)]
    for i in range(n):
        w[i][0],w[i][1]=map(int,input().split())
    w.sort()
    ans=0
    p=[0,0,0] #left,left_atack,ans
    i=-1
    while 1:
        i+=1
        if i>=n: break
        if w[i][1]<=0: continue
        k=(w[i][1]+a-1)//a
        p[0]=w[i][0]
        p[1]=k*a
        p[2]+=k
        w[i][1]-=p[1]
        j=0
        zz=-1
        while 1:
            j+=1
            if i+j>n-1 or w[i+j][0]>p[0]+dd-1:
                break
            elif i+j<=n-1 and w[i+j][0]<=p[0]+dd-1:
                w[i+j][1]-=p[1]
                if w[i+j][1]>0 and zz==-1:
                    zz=j
        if zz!=-1:
            i+=zz-1
    print(p[2])
if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
def sol():
    import sys
    input=sys.stdin.readline
    n,d,a=map(int,input().split())
    dd=d*2+1
    w=[]
    for i in range(n):
        x,h=map(int,input().split())
        w.append([x,h])
    w.sort()
    ans=0
    p=[0,0,0] #left,left_atack,ans
    i=-1
    while 1:
        i+=1
        if i>=n: break
        if w[i][1]<=0: continue
        p[0]=w[i][0]
        p[1]=((w[i][1]+a-1)//a)*a
        p[2]+=(w[i][1]+a-1)//a
        w[i][1]-=p[1]
        j=0
        zz=-1
        while 1:
            j+=1
            if i+j>n-1 or w[i+j][0]>p[0]+dd-1:
                break
            elif i+j<=n-1 and w[i+j][0]<=p[0]+dd-1:
                w[i+j][1]-=p[1]
                if w[i+j][1]>0 and zz==-1:
                    zz=j
        if zz!=-1:
            i+=zz-1
    print(p[2])
if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
def sol():
    import sys
    input=sys.stdin.readline
    n,d,a=map(int,input().split())
    dd=d*2+1
    w=[]
    for i in range(n):
        x,h=map(int,input().split())
        w.append([x,h])
    w.sort()
    ans=0
    p=[0,0,0] #left,left_atack,ans
    i=-1
    while 1:
        i+=1
        if i>=n: break
        if w[i][1]<=0: continue
        p[0]=w[i][0]
        p[1]=((w[i][1]+a-1)//a)*a
        p[2]+=(w[i][1]+a-1)//a
        w[i][1]-=p[1]
        j=0
        while 1:
            j+=1
            if i+j>n-1 or w[i+j][0]>p[0]+dd-1:
                break
            elif i+j<=n-1 and w[i+j][0]<=p[0]+dd-1:
                w[i+j][1]-=p[1]
    print(p[2])
if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
def sol():
    n,d,a=map(int,input().split())
    dd=d*2+1
    w=[]
    for i in range(n):
        x,h=map(int,input().split())
        w.append([x,h])
    w.sort()
    ans=0
    p=[0,0,0] #left,left_atack,ans
    i=-1
    while 1:
        i+=1
        if i>=n: break
        if w[i][1]<=0: continue
        p[0]=w[i][0]
        p[1]=((w[i][1]+a-1)//a)*a
        p[2]+=(w[i][1]+a-1)//a
        w[i][1]-=p[1]
        j=0
        while 1:
            j+=1
            if i+j>n-1 or w[i+j][0]>p[0]+dd:
                break
            elif i+j<=n-1 and w[i+j][0]<=p[0]+dd-1:
                w[i+j][1]-=p[1]
    print(p[2])

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
import sys
input = sys.stdin.buffer.readline

class SegmentTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size, initValue, cmpFunc):
        self.size = 1 << (size.bit_length())  # 完全二分木にする
        self.data = [initValue] * (2 * self.size - 1)
        self.initValue = initValue
        self.cmpFunc = cmpFunc

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in range(self.size - 1)[:: -1]:
            self.data[i] = self.cmpFunc(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = self.cmpFunc(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = self.initValue
        while L < R:
            if R & 1:
                R -= 1
                ret = self.cmpFunc(ret, self.data[R - 1])
            if L & 1:
                ret = self.cmpFunc(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

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

tree = SegmentTree(N + 1, 0, lambda a, b: a + b)

ans = 0
for i, (x, h) in enumerate(XH):
    cnt = tree.query(0, i + 1)
    h -= cnt * A

    if h <= 0:
        continue

    ness = -(-h // A)
    ans += ness
    tree.update(i, tree.query(i, i + 1) + ness)
    j = bisect_right(X, x + 2 * D)
    tree.update(j, tree.query(j, j + 1) - ness)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A=map(int,input().split())
L=[]
for i in range(N):
    x,h=map(int,input().split())
    L.append([x,h])
L.sort()

import math

ans=0
S=0
P=0
RL=[10**10]
RC=[0]
cnt=0
for i in range(N):
    while RL[P]<L[i][0]:
        cnt+=RC[P]
        P+=1
    if L[i][1]-S+cnt>0:
        ans+=math.ceil((L[i][1]-S+cnt)/A)
        RL=RL[:len(RL)-1]
        RC=RC[:len(RC)-1]
        RL+=[L[i][0]+2*D]+[10**10]
        RC+=[math.ceil((L[i][1]-S+cnt)/A)*A]+[0]
        S+=math.ceil((L[i][1]-S+cnt)/A)*A
    #print(i,ans,P)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

class SegmentTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size, initValue, cmpFunc):
        self.size = 1 << (size.bit_length())  # 完全二分木にする
        self.data = [initValue] * (2 * self.size - 1)
        self.initValue = initValue
        self.cmpFunc = cmpFunc

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in range(self.size - 1)[:: -1]:
            self.data[i] = self.cmpFunc(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = self.cmpFunc(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = self.initValue
        while L < R:
            if R & 1:
                R -= 1
                ret = self.cmpFunc(ret, self.data[R - 1])
            if L & 1:
                ret = self.cmpFunc(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

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

tree = SegmentTree(N + 1, 0, lambda a, b: a + b)

ans = 0
for i, (x, h) in enumerate(XH):
    cnt = tree.query(0, i + 1)
    h -= cnt * A

    if h <= 0:
        continue

    ness = -(-h // A)
    ans += ness
    tree.update(i, tree.query(i, i + 1) + ness)
    j = bisect_right(X, x + 2 * D)
    tree.update(j, tree.query(j, j + 1) - ness)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, d, a = map(int, input().split())
xh = sorted([list(map(int,input().split())) for _ in range(n)],key=lambda x:x[0])


ans = 0
b = 0


while b < n:
    while xh[b][1] <= 0:
        if b == n-1:
            print(ans)
            exit()
        b += 1
    k = -(-xh[b][1]//a)
    for i in range(b ,min(b+ d*2+1,n)):
        if  xh[i][0] <= xh[b][0] + 2*d:
            xh[i][1] -= k*a
        else:
            break
    ans += k
    
    #TLE

Submission status: Time Limit Exceeded

Solution code:
n, d, a = map(int, input().split())
xh = sorted([list(map(int,input().split())) for _ in range(n)],key=lambda x:x[0])


ans = 0
b = 0


def f(h,a):
    if h%a:
        return h//a + 1
    else:
        return h//a


while b < n:
    while xh[b][1] <= 0:
        if b == n-1:
            print(ans)
            exit()
        b += 1
    k = f(xh[b][1],a)
    for i in range(b ,min(b+ d*2+1,n)):
        if  xh[i][0] <= xh[b][0] + 2*d:
            xh[i][1] -= k*a
        else:
            break
    ans += k
    
    #TLE

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect
N, D, A = map(int, input().split())
lst = []
lst_1 = []
lst_2 = []

for i in range(N):
	X, H = map(int, input().split())
	lst.append([X, math.ceil(H / A)])
	
lst.sort(key = lambda x : x[0])

for i in range(N):
	lst_1.append(lst[i][0])
	lst_2.append(lst[i][1])
	
ans = 0

while lst_1:
	x = lst_1.pop(0)
	y = lst_2.pop(0)
	if y <= 0: continue
	for i in range(bisect.bisect_right(lst_1, x + 2 * D)):
		lst_2[i] -= y
	ans += y
		
		
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

n, d, a = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
m.sort()
x = [mm[0] for mm in m]
h = [mm[1] for mm in m]
y = [None for _ in range(n)]
idx = 0
ans = 0
hh = [0 for _ in range(n)]
for i in range(n):
    k = -((hh[i] - h[i]) // a)
    if k < 0:
        continue
    ans += k
    y = bisect_right(x, x[i] + 2 * d, lo=i)
    for j in range(i, y):
        hh[j] += k * a
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

n, d, a = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
m.sort()
x = [mm[0] for mm in m]
h = [mm[1] for mm in m]
y = [None for _ in range(n)]
for i in range(n):
    y[i] = bisect_right(x, x[i] + 2 * d)

idx = 0
ans = 0
hh = [0 for _ in range(n)]
for i in range(n):
    k = -((hh[i] - h[i]) // a)
    if k < 0:
        continue
    ans += k
    for j in range(i, y[i]):
        hh[j] += k * a
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, d, a = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
m.sort(key=lambda x: x[0])
idx = 0
ans = 0
while True:
    k = -(-m[idx][-1] // a)
    m[idx][-1] -= k * a
    dd = m[idx][0] + 2 * d
    ans += k
    is_update = False
    for i in range(idx + 1, n):
        if dd < m[i][0]:
            if not is_update:
                idx = i
            break
        m[i][-1] -= k * a
        if not is_update and m[i][-1] > 0:
            idx = i
            is_update = True
    else:
        if not is_update:
            break
print(ans)

Submission status: Time Limit Exceeded

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

xh.sort()

ends = []
start = 0
# loop = 0
for base in range(n):
    for start, (x, _) in enumerate(xh[start:], start):
        # loop += 1
        if x > xh[base][0] + 2 * d:
            # start -= 1 # in range
            break
    else:
        start = n
    ends.append(start)
#     print(start)
# print(ends)
# print(loop, "loop")

cnt = [0] * (n + 1)

hist = 0
ans = 0
for i, end in enumerate(ends):
    hist += cnt[i]
    atk = (max(0, xh[i][1] - hist * a) + a - 1) // a
    # print(atk, "atk", hist, end=" ")
    ans += atk
    hist += atk

    cnt[i] += atk
    cnt[end] -= atk
    # print(":", cnt)

print(ans)
# print(cnt)
#
# import functools
# import operator
# print(functools.reduce(operator.add, cnt[:-1]), ans)

Submission status: Time Limit Exceeded

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 update(self,left,right,f):
        left += self.n
        right += self.n
        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])

r = [0 for _ in range(N)]
for i in range(N):
    r[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,r[i],-A*cnt)
    ans += cnt

print(ans)

Submission status: Time Limit Exceeded

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

xh.sort()

ends = []
start = 0
for base in range(n):
    for start, (x, _) in enumerate(xh[start:], start):
        if x > xh[base][0] + 2 * d:
            # start -= 1 # in range
            break
    else:
        start = n
    ends.append(start)
#     print(start)
# print(ends)

cnt = [0] * (n + 1)

hist = 0
ans = 0
for i, end in enumerate(ends):
    hist += cnt[i]
    atk = (max(0, xh[i][1] - hist * a) + a - 1) // a
    # print(atk, "atk", hist, end=" ")
    ans += atk
    hist += atk

    cnt[i] += atk
    cnt[end] -= atk
    # print(":", cnt)

print(ans)
# print(cnt)
#
# import functools
# import operator
# print(functools.reduce(operator.add, cnt[:-1]), ans)

Submission status: Time Limit Exceeded

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


ans = 0
b = 0


def f(h,a):
    if h%a:
        return h//a + 1
    else:
        return h//a


while b < n:
    while xh[b][1] <= 0:
        if b == n-1:
            print(ans)
            exit()
        b += 1
    k = f(xh[b][1],a)
    for i in range(b ,min(b+ d*2+1,n)):
        if  xh[i][0] <= xh[b][0] + 2*d:
            xh[i][1] -= k*a
        else:
            break
    ans += k

Submission status: Time Limit Exceeded

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)])
L1 = sorted(L1)
ans = 0
j = 1
L2 = [-1]*N
for i in range(N):
    lim = L1[i][0] + 2*D
    for k in range(j,N):
        if L1[k][0] > lim:
            L2[i] = k-1
            j = k-1
            break
        elif k == N-1:
            L2[i] = N-1
            j = N-1
for i in range(N):
    x,h = L1[i] 
    if h > 0:
        ans += h
        for j in range(i,L2[i]+1):
            L1[j][1] -= h
print(ans)