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
input = sys.stdin.readline
n, d, a = map(int, input().split())
xh = sorted([tuple(map(int, input().split()))for _ in range(n)])

x, h = xh[0]
cnt = -(-h//a)
ans = cnt
bomb_list = [(x+2*d, cnt*a)]
effective_bomb_idx = 0
for x, h in xh[1:]:
    idx = effective_bomb_idx
    for bomb in bomb_list[idx:]:
        area, damage = bomb
        if x <= area:
            h -= damage
            if h <= 0:
                break
        else:
            effective_bomb_idx += 1

    if 0 < h:
        cnt = -(-h//a)
        bomb_list.append((x+2*d, cnt*a))
        ans += cnt

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, d, a = map(int, input().split())
xh = sorted([tuple(map(int, input().split()))for _ in range(n)])

x, h = xh[0]
cnt = -(-h//a)
ans = cnt
bomb_list = [(x+2*d, cnt*a)]
effective_bomb_idx = 0
for x, h in xh[1:]:
    for bomb in bomb_list[effective_bomb_idx:]:
        area, damage = bomb
        if x <= area:
            h -= damage
        else:
            effective_bomb_idx += 1

    if 0 < h:
        cnt = -(-h//a)
        bomb_list.append((x+2*d, cnt*a))
        ans += cnt

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
input=sys.stdin.readline
n,d,a=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()

LV=(n-1).bit_length()
N0=2**LV
data=[0]*(2*N0)
lazy=[0]*(2*N0)

def gindex(l,r):
  L=l+N0;R=r+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(*ids):
  for i in reversed(ids):
    v=lazy[i-1]
    if not v:
      continue
    lazy[2*i-1]+=v;lazy[2*i]+=v
    data[2*i-1]+=v;data[2*i]+=v
    lazy[i-1]=0

def update(l,r,x):
  L=N0+l;R=N0+r
  while L<R:
    if R&1:
      R-=1
      lazy[R-1]+=x;data[R-1]+=x
    if L&1:
      lazy[L-1]+=x; data[L-1]+=x
      L+=1
    L>>=1;R>>=1
  for i in gindex(l,r):
    data[i-1]=min(data[2*i-1],data[2*i])+lazy[i-1]

def query(l,r):
  propagates(*gindex(l,r))
  L=N0+l;R=N0+r

  s=10**9+1
  while L<R:
    if R&1:
      R-=1
      s=min(s,data[R-1])
    if L&1:
      s=min(s,data[L-1])
      L+=1
    L>>=1; R>>=1
  return s

x=[]
for i in range(n):
  x.append(l[i][0])
  update(i,i+1,l[i][1])

Right=[]
for i in range(n):
  Right.append(bisect.bisect_right(x,x[i]+2*d))

p=0
ans=0
while p<n:
  Q=query(p,p+1)
  update(p,Right[p],-((Q+a-1)//a)*a)
  ans+=(Q+a-1)//a
  p=min(p+1,n-1)
  while query(p,p+1)<=0:
    p+=1
    if p==n:
      break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
input=sys.stdin.readline
n,d,a=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()

LV=(n-1).bit_length()
N0=2**LV
data=[0]*(2*N0)
lazy=[0]*(2*N0)

def gindex(l,r):
  L=l+N0;R=r+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(*ids):
  for i in reversed(ids):
    v=lazy[i-1]
    if not v:
      continue
    lazy[2*i-1]+=v;lazy[2*i]+=v
    data[2*i-1]+=v;data[2*i]+=v
    lazy[i-1]=0

def update(l,r,x):
  L=N0+l;R=N0+r
  while L<R:
    if R&1:
      R-=1
      lazy[R-1]+=x;data[R-1]+=x
    if L&1:
      lazy[L-1]+=x; data[L-1]+=x
      L+=1
    L>>=1;R>>=1
  for i in gindex(l,r):
    data[i-1]=min(data[2*i-1],data[2*i])+lazy[i-1]

def query(l,r):
  propagates(*gindex(l,r))
  L=N0+l;R=N0+r

  s=10**9+1
  while L<R:
    if R&1:
      R-=1
      s=min(s,data[R-1])
    if L&1:
      s=min(s,data[L-1])
      L+=1
    L>>=1; R>>=1
  return s

x=[]
for i in range(n):
  x.append(l[i][0])
  update(i,i+1,l[i][1])

Right=[]
for i in range(n):
  Right.append(bisect.bisect_right(x,x[i]+2*d))

p=0
ans=0
while p<n:
  Q=query(p,p+1)
  update(p,Right[p],-((Q+a-1)//a)*a)
  ans+=(Q+a-1)//a
  if p==n-1:
    break
  p+=1
  while query(p,p+1)<=0:
    p+=1
    if p==n:
      break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
input=sys.stdin.readline
n,d,a=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()

LV=(n-1).bit_length()
N0=2**LV
data=[0]*(2*N0)
lazy=[0]*(2*N0)

def gindex(l,r):
  L=l+N0;R=r+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(*ids):
  for i in reversed(ids):
    v=lazy[i-1]
    if not v:
      continue
    lazy[2*i-1]+=v;lazy[2*i]+=v
    data[2*i-1]+=v;data[2*i]+=v
    lazy[i-1]=0

def update(l,r,x):
  L=N0+l;R=N0+r
  while L<R:
    if R&1:
      R-=1
      lazy[R-1]+=x;data[R-1]+=x
    if L&1:
      lazy[L-1]+=x; data[L-1]+=x
      L+=1
    L>>=1;R>>=1
  for i in gindex(l,r):
    data[i-1]=min(data[2*i-1],data[2*i])+lazy[i-1]

def query(l,r):
  propagates(*gindex(l,r))
  L=N0+l;R=N0+r

  s=10**9+1
  while L<R:
    if R&1:
      R-=1
      s=min(s,data[R-1])
    if L&1:
      s=min(s,data[L-1])
      L+=1
    L>>=1; R>>=1
  return s

def main():
  x=[]
  for i in range(n):
    x.append(l[i][0])
    update(i,i+1,l[i][1])

  Right=[]
  for i in range(n):
    Right.append(bisect.bisect_right(x,x[i]+2*d))

  p=0
  ans=0
  while p<n:
    x=query(p,p+1)
    update(p,Right[p],-((x+a-1)//a)*a)
    ans+=(x+a-1)//a
    while query(p,p+1)<=0:
      p+=1
      if p==n:
        break
  print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
input=sys.stdin.readline
n,d,a=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
x=[];h=[]
for i in range(n):
  x.append(l[i][0])
  h.append(l[i][1])

Right=[]
for i in range(n):
  Right.append(bisect.bisect_right(x,x[i]+2*d))

LV=(n-1).bit_length()
N0=2**LV
data=[0]*(2*N0)
lazy=[0]*(2*N0)

def gindex(l,r):
  L=l+N0;R=r+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(*ids):
  for i in reversed(ids):
    v=lazy[i-1]
    if not v:
      continue
    lazy[2*i-1]+=v;lazy[2*i]+=v
    data[2*i-1]+=v;data[2*i]+=v
    lazy[i-1]=0

def update(l,r,x):
  L=N0+l;R=N0+r
  while L<R:
    if R&1:
      R-=1
      lazy[R-1]+=x;data[R-1]+=x
    if L&1:
      lazy[L-1]+=x; data[L-1]+=x
      L+=1
    L>>=1;R>>=1
  for i in gindex(l,r):
    data[i-1]=min(data[2*i-1],data[2*i])+lazy[i-1]

def query(l,r):
  propagates(*gindex(l,r))
  L=N0+l;R=N0+r

  s=10**9+1
  while L<R:
    if R&1:
      R-=1
      s=min(s,data[R-1])
    if L&1:
      s=min(s,data[L-1])
      L+=1
    L>>=1; R>>=1
  return s

for i in range(n):
  update(i,i+1,h[i])

p=0
ans=0
while p<n:
  x=query(p,p+1)
  update(p,Right[p],-((x+a-1)//a)*a)
  ans+=(x+a-1)//a
  while query(p,p+1)<=0:
    p+=1
    if p==n:
      break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
input=sys.stdin.readline
n,d,a=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
x=[];h=[]
for i in range(n):
  x.append(l[i][0])
  h.append(l[i][1])

Right=[]
for i in range(n):
  Right.append(bisect.bisect_right(x,x[i]+2*d))

LV=(n-1).bit_length()
N0=2**LV
data=[0]*(2*N0)
lazy=[0]*(2*N0)

def gindex(l,r):
  L=l+N0;R=r+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(*ids):
  for i in reversed(ids):
    v=lazy[i-1]
    if not v:
      continue
    lazy[2*i-1]+=v;lazy[2*i]+=v
    data[2*i-1]+=v;data[2*i]+=v
    lazy[i-1]=0

def update(l,r,x):
  L=N0+l;R=N0+r
  while L<R:
    if R&1:
      R-=1
      lazy[R-1]+=x;data[R-1]+=x
    if L&1:
      lazy[L-1]+=x; data[L-1]+=x
      L+=1
    L>>=1;R>>=1
  for i in gindex(l,r):
    data[i-1]=min(data[2*i-1],data[2*i])+lazy[i-1]

def query(l,r):
  propagates(*gindex(l,r))
  L=N0+l;R=N0+r

  s=999999999999999999
  while L<R:
    if R&1:
      R-=1
      s=min(s,data[R-1])
    if L&1:
      s=min(s,data[L-1])
      L+=1
    L>>=1; R>>=1
  return s

for i in range(n):
  update(i,i+1,h[i])

p=0
ans=0
while p<n:
  x=query(p,p+1)
  update(p,Right[p],-((x+a-1)//a)*a)
  ans+=(x+a-1)//a
  while query(p,p+1)<=0:
    p+=1
    if p==n:
      break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
input=sys.stdin.readline
n,d,a=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
x=[];h=[]
for i in range(n):
  x.append(l[i][0])
  h.append(l[i][1])

Right=[]
for i in range(n):
  Right.append(bisect.bisect_right(x,x[i]+2*d))

LV=(n-1).bit_length()
N0=2**LV
data=[0]*(2*N0)
lazy=[0]*(2*N0)

def gindex(l,r):
  L=l+N0;R=r+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(*ids):
  for i in reversed(ids):
    v=lazy[i-1]
    if not v:
      continue
    lazy[2*i-1]+=v;lazy[2*i]+=v
    data[2*i-1]+=v;data[2*i]+=v
    lazy[i-1]=0

def update(l,r,x):
  L=N0+l;R=N0+r
  while L<R:
    if R&1:
      R-=1
      lazy[R-1]+=x;data[R-1]+=x
    if L&1:
      lazy[L-1]+=x; data[L-1]+=x
      L+=1
    L>>=1;R>>=1
  for i in gindex(l,r):
    data[i-1]=min(data[2*i-1],data[2*i])+lazy[i-1]

def query(l,r):
  propagates(*gindex(l,r))
  L=N0+l;R=N0+r

  s=float('inf')
  while L<R:
    if R&1:
      R-=1
      s=min(s,data[R-1])
    if L&1:
      s=min(s,data[L-1])
      L+=1
    L>>=1; R>>=1
  return s

for i in range(n):
  update(i,i+1,h[i])

p=0
ans=0
while p<n:
  x=query(p,p+1)
  update(p,Right[p],-((x+a-1)//a)*a)
  ans+=(x+a-1)//a
  while query(p,p+1)<=0:
    p+=1
    if p==n:
      break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline().strip()

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

x = []
h = {} # x:h
for _ in range(n):
    i, j = map(int, input().split())
    x.append(i)
    h[i] = j
x.sort()
x.append(x[-1] + 2*d + 1)

# attackで累積和を用いる
ans = 0
attack = [0 for _ in range(n+1)]
for i in range(n):
    attack[i] += attack[i-1]
    if attack[i] >= h[x[i]]:
        continue

    if (h[x[i]] - attack[i]) % a == 0:
        j = (h[x[i]] - attack[i]) // a
    else:
        j = (h[x[i]] - attack[i]) // a + 1
    attack[i] += a * j
    ans += j

    # 二分探索で、x[y] > x[i] + 2*d、を満たす最小のyを求める
    # start <= y <= stop
    start = i + 1
    stop = n
    k = stop - start + 1
    while k > 1:
        if x[start + k//2 - 1] <= x[i] + 2*d:
            start += k//2
        else:
            stop = start + k//2 - 1
        k = stop - start + 1
    attack[start] -= a * j

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline().strip()

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

x = []
h = {} # x:h
for _ in range(n):
    i, j = map(int, input().split())
    x.append(i)
    h[i] = j
x.sort()

ans = 0
attack = [0 for _ in range(n)]
for i in range(n):
    attack[i] += attack[i-1]
    if attack[i] >= h[x[i]]:
        continue

    if (h[x[i]] - attack[i]) % a == 0:
        k = (h[x[i]] - attack[i]) // a
    else:
        k = (h[x[i]] - attack[i]) // a + 1
    attack[i] += a * k
    ans += k

    for j in range(i+1, n):
        if x[j] > x[i] + 2*d:
            attack[j] -= a * k
            break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline().strip()

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

x = []
h = {} # x:h
for _ in range(n):
    i, j = map(int, input().split())
    x.append(i)
    h[i] = j
x.sort()

ans = 0
todo = [0 for _ in range(n)] #未処理は0、処理済は1
for i in range(n):
    if todo[i] == 0:
        if h[x[i]] % a == 0:
            k = h[x[i]] // a
        else:
            k = h[x[i]] // a + 1
        ans += k
        todo[i] = 1
        for j in range(i+1, n):
            if x[j] <= x[i] + 2*d:
                if todo[j] == 0:
                    if h[x[j]] <= a * k:
                        todo[j] = 1
                    else:
                        h[x[j]] -= a * k
            else:
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

I = np.array(read().split(), np.int64)
X = I[::2]
H = I[1::2]

sort_ind = np.argsort(X)
X = X[sort_ind]
H = H[sort_ind]

atack = np.zeros(N+1)
cover = np.searchsorted(X, X + (2 * D), side = 'right')

ans = 0
cnt = 0
for i in range(N):
	cnt += atack[i]
	H[i] -= cnt
	if H[i] > 0:
		tmp = -(-H[i]//A)
		ans += tmp
		cnt += tmp * A
		atack[cover[i]] -= tmp * A

print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
N = num monsters
A = dmg per bomb
D = distance from bomb
"""

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

from math import ceil
from collections import deque

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

monsters.sort()

def solve(monsters, N, D, A):
    count = 0
    i = 0

    while i < N:
        lm_x, lm_h = monsters[i]
        bombs = ceil(lm_h/A)
        tot_damage = bombs * A
        rm_x = lm_x + 2 * D

        j = i
        while j < N:
            mx, mh = monsters[j]

            if mx > rm_x:
                break

            new_h = mh - tot_damage
            
            # Move pointer
            if new_h <= 0 and i == j:
                i += 1
                j += 1
                continue
            
            # Update values
            monsters[j] = (mx, new_h)

            j += 1

        count += bombs
    
    return count
 
print(solve(monsters, N, D, A))

Submission status: Time Limit Exceeded

Solution code:
"""
N = num monsters
A = dmg per bomb
D = distance from bomb
"""

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

from math import ceil
from collections import deque

monsters = []
for _ in range(N):
    X, h = map(int, input().split())
    monsters.append((X, h))

monsters.sort()

def solve(monsters, N, D, A):
    count = 0
    i = 0

    while i < N:
        lm_x, lm_h = monsters[i]
        bombs = ceil(lm_h/A)
        tot_damage = bombs * A
        rm_x = lm_x + 2 * D

        j = i
        while j < N:
            mx, mh = monsters[j]

            if mx > rm_x:
                break

            new_h = mh - tot_damage
            
            # Move pointer
            if new_h <= 0 and i == j:
                i += 1
            
            # Update values
            monsters[j] = (mx, new_h)

            j += 1

        count += bombs
    
    return count
 
print(solve(monsters, N, D, A))

Submission status: Time Limit Exceeded

Solution code:
"""
N = num monsters
A = dmg per bomb
D = distance from bomb
"""

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

from math import ceil
from collections import deque

monsters = []
for _ in range(N):
    X, h = map(int, input().split())
    monsters.append((X, h))

monsters.sort()
monsters = deque(monsters)

def solve(monsters, N, D, A):
    count = 0

    while monsters:
        lm_x, lm_h = monsters[0]
        bombs = ceil(lm_h/A)
        tot_damage = bombs * A
        rm_x = lm_x + 2 * D

        re_add = []

        while monsters and monsters[0][0] <= rm_x:
            mx, mh = monsters.popleft()
            new_h = mh - tot_damage

            if new_h <= 0:
                continue
            else:
                re_add.append((mx, new_h))
        
        for i in range(len(re_add)-1, -1, -1):
            monsters.appendleft(re_add[i])

        count += bombs
    
    return count
 
print(solve(monsters, N, D, A))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, D, A = map(int, input().split())
d = defaultdict(int)
X = []
for i in range(N):
    x, h = map(int, input().split())
    d[x] = h
    X.append(x)
X.sort()
li = [0] * N
for i in range(N):
    u = N
    l = i
    while u - l > 1:
        m = (u+l)//2
        if X[m] - X[i] > 2*D:
            u = m
        else:
            l = m
    li[i] = l
ans = 0
for i in range(N):
    x = X[i]
    if d[x] > 0:
        m = -(-d[x]//A)
        ans += m
        for j in range(i+1, li[i]+1):
            d[X[j]] -= m*A
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

import math
from collections import deque
    
n,d,a = l_in()
xh = []
for _ in range(n):
    x,h=l_in()
    xh.append((x,math.ceil(h/a)))

xh.sort()
res = 0
currentX = -1
currentH = 0
q=deque()

for x,h in xh:
    while len(q) > 0:
        bx, bh = q[0]
        if bx < x:
            q.popleft()
        else:
            break
    for bx, bh in q:    
        h -= bh
    if h > 0:
        q.append((x+2*d, h))
        res += h

print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
N, D, A = map(int, input().split())
L = 2 * D
I = np.array(sys.stdin.read().split(), np.int64)
X = I[::2]
H = I[1::2]
sort_ind = np.argsort(X)
X = X[sort_ind]
H = H[sort_ind]
S = np.zeros(N+1, np.int64)

atack = 0
ans = 0
for i in range(N):
	atack += S[i]
	H[i] -= atack
	if H[i] > 0:
		atack_cnt = -(-H[i]//A)
		ans += atack_cnt
		tmp = atack_cnt * A
		S[i+1] += tmp
		ind = np.searchsorted(X,X[i]+L+1,side = 'left')
		S[ind] -= tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
N, D, A = map(int, input().split())
L = 2 * D
I = np.array(sys.stdin.read().split(), np.int32)
X = I[::2]
H = I[1::2]
sort_ind = np.argsort(X)
X = X[sort_ind]
H = H[sort_ind]
S = np.zeros(N+1, np.int32)

atack = 0
ans = 0
for i in range(N):
	atack += S[i]
	H[i] -= atack
	if H[i] > 0:
		atack_cnt = -(-H[i]//A)
		ans += atack_cnt
		S[i+1] += atack_cnt * A
		ind = np.searchsorted(X,X[i]+L+1,side = 'left')
		S[ind] -= atack_cnt * A

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
N, D, A = map(int, input().split())
L = 2 * D
I = np.array(sys.stdin.read().split(), np.int64)
X = I[::2]
H = I[1::2]
sort_ind = np.argsort(X)
X = X[sort_ind]
H = H[sort_ind]
S = np.zeros(N+1, np.int64)

atack = 0
ans = 0
for i in range(N):
	atack += S[i]
	H[i] -= atack
	if H[i] > 0:
		atack_cnt = -(-H[i]//A)
		ans += atack_cnt
		S[i+1] += atack_cnt * A
		ind = np.searchsorted(X,X[i]+L+1,side = 'left')
		S[ind] -= atack_cnt * A

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
N, D, A = map(int, input().split())
L = 2 * D
I = np.array(sys.stdin.read().split(), np.int64)
X = I[::2]
H = I[1::2]
sort_ind = np.argsort(X)
X = X[sort_ind]
H = H[sort_ind]
S = np.zeros(N+1)

atack = 0
ans = 0
for i in range(N):
	atack += S[i]
	H[i] -= atack
	if H[i] > 0:
		atack_cnt = -(-H[i]//A)
		ans += atack_cnt
		S[i+1] += atack_cnt * A
		ind = np.searchsorted(X,X[i]+L+1,side = 'left')
		S[ind] -= atack_cnt * A

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 左からgreedyに
N, D, A = lr()
monsters = []
for _ in range(N):
    x, h = lr()
    monsters.append((x, h))

monsters.sort()
bomb = deque()
answer = 0
for x, h in monsters:
    while bomb:
        if bomb[0][0] + D < x:
            bomb.popleft()
        else:
            break
    for place, time in bomb:
        h -= A * time
    if h > 0:
        t = -(-h//A)
        answer += t
        bomb.append((x + D, t))

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect
N, D, A = list(map(int, input().split()))
data = []
for _ in range(N):
    x, h = list(map(int, input().split()))
    data.append((x, h))
data = sorted(data, key=lambda x: x[0])

loc = {}
for x, h in data:
    loc[x] = bisect.bisect_right([x for x, _ in data], x+2*D)

c = 0
for i in range(N):
    x, h = data[i]
    if h <= 0:
        continue

    # 爆破回数
    attack = math.ceil(h / A)
    c += attack

    # 爆破場所
    # x + D
    for j in range(i+1, loc[x]):
        _x, _h = data[j]        
        if _x <= x + D + D:
            _h -= A * attack
            data[j] = (_x, _h)
        else:
            break

print(c)

Submission status: Time Limit Exceeded

Solution code:
import math
N, D, A = list(map(int, input().split()))
data = []
for _ in range(N):
    x, h = list(map(int, input().split()))
    data.append((x, h))
data = sorted(data, key=lambda x: x[0])

c = 0
for i in range(N):
    x, h = data[i]
    if h <= 0:
        continue

    # 爆破回数
    attack = math.ceil(h / A)
    c += attack

    # 爆破場所
    # x + D
    for j in range(i+1, N):
        _x, _h = data[j]        
        if _x <= x + D + D:
            _h -= A * attack
            data[j] = (_x, _h)
        else:
            break

print(c)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
import bisect
N, D, A = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(N)]
L = [[pos, ceil(hp/A)] for pos, hp in L]
L = sorted(L, key=lambda pos: pos[0])
cnt = 0

for i in range(N):
    left_pos, hp = L[i]
    if hp <= 0:
        continue
    cnt += hp
    right_ind = bisect.bisect_right([v[0] for v in L], left_pos+2*D)
    for v in range(i, right_ind):
        L[v][1] = max(0, L[v][1] - hp)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import bisect

input = sys.stdin.readline
ceil = math.ceil
rbisect=bisect.bisect_right
def main():
    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()
    keys = [ls[0] for ls in mon] #bisect用の配列

    damage = [0]*(n+1)
    ans = 0
    for i in range(n):
        x,h = mon[i]
        res = h-damage[i]
        if res>0:##体力が残ってたら
            c = ceil(res/a)
            ans+=c
            idx = rbisect(keys[i:],x+2*d)-1 ##爆風が届くぎりぎりの位置
            if idx==-1:continue
            damage[i] +=a*c
            damage[i+idx+1] -=a*c
        damage[i+1] += damage[i]
    print(ans)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    def isok(z,val):##適宜変更
        return (z-val<=2*d)
    def bisect(ls,val): ##valの関数isok(x,val)がTrueとなる一番右のindex を返す 全部Falseなら-1
        ok = -1
        ng = len(ls)
        idx = (ok+ng)//2
        while ng-ok>1:
            num = ls[idx]
            if isok(num,val):
                ok = idx
            else:
                ng = idx
            idx = (ok+ng)//2
        return ok ##一番右のTrueのindex  Trueの個数はok+1こ

    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()
    keys = [ls[0] for ls in mon] #bisect用の配列

    damage = [0]*(n+1)
    ans = 0
    for i in range(n):
        x,h = mon[i]
        res = h-damage[i]
        if res>0:##体力が残ってたら
            c = ceil(res/a)
            ans+=c
            idx = bisect(keys[i:],x) ##爆風が届くぎりぎりの位置
            if idx==-1:continue
            damage[i] +=a*c
            damage[i+idx+1] -=a*c
        damage[i+1] += damage[i]
    print(ans)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def isok(z,val):##適宜変更
    if z-val<=2*d:
        return True
    else:
        return False
def bisect(ls,val): ##valの関数isok(x,val)がTrueとなる一番右のindex を返す 全部Falseなら-1
    ok = -1
    ng = len(ls)
    idx = (ok+ng)//2
    while ng-ok>1:
        num = ls[idx]
        if isok(num,val):
            ok = idx
        else:
            ng = idx
        idx = (ok+ng)//2
    return ok ##一番右のTrueのindex  Trueの個数はok+1こ


import sys
import math
input = sys.stdin.readline
ceil = math.ceil
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()
keys = [ls[0] for ls in mon] #bisect用の配列



damage = [0]*(2*n+1)
ans = 0
for i in range(n):
    x,h = mon[i]
    res = h-damage[i]
    if res>0:##体力が残ってたら
        c = ceil(res/a)
        ans+=c
        idx = bisect(keys[i:],x) ##爆風が届くぎりぎりの位置
        if idx==-1:continue
        damage[i] +=a*c
        damage[i+idx+1] -=a*c
    damage[i+1] += damage[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
N, D, A = list(map(int, input().split()))
data = []
for _ in range(N):
    x, h = list(map(int, input().split()))
    data.append((x, h))
data = sorted(data, key=lambda x: x[0])

c = 0
while N:
    if len(data) > 1:
        xl, hl = data[0]
        xr, hr = data[-1]
        if hl < hr:
            h = hr
            t = xr - D
        else:
            h = hl
            t = xl + D
    else:
        t, h = data[0]
    
    # 大きい方を殺す
    attack = math.floor(h / A)
    c += attack

    # 爆破させる場所
    # t = hl + D or hr - D    
    # abs(t - x) <= D が攻撃を受ける

    use = []
    for i in range(len(data)):
        x, h = data[i]
        if abs(t - x) <= D:
            h -= A * attack
            if h <= 0:
                N -= 1
            else:
                use.append((x, h))
        else:
            use.append((x,h))
    data = use[:]


print(c)

Submission status: Time Limit Exceeded

Solution code:
def main():
  N,D,A=map(int,input().split())
  m=sorted([int(j) for j in input().split()] for i in range(N))

  c,l=0,0
  while l<N:
    p=(m[l][1]+A-1)//A
    m[l][1],n,r,c=0,0,l+1,c+p
    while r<N and m[l][0]+2*D>=m[r][0]:
      if m[r][1]>A*p:
        m[r][1]-=A*p
        if n==0:
          n=r
      elif m[r][1]!=0:
        m[r][1]=0
      r+=1
    else:
      l=n if n!=0 else r

  print(c)

main()

Submission status: Time Limit Exceeded

Solution code:
N,D,A=map(int,input().split())
m=sorted([int(j) for j in input().split()] for i in range(N))

def main():
  c,l=0,0
  while l<N:
    p=(m[l][1]+A-1)//A
    m[l][1],n,r,c=0,0,l+1,c+p
    while r<N and m[l][0]+2*D>=m[r][0]:
      if m[r][1]>A*p:
        m[r][1]-=A*p
        if n==0:
          n=r
      elif m[r][1]!=0:
        m[r][1]=0
      r+=1
    else:
      l=n if n!=0 else r

  print(c)

main()

Submission status: Time Limit Exceeded

Solution code:
N,D,A=map(int,input().split())
m=sorted([int(j) for j in input().split()] for i in range(N))

def main():
  c,l=0,0
  while l<N:
    p=(m[l][1]+A-1)//A
    m[l][1],n,r,c=0,0,l+1,c+p
    while r<N and m[l][0]+2*D>=m[r][0]:
      if m[r][1]>A*p:
        m[r][1]-=A*p
        if n==0:
          n=r
      else:
        m[r][1]=0
      r+=1
    else:
      l=n if n!=0 else r

  print(c)

main()

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

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

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

f.sort()
f = np.array(f)

num_bomb = 0
for i in range(n):
    if f[i][1] <= 0:
        continue

    num = math.ceil(f[i][1] / a)
    num_bomb += num
    f[np.where(f[:,0] <= f[i][0] + 2 * d), 1] -= num * a

print(num_bomb)

Submission status: Time Limit Exceeded

Solution code:
import math
n, d, a = map(int, input().split())
foxes = []

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

foxes.sort()

num_bomb = 0
for i in range(n):
    if foxes[i][1] <= 0:
        continue

    num = math.ceil(foxes[i][1] / a)
    num_bomb += num
    for j in range(i, n):
        if foxes[j][0] <= foxes[i][0] + 2 * d:
            foxes[j][1] -= num * a
        else:
            break

print(num_bomb)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, D, A = map(int, input().split())
XH = [0]*N
count = 0
for i in range(N):
    XH[i] = list(map(int, input().split()))
XH.sort()
XHd = deque(XH)
while len(XHd) > 0:
    if XHd[0][1] > 0:
        for i in range(len(XHd)):
            if XHd[i][0] <= XHd[0][0] + 2* D:
                XHd[i][1] -= A
        count += 1
    else:
        XHd.popleft()
print(count)

Submission status: Time Limit Exceeded

Solution code:
n, d, a = map(int, input().split())
array = [0]*n
count = 0
for i in range(n):
    array[i] = list(map(int, input().split()))
array.sort()
while array:
    if array[0][1] <= 0:
        array.pop(0)
    else:
        for i in range(len(array)):
            if array[i][0] <= array[0][0] + 2 * d:
                array[i][1] -= a
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N, D, A = map(int, input().split())
XH = [0]*N
count = 0
delL = []
for i in range(N):
    XH[i] = list(map(int, input().split()))
XH.sort()
while len(XH) > 0:
    if XH[0][1] > 0:
        for i in range(len(XH)):
            if XH[i][0] <= XH[0][0] + 2* D:
                XH[i][1] -= A
        count += 1
    else:
        XH = XH[1::]
print(count)