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:
# https://atcoder.jp/contests/abc153/tasks/abc153_f
# 筋肉でなぐる


def _gidx(l, r, treesize):
    '''
    lazy propagation用idx生成器 木の下から生成される。1based-indexなので注意.(使うときは-1するとか)
    もとの配列において[l,r)を指定したときに更新すべきidxをyieldする
    treesizeは多くの場合self.num
    '''
    L, R = l + treesize, r + treesize
    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:  # Rでもいいけどね
        yield L
        L >>= 1


import operator


class LazySegmentTree:  # 区間合計(ホントは何でも良い)クエリ と 区間加算クエリを扱うことにする
    def __init__(self, ls: list, segfunc=operator.add, identity_element=0, lazy_ide=0):
        '''
        セグ木
        一次元のリストlsを受け取り初期化する。O(len(ls))
        区間のルールはsegfuncによって定義される
        identity elementは単位元。e.g., 最小値を求めたい→inf, 和→0, 積→1, gcd→0
        [単位元](https://ja.wikipedia.org/wiki/%E5%8D%98%E4%BD%8D%E5%85%83)
        '''
        self.ide = identity_element
        self.lide = lazy_ide  # lazy用単位元
        self.func = segfunc
        n = len(ls)
        self.num = 2 ** (n - 1).bit_length()  # n以上の最小の2のべき乗
        self.tree = [self.ide] * (2 * self.num)  # 関係ない値を-1においてアクセスを許すと都合が良い
        self.lazy = [self.lide] * (2 * self.num)  # 遅延配列
        for i, l in enumerate(ls):  # 木の葉に代入
            self.tree[i + self.num - 1] = l
        for i in range(self.num - 2, -1, -1):  # 子を束ねて親を更新
            self.tree[i] = segfunc(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def _lazyprop(self, *ids):
        '''
        遅延評価用の関数
        - self.tree[i] に self.lazy[i]の値を伝播させて遅延更新する
        - 子ノードにself.lazyの値を伝播させる **ここは問題ごとに書き換える必要がある**
        - self.lazy[i]をリセットする
        '''
        for i in reversed(ids):
            i -= 1  # to 0basedindex
            v = self.lazy[i]
            if v == self.lide:
                continue
            #########################################################
            # この4つの配列をどう更新するかは問題によって異なる
            self.tree[2 * i + 1] += v >> 1  # 区間加算クエリなので
            self.tree[2 * i + 2] += v >> 1
            self.lazy[2 * i + 1] += v >> 1
            self.lazy[2 * i + 2] += v >> 1
            #########################################################

            self.lazy[i] = self.lide  # 遅延配列を空に戻す

    def update(self, l, r, x):
        '''
        [l,r)番目の要素をxを適応するクエリを行う O(logN)
        '''
        # 1, 根から区間内においてlazyの値を伝播しておく(self.treeの値が有効になる)
        ids = tuple(_gidx(l, r, self.num))
        #########################################################
        # 区間加算queryのような操作の順序が入れ替え可能な場合これをする必要なないが多くの場合でしたほうがバグが少なく(若干遅くなる)
        # self._lazyprop(*ids)
        #########################################################
        # 2, 区間に対してtree,lazyの値を更新 (treeは根方向に更新するため、lazyはpropで葉方向に更新するため)
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        l += self.num
        r += self.num
        while l < r:
            #########################################################
            # ** 問題によって値のセットの仕方も変えるべし**
            if r & 1:
                r -= 1
                self.tree[r - 1] += x
                self.lazy[r - 1] += x
            if l & 1:
                self.tree[l - 1] += x
                self.lazy[l - 1] += x
                l += 1
            #########################################################
            x <<= 1  # 区間加算クエリでは上段では倍倍になるはずだよね
            l >>= 1
            r >>= 1
        # 3, 伝播させた区間について下からdataの値を伝播する
        for i in ids:
            i -= 1  # to 0based
            #########################################################
            # 関数の先頭でlazy propを省略した場合は、現在のノードにlazyが反映されていないことがある
            # lazyを省略するならここを慎重に書き換えなければならない
            self.tree[i] = self.func(
                self.tree[2 * i + 1], self.tree[2 * i + 2]) + self.lazy[i]
            #########################################################

    def query(self, l, r):
        '''
        区間[l,r)に対するクエリをO(logN)で処理する。例えばその区間の最小値、最大値、gcdなど
        '''
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        # 1, 根からにlazyの値を伝播させる
        self._lazyprop(*_gidx(l, r, self.num))
        # 2, 区間[l,r)の最小値を求める
        l += self.num
        r += self.num
        res = self.ide
        while l < r:  # 右から寄りながら結果を結合していくイメージ
            if r & 1:
                r -= 1
                res = self.func(res, self.tree[r - 1])
            if l & 1:
                res = self.func(res, self.tree[l - 1])
                l += 1
            l >>= 1
            r >>= 1
        return res


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


# default import
from bisect import bisect_left, bisect_right


N, D, A = read_ints()
XH = read_tuple(N)

XH.sort()
# なにはともあれ攻撃回数に変更
X = []
H_cnt = []
for x, h in XH:
    H_cnt.append((h - 1) // A + 1)
    X.append(x)

seg = LazySegmentTree(H_cnt)
# 前から順に攻撃をシミュレーション
ans = 0
for i in range(N):
    atk = seg.query(i, i + 1)  # 残りの体力を取得(攻撃回数)
    if atk <= 0:
        continue
    ans += atk
    # 巻き添えを後ろの方々に
    seg.update(i+1, bisect_left(X, X[i] + 2 * D + 1, lo=i), -atk)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc153/tasks/abc153_f
# 筋肉でなぐる


def _gidx(l, r, treesize):
    '''
    lazy propagation用idx生成器 木の下から生成される。1based-indexなので注意.(使うときは-1するとか)
    もとの配列において[l,r)を指定したときに更新すべきidxをyieldする
    treesizeは多くの場合self.num
    '''
    L, R = l + treesize, r + treesize
    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:  # Rでもいいけどね
        yield L
        L >>= 1


import operator


class LazySegmentTree:  # 区間合計(ホントは何でも良い)クエリ と 区間加算クエリを扱うことにする
    def __init__(self, ls: list, segfunc=operator.add, identity_element=0, lazy_ide=0):
        '''
        セグ木
        一次元のリストlsを受け取り初期化する。O(len(ls))
        区間のルールはsegfuncによって定義される
        identity elementは単位元。e.g., 最小値を求めたい→inf, 和→0, 積→1, gcd→0
        [単位元](https://ja.wikipedia.org/wiki/%E5%8D%98%E4%BD%8D%E5%85%83)
        '''
        self.ide = identity_element
        self.lide = lazy_ide  # lazy用単位元
        self.func = segfunc
        n = len(ls)
        self.num = 2 ** (n - 1).bit_length()  # n以上の最小の2のべき乗
        self.tree = [self.ide] * (2 * self.num)  # 関係ない値を-1においてアクセスを許すと都合が良い
        self.lazy = [self.lide] * (2 * self.num)  # 遅延配列
        for i, l in enumerate(ls):  # 木の葉に代入
            self.tree[i + self.num - 1] = l
        for i in range(self.num - 2, -1, -1):  # 子を束ねて親を更新
            self.tree[i] = segfunc(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def _lazyprop(self, *ids):
        '''
        遅延評価用の関数
        - self.tree[i] に self.lazy[i]の値を伝播させて遅延更新する
        - 子ノードにself.lazyの値を伝播させる **ここは問題ごとに書き換える必要がある**
        - self.lazy[i]をリセットする
        '''
        for i in reversed(ids):
            i -= 1  # to 0basedindex
            v = self.lazy[i]
            if v == self.lide:
                continue
            #########################################################
            # この4つの配列をどう更新するかは問題によって異なる
            self.tree[2 * i + 1] += v >> 1  # 区間加算クエリなので
            self.tree[2 * i + 2] += v >> 1
            self.lazy[2 * i + 1] += v >> 1
            self.lazy[2 * i + 2] += v >> 1
            #########################################################

            self.lazy[i] = self.lide  # 遅延配列を空に戻す

    def update(self, l, r, x):
        '''
        [l,r)番目の要素をxを適応するクエリを行う O(logN)
        '''
        # 1, 根から区間内においてlazyの値を伝播しておく(self.treeの値が有効になる)
        ids = tuple(_gidx(l, r, self.num))
        #########################################################
        # 区間加算queryのような操作の順序が入れ替え可能な場合これをする必要なないが多くの場合でしたほうがバグが少なく(若干遅くなる)
        # self._lazyprop(*ids)
        #########################################################
        # 2, 区間に対してtree,lazyの値を更新 (treeは根方向に更新するため、lazyはpropで葉方向に更新するため)
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        l += self.num
        r += self.num
        while l < r:
            #########################################################
            # ** 問題によって値のセットの仕方も変えるべし**
            if r & 1:
                r -= 1
                self.tree[r - 1] += x
                self.lazy[r - 1] += x
            if l & 1:
                self.tree[l - 1] += x
                self.lazy[l - 1] += x
                l += 1
            #########################################################
            x <<= 1  # 区間加算クエリでは上段では倍倍になるはずだよね
            l >>= 1
            r >>= 1
        # 3, 伝播させた区間について下からdataの値を伝播する
        for i in ids:
            i -= 1  # to 0based
            #########################################################
            # 関数の先頭でlazy propを省略した場合は、現在のノードにlazyが反映されていないことがある
            # lazyを省略するならここを慎重に書き換えなければならない
            self.tree[i] = self.func(
                self.tree[2 * i + 1], self.tree[2 * i + 2]) + self.lazy[i]
            #########################################################

    def query(self, l, r):
        '''
        区間[l,r)に対するクエリをO(logN)で処理する。例えばその区間の最小値、最大値、gcdなど
        '''
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        # 1, 根からにlazyの値を伝播させる
        self._lazyprop(*_gidx(l, r, self.num))
        # 2, 区間[l,r)の最小値を求める
        l += self.num
        r += self.num
        res = self.ide
        while l < r:  # 右から寄りながら結果を結合していくイメージ
            if r & 1:
                r -= 1
                res = self.func(res, self.tree[r - 1])
            if l & 1:
                res = self.func(res, self.tree[l - 1])
                l += 1
            l >>= 1
            r >>= 1
        return res


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from fractions import gcd
from bisect import bisect_left, bisect_right, insort_left, insort_right


N, D, A = read_ints()
XH = read_tuple(N)

XH.sort()
# なにはともあれ攻撃回数に変更
X = []
H_cnt = []
for x, h in XH:
    H_cnt.append((h - 1) // A + 1)
    X.append(x)

seg = LazySegmentTree(H_cnt)
# 前から順に攻撃をシミュレーション
ans = 0
for i in range(N):
    atk = seg.query(i, i + 1)  # 残りの体力を取得(攻撃回数)
    if atk <= 0:
        continue
    ans += atk
    # 巻き添えを後ろの方々に
    seg.update(i, bisect_left(X, X[i] + 2 * D + 1, lo=i), -atk)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc153/tasks/abc153_f
# 筋肉でなぐる


def _gidx(l, r, treesize):
    '''
    lazy propagation用idx生成器 木の下から生成される。1based-indexなので注意.(使うときは-1するとか)
    もとの配列において[l,r)を指定したときに更新すべきidxをyieldする
    treesizeは多くの場合self.num
    '''
    L, R = l + treesize, r + treesize
    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:  # Rでもいいけどね
        yield L
        L >>= 1


import operator


class LazySegmentTree:  # 区間合計(ホントは何でも良い)クエリ と 区間加算クエリを扱うことにする
    def __init__(self, ls: list, segfunc=operator.add, identity_element=0, lazy_ide=0):
        '''
        セグ木
        一次元のリストlsを受け取り初期化する。O(len(ls))
        区間のルールはsegfuncによって定義される
        identity elementは単位元。e.g., 最小値を求めたい→inf, 和→0, 積→1, gcd→0
        [単位元](https://ja.wikipedia.org/wiki/%E5%8D%98%E4%BD%8D%E5%85%83)
        '''
        self.ide = identity_element
        self.lide = lazy_ide  # lazy用単位元
        self.func = segfunc
        n = len(ls)
        self.num = 2 ** (n - 1).bit_length()  # n以上の最小の2のべき乗
        self.tree = [self.ide] * (2 * self.num)  # 関係ない値を-1においてアクセスを許すと都合が良い
        self.lazy = [self.lide] * (2 * self.num)  # 遅延配列
        for i, l in enumerate(ls):  # 木の葉に代入
            self.tree[i + self.num - 1] = l
        for i in range(self.num - 2, -1, -1):  # 子を束ねて親を更新
            self.tree[i] = segfunc(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def _lazyprop(self, *ids):
        '''
        遅延評価用の関数
        - self.tree[i] に self.lazy[i]の値を伝播させて遅延更新する
        - 子ノードにself.lazyの値を伝播させる **ここは問題ごとに書き換える必要がある**
        - self.lazy[i]をリセットする
        '''
        for i in reversed(ids):
            i -= 1  # to 0basedindex
            v = self.lazy[i]
            if v == self.lide:
                continue
            #########################################################
            # この4つの配列をどう更新するかは問題によって異なる
            self.tree[2 * i + 1] += v  # 区間加算クエリなので
            self.tree[2 * i + 2] += v
            self.lazy[2 * i + 1] += v
            self.lazy[2 * i + 2] += v
            #########################################################

            self.lazy[i] = self.lide  # 遅延配列を空に戻す

    def update(self, l, r, x):
        '''
        [l,r)番目の要素をxを適応するクエリを行う O(logN)
        '''
        # 1, 根から区間内においてlazyの値を伝播しておく(self.treeの値が有効になる)
        ids = tuple(_gidx(l, r, self.num))
        #########################################################
        # 区間加算queryのような操作の順序が入れ替え可能な場合これをする必要なないが多くの場合でしたほうがバグが少なく(若干遅くなる)
        self._lazyprop(*ids)
        #########################################################
        # 2, 区間に対してtree,lazyの値を更新 (treeは根方向に更新するため、lazyはpropで葉方向に更新するため)
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        l += self.num
        r += self.num
        while l < r:
            #########################################################
            # ** 問題によって値のセットの仕方も変えるべし**
            if r & 1:
                r -= 1
                self.tree[r - 1] += x
                self.lazy[r - 1] += x
            if l & 1:
                self.tree[l - 1] += x
                self.lazy[l - 1] += x
                l += 1
            #########################################################
            l >>= 1
            r >>= 1
        # 3, 伝播させた区間について下からdataの値を伝播する
        for i in ids:
            i -= 1  # to 0based
            #########################################################
            # 関数の先頭でlazy propを省略した場合は、現在のノードにlazyが反映されていないことがある
            # lazyを省略するならここを慎重に書き換えなければならない
            self.tree[i] = self.func(
                self.tree[2 * i + 1], self.tree[2 * i + 2])
            #########################################################

    def query(self, l, r):
        '''
        区間[l,r)に対するクエリをO(logN)で処理する。例えばその区間の最小値、最大値、gcdなど
        '''
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        # 1, 根からにlazyの値を伝播させる
        self._lazyprop(*_gidx(l, r, self.num))
        # 2, 区間[l,r)の最小値を求める
        l += self.num
        r += self.num
        res = self.ide
        while l < r:  # 右から寄りながら結果を結合していくイメージ
            if r & 1:
                r -= 1
                res = self.func(res, self.tree[r - 1])
            if l & 1:
                res = self.func(res, self.tree[l - 1])
                l += 1
            l >>= 1
            r >>= 1
        return res


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from fractions import gcd
from bisect import bisect_left, bisect_right, insort_left, insort_right


N, D, A = read_ints()
XH = read_tuple(N)

XH.sort()
# なにはともあれ攻撃回数に変更
X = []
H_cnt = []
for x, h in XH:
    H_cnt.append((h - 1) // A + 1)
    X.append(x)

seg = LazySegmentTree(H_cnt)
# 前から順に攻撃をシミュレーション
ans = 0
for i in range(N):
    atk = seg.query(i, i + 1)  # 残りの体力を取得(攻撃回数)
    if atk <= 0:
        continue
    ans += atk
    # 巻き添えを後ろの方々に
    seg.update(i, bisect_left(X, X[i] + 2 * D + 1, lo=i), -atk)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math

#区間加算，1点取得
class SegTree2:
    # n : 元の配列の長さ
    # init_list: 元の配列
    # segfunc : 載せる関数（演算）
    # ide_ele : segfuncの単位元
        
    def __init__(self, n, init_list ,segfunc, ide_ele):
        #　num : 2**num >= n となる最小の整数 （葉の数）
        # seg : segtreeのリスト
        self.num = 2**((n-1).bit_length())
        self.seg = [ide_ele]*(2*self.num)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        # 葉の要素をセット
        for i in range(n):
            self.seg[i+self.num-1] = init_list[i]        
        # segtreeの構築
        for i in range(self.num-2, -1, -1):
            self.seg[i] = segfunc(self.seg[2*i+1],self.seg[2*i+2])
        
        #memo: 要素iの子ノードは要素2*i+1, 2*i+2
        #    : 要素iの親ノードは要素(i-1)//2
        
    # 更新[l,r)にxを加算
    def update(self,l,r,x):
        if r<=l:
            return self.ide_ele
        l += self.num-1 #葉のノードのインデックス
        r += self.num-2 #半開区間から閉区間へ
         
        while r-l>1:
            if l&1 == 0:
                self.seg[l] = self.segfunc(self.seg[l],x)       
            if r&1 == 1:
                self.seg[r] = self.segfunc(self.seg[r],x)
                r -= 1
            # 親ノードへ遷移
            l = l//2
            r = (r-1)//2
        if r==l:
            self.seg[r] = self.segfunc(self.seg[r],x)
        else:
            self.seg[l] = self.segfunc(self.seg[l],x)
            self.seg[r] = self.segfunc(self.seg[r],x)
  
    # k番目の要素に加算されている合計値を計算
    def query(self,k):    
        k += self.num-1 #葉のノードのインデックス
        ret = self.seg[k]
        #末端から頂点まで更新
        while k:
            k = (k-1)//2
            ret = self.segfunc(ret, self.seg[k])
        return ret
    
            
def segfunc(x,y):
    return x|y



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

#%%
ans = 0
damage = 0
seg = SegTree2(N,[0]*N,lambda x,y:x+y,0)

right = 1
for i in range(N):
    d = XH[i][1] - seg.query(i)
    if d<=0:
        continue
    else:
        c = math.ceil(d/A)
        ans += c
        
        while right<N and XH[right][0]<=XH[i][0]+2*D :
            right += 1
        
        seg.update(i,right,c*A)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

def div_ceil(x, y): return (x + y - 1) // y

N, D, A = map(int, input().split())
monsters = [list(map(int, input().split())) for _ in range(N)]
monsters = sorted(monsters, key=lambda x: x[0])
position = [x for x, _ in monsters]
ans = 0
for i, m in enumerate(monsters):
    x, hp = m
    if hp <= 0: continue
    j = bisect_right(position, x + 2*D)
    attack = div_ceil(hp, A)
    ans += attack
    damage = attack * A
    for k in range(i+1, min(j, N)):
        monsters[k][1] -= damage
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left,bisect_right
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])
X = [e[0] for e in XH]
H = [e[1] for e in XH]
ans = 0
pos = XH[0][0]+D
while any([e>0 for e in H]):
    k1 = bisect_left(X,pos-D)
    k2 = bisect_right(X,pos+D)
    if H[k1] % A == 0:
        c = H[k1]//A
    else:
        c = H[k1]//A+1
    for i in range(k1,k2):
        H[i] -= A*c
    ans += c
    #decide next position
    for i in range(k1,N):
        if H[i] > 0:
            pos = X[i]+D
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left,bisect_right



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])
X = [e[0] for e in XH]
H = [e[1] for e in XH]
ans = 0
pos = XH[0][0]+D
while any([e>0 for e in H]):
    k1 = bisect_left(X,pos-D)
    k2 = bisect_right(X,pos+D)
    if H[k1] % A == 0:
        c = H[k1]//A
    else:
        c = H[k1]//A+1
    for i in range(k1,k2):
        H[i] -= A*c
    ans += c
    #decide next position
    for i in range(N):
        if H[i] > 0:
            pos = X[i]+D
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import math

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

monsters = collections.deque(sorted(XH))
ans = 0
while monsters:
    left_x, left_h = monsters.popleft()
    if left_h < 0:
        continue
    bomb_count = math.ceil(left_h / A)
    ans += bomb_count

    i = 0
    while i < len(monsters):
        if monsters[i][0] > left_x + 2 * D:
            break
        else:
            monsters[i] = (monsters[i][0], monsters[i][1] - bomb_count * A)
            i += 1
print(ans)

Submission status: Time Limit Exceeded

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

X = numpy.array([xh[0] for xh in XH])
H = numpy.array([xh[1] for xh in XH])

ans = 0
for i in range(N):
    if H[i] <= 0:
        continue

    bomb_count = math.ceil(H[i] / A)
    ans += bomb_count

    in_range = X <= X[i]+2*D
    H += in_range * (-bomb_count * A)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy
import math
N, D, A = tuple(map(int, input().split(" ")))
XH = []
for _ in range(N):
    XH.append(tuple(map(int, input().split(" "))))

X = numpy.array([XH[0] for XH in sorted(XH)])
H = numpy.array([XH[1] for XH in sorted(XH)])

ans = 0
for i in range(N):
    if H[i] <= 0:
        continue

    bomb_count = math.ceil(H[i] / A)
    ans += bomb_count

    in_range = X <= X[i]+2*D
    H += in_range * (-bomb_count * A)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import math
N, D, A = tuple(map(int, input().split(" ")))
XH = []
for _ in range(N):
    XH.append(tuple(map(int, input().split(" "))))

monsters = collections.deque(sorted(XH))
ans = 0
while monsters:
    left_x, left_h = monsters.popleft()
    bomb_count = math.ceil(left_h / A)
    ans += bomb_count

    i = 0
    while i < len(monsters):
        if monsters[i][0] > left_x + 2 * D:
            break
        elif monsters[i][1] - bomb_count * A <= 0:
            del monsters[i]
        else:
            monsters[i] = (monsters[i][0], monsters[i][1] - bomb_count * A)
            i += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import math
N, D, A = tuple(map(int, input().split(" ")))
XH = []
for _ in range(N):
    XH.append(tuple(map(int, input().split(" "))))

monsters = collections.deque(sorted(XH))
ans = 0
while monsters:
    left_x, left_h = monsters.popleft()
    surroundings = []
    while monsters and monsters[0][0] <= left_x + 2 * D:
        surroundings.append(monsters.popleft())
    bomb_count = math.ceil(left_h / A)
    ans += bomb_count
    for s in surroundings[::-1]:
        x, h = s
        if h - bomb_count * A > 0:
            monsters.appendleft((x, h - bomb_count * A))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math

N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort()
#%%
ans = 0
damage = 0
for i in range(N):
    d = XH[i][1]
    if d<=0:
        continue
    else:
        c = math.ceil(d/A)
        ans += c
        
        idx = i+1
        while idx<N and XH[idx][0]<=XH[i][0]+2*D :
            XH[idx][1] -= A*c
            idx += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, D, a = [int(x) for x in input().split()]
XH = []
for _ in range(N):
    XH.append([int(x) for x in input().split()])
XH.sort()

#####segfunc######
def segfunc(x,y):
    return x + y

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#入力
n = N
A = [0] * N

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

#init
init(A)

import bisect

X = []
H = []
for i in XH:
    X.append(i[0])
    H.append(i[1])
ans = 0
for i in range(N):
    x, h = X[i], H[i]
    idx_left = bisect.bisect_left(X, x - 2 * D)
    idx_right = bisect.bisect_right(X, x + 2 * D)
    if query(idx_left, idx_right) < h:
        h -= query(idx_left, idx_right)
        cnt = h // a
        if h % a != 0:
            cnt += 1
        ans += cnt
        update(i, a * cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, D, A = list(map(int, input().split()))
X = np.ones(N)
H = np.ones(N)
for i in range(N):
  X[i], H[i] = list(map(int, input().split()))

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

min_n = 0

for i in range(N):
  if H[i] <= 0:
    continue
  in2Di = np.abs(X - X[i]) <= 2 * D
  ni = int(H[i]/A) if H[i] % A == 0 else int(H[i]/A) + 1
  H[in2Di] -= A * ni
  min_n += ni
  
print(min_n)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

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

x=[xh[i][0] for i in range(n)]
lst=[]
for i in range(n):
    lst.append([i,bisect.bisect(x,x[i]+2*d)])
# print(lst)

ans=0
for i in range(n):
    if xh[i][1]>0:
        cnt=math.ceil(xh[i][1]/a)
        ans+=cnt
        for j in range(lst[i][0],lst[i][1]):
            xh[j][1]-=cnt*a
        # print(cnt,ans)
        # print(xh)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import socket

if socket.gethostname() in ['N551J', 'F551C']:
    sys.stdin = open('f1.in')


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


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


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    n, d, a = read_int_list()
    pairs = [read_int_list() for _ in range(n)]
    pairs.sort()
    x, h = map(list, zip(*pairs))

    res = 0
    damage = 0
    q = []
    for i in range(n):
        while len(q) > 0 and q[0][0] + d < x[i]:
            y, m = q.pop(0)
            damage -= m * a
        if damage < h[i]:
            y = x[i] + d
            quotient, rest = divmod(h[i] - damage, a)
            m = quotient + (rest > 0)
            q.append((y, m))
            damage += m * a
            res += m

    return res



def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

XH = sorted(XH, key=lambda x: x[0])
X = [XH[i][0] for i in range(N)]
H = [(XH[i][1] + A - 1) // A for i in range(N)] 
## どうせAずつしか体力減らせないので、何回攻撃したら倒せるかに変換

if X[-1] - X[0] <= 2*D:
  ans = max(H)
  print(ans)
  exit()

ans = 0
for i in range(N):
  if H[i] <= 0:
    continue
  else:
    max_index = bisect.bisect_right(X, X[i]+2*D)
    n_attack_i = H[i]
    for j in range(i, max_index):
      H[j] -= n_attack_i
    ans += n_attack_i
    
print(ans)