Problem p03033 (python)

Fixed submission:
from bisect import bisect, bisect_left
from collections import Counter
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

import sys
input = sys.stdin.readline

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

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.size = 2 ** (int.bit_length(N+1))
        self.tree = [0]*(self.size + 1)

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

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


class DammyMap:

    def __init__(self, counter, INF=2**32):
        if type(counter) != Counter:
            counter = Counter(counter)

        self.bit = BIT(len(counter.keys())+3)
        self.key = sorted([-INF, -INF] + sorted(counter.keys()) + [INF])
        self.val = [counter[k] for k in self.key]
        S = list(accumulate(self.val))

        for i in range(len(self.key)):
            self.bit.tree[i] = S[i] - S[i - (i&-i)]
        for i in range(len(self.key), len(self.bit.tree)):
            j = i - (i&-i)
            if j < len(S):
                self.bit.tree[i] = S[-1] - S[i - (i&-i)]


    def add(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, 1)


    def update(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            self.bit.add(ix, v)


    def remove(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            
            # 空の値を削除しないかのチェック
            # 時間が厳しそうなときはコメントアウト
            assert self.bit.sum(ix) - self.bit.sum(ix-1) > 0

            self.bit.add(ix, -v)


    def pop_vals(self, l, r):
        assert l <= r

        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        # (lix, rix]になるのに注意
        rv = self.bit.sum(rix)
        lv = self.bit.sum(lix)
        delta = rv - lv
        tv = lv+1
        tix = lix*1

        vix = 0
        rmvix = 0
        vals = [0]*delta
        rmvk = [0]*delta
        rmvv = [0]*delta
        while delta:
            OK = rix * 1
            NG = tix * 1
            while abs(OK - NG) > 1:
                mid = (OK + NG)//2
                if tv <= self.bit.sum(mid):
                    OK = mid
                else:
                    NG = mid
            c = self.bit.sum(OK)
            d = c - tv + 1
            for _ in range(d):
                vals[vix] = self.key[OK]
                vix += 1
            rmvk[rmvix] = OK
            rmvv[rmvix] = d
            rmvix += 1
            tv += d
            tix = OK
            delta -= d

        for i in range(rmvix):
            self.bit.add(rmvk[i], -rmvv[i])
        return vals

N, M = inpl()
Q = sorted([inpl() for _ in range(N)], key=itemgetter(2))
D = [int(input()) for _ in range(M)]
rD = {v:i for i, v in enumerate(D)}
ans = [-1]*(M)
 
dmap = DammyMap(D)
 
for s, t, x in Q:
    val = dmap.pop_vals(s-x, t-1-x)
    for v in val:
        ans[rD[v]] = x
 
print(*ans, sep="\n")

Buggy submission (verdict: Runtime Error):
from bisect import bisect, bisect_left
from collections import Counter
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

import sys
input = sys.stdin.readline

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

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.size = 2 ** (int.bit_length(N+1))
        self.tree = [0]*(self.size + 1)

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

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


class DammyMap:


    def __init__(self, counter, INF=2**32):
        if type(counter) != Counter:
            counter = Counter(counter)

        self.bit = BIT(len(counter.keys())+3)
        self.key = sorted([-INF, -INF] + sorted(counter.keys()) + [INF])
        self.val = [counter[k] for k in self.key]
        S = list(accumulate(self.val))
        
        for i in range(len(self.key)):
            self.bit.tree[i] = S[i] - S[i - (i&-i)]
        for i in range(len(self.key), len(self.bit.tree)):
            j = i - (i&-i)
            if j < len(S):
                self.bit.tree[i] = S[-1] - S[i - (i&-i)]
        
    
    def add(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, 1)

        
    def update(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            self.bit.add(ix, v)

    
    def remove(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            
            # 空の値を削除しないかのチェック
            # 時間が厳しそうなときはコメントアウト
            #assert self.bit.sum(ix) - self.bit.sum(ix-1) > 0

            self.bit.add(ix, -v)


    def pop_vals(self, l, r):
        assert l <= r

        vals = []
        rmvs = []

        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        # (lix, rix]になるのに注意
        rv = self.bit.sum(rix)
        lv = self.bit.sum(lix)
        delta = rv - lv
        tv = lv+1
        tix = lix*1
        while delta:
            OK = rix * 1
            NG = tix * 1
            while abs(OK - NG) > 1:
                mid = (OK + NG)//2
                if tv <= self.bit.sum(mid):
                    OK = mid
                else:
                    NG = mid
            c = self.bit.sum(OK)
            d = c - tv + 1
            vals.extend([self.key[OK]*1 for _ in range(d)])
            rmvs.append([OK, d])
            tv += d
            tix = OK
            delta -= d
        
        for ix, d in rmvs:
            self.bit.add(ix, -d)
        return vals


N, M = inpl()
Q = sorted([inpl() for _ in range(N)], key=itemgetter(2))
D = [int(input()) for _ in range(M)]
rD = {v:i for i, v in enumerate(D)}
ans = [-1]*(M)

dmap = DammyMap(D)

for s, t, x in Q:
    val = dmap.get_vals(s-x, t-1-x)
    for v in val:
        ans[rD[v]] = x
    dmap.remove(val)

print(*ans, sep="\n")

Buggy submission (verdict: Runtime Error):
from bisect import bisect, bisect_left
from collections import Counter
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

import sys
input = sys.stdin.readline

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

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.size = 2 ** (int.bit_length(N+1))
        self.tree = [0]*(self.size + 1)

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

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


class RABIT():
    # range add BIT
    def __init__(self, N):
        self.bit0 = BIT(N)
        self.bit1 = BIT(N)

    def sum(self, i):
        return i*self.bit1.sum(i) + self.bit0.sum(i)

    def add_range(self, l, r, x):
        self.bit0.add(l, -x*(l-1))
        self.bit1.add(l, x)
        self.bit0.add(r+1, x*r)
        self.bit1.add(r+1, -x)

    def get_range(self, l, r):
        return self.sum(r) - self.sum(l-1)

class DammyMap:
    """
    座圧してc++のmapみたいな操作が必要な問題に対応する
    要素の追加、削除がO(logN)
    指定した区間の取り出しがO(logNlogN)
    """
    def __init__(self, counter, INF=2**31):
        if type(counter) != Counter:
            counter = Counter(counter)

        self.rabit = RABIT(len(counter.keys()) + 2)
        self.key = sorted([-INF] + sorted(counter.keys()) + [INF])
        self.ukey = set(counter.keys())
        self.val = [counter[k] for k in self.key]
        S = list(accumulate(accumulate(self.val)))

        for i in range(len(self.key)):
            self.rabit.bit0.tree[i] = S[i] - S[i - (i&-i)]
        for i in range(len(self.key), len(self.rabit.bit0.tree)):
            j = i - (i&-i)
            if j < len(S):
                self.rabit.bit0.tree[i] = S[-1] - S[i - (i&-i)]
    
    def add(self, val):
        if not val in self.ukey:
            raise KeyError
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.rabit.add_range(ix, len(self.rabit.bit0.tree)-1, 1)
    
    def update(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            self.rabit.add_range(ix,  len(self.rabit.bit0.tree)-1, v)

    def remove(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            self.rabit.add_range(ix, len(self.rabit.bit0.tree)-1, -v)
    
    def get_vals(self, l, r):
        """
        [l, r]に含まれるアイテムを返す
        """
        assert l <= r

        vals = []
        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        # (lix, rix]になるのに注意
        rv = self.rabit.get_range(rix, rix)
        lv = self.rabit.get_range(lix, lix) if lix else 0
        delta = rv - lv
        tv = lv+1
        tix = lix*1
        while delta:
            OK = rix * 1
            NG = tix * 1
            while abs(OK - NG) > 1:
                mid = (OK + NG)//2
                if tv <= self.rabit.get_range(mid, mid):
                    OK = mid
                else:
                    NG = mid
            c = self.rabit.get_range(OK, OK)
            d = c - tv + 1
            vals.extend([self.key[OK]*1 for _ in range(d)])
            tv += d
            tix = OK
            delta -= d
        return vals

N, M = inpl()
Q = sorted([inpl() for _ in range(N)], key=itemgetter(2))
D = [int(input()) for _ in range(M)]
rD = {v:i for i, v in enumerate(D)}
ans = [-1]*(M)

dmap = DammyMap(D)

for s, t, x in Q:
    val = dmap.get_vals(s-x, t-1-x)
    for v in val:
        ans[rD[v]] = x
    dmap.remove(val)

print(*ans, sep="\n")

Buggy submission (verdict: Runtime Error):
from bisect import bisect, bisect_left
from collections import Counter
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

import sys
input = sys.stdin.readline

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

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.size = 2 ** (int.bit_length(N+1))
        self.tree = [0]*(self.size + 1)

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

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


class RABIT():
    # range add BIT
    def __init__(self, N):
        self.bit0 = BIT(N)
        self.bit1 = BIT(N)

    def sum(self, i):
        return i*self.bit1.sum(i) + self.bit0.sum(i)

    def add_range(self, l, r, x):
        self.bit0.add(l, -x*(l-1))
        self.bit1.add(l, x)
        self.bit0.add(r+1, x*r)
        self.bit1.add(r+1, -x)

    def get_range(self, l, r):
        return self.sum(r) - self.sum(l-1)

class DammyMap:
    """
    座圧してc++のmapみたいな操作が必要な問題に対応する
    要素の追加、削除がO(logN)
    指定した区間の取り出しがO(logNlogN)
    """
    def __init__(self, counter, INF=2**31):
        if type(counter) != Counter:
            counter = Counter(counter)

        self.rabit = RABIT(len(counter.keys()) + 2)
        self.key = sorted([-INF] + sorted(counter.keys()) + [INF])
        self.ukey = set(counter.keys())
        self.val = [counter[k] for k in self.key]
        S = list(accumulate(accumulate(self.val)))

        for i in range(len(self.key)):
            self.rabit.bit0.tree[i] = S[i] - S[i - (i&-i)]
        for i in range(len(self.key), len(self.rabit.bit0.tree)):
            j = i - (i&-i)
            if j < len(S):
                self.rabit.bit0.tree[i] = S[-1] - S[i - (i&-i)]
    
    def add(self, val):
        if not val in self.ukey:
            raise KeyError
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.rabit.add_range(ix, len(self.rabit.bit0.tree)-1, 1)
    
    def update(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            self.rabit.add_range(ix,  len(self.rabit.bit0.tree)-1, v)

    def remove(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            self.rabit.add_range(ix, len(self.rabit.bit0.tree)-1, -v)
    
    def get_vals(self, l, r):
        """
        [l, r]に含まれるアイテムを返す
        """
        assert l <= r

        vals = []
        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        # (lix, rix]になるのに注意
        rv = self.rabit.get_range(rix, rix)
        lv = self.rabit.get_range(lix, lix) if lix else 0
        delta = rv - lv
        tv = lv+1
        tix = lix*1
        while delta:
            OK = rix * 1
            NG = tix * 1
            while abs(OK - NG) > 1:
                mid = (OK + NG)//2
                if tv <= self.rabit.get_range(mid, mid):
                    OK = mid
                else:
                    NG = mid
            c = self.rabit.get_range(OK, OK)
            d = c - tv + 1
            vals.extend([self.key[OK]*1 for _ in range(d)])
            tv += d
            tix = OK
            delta -= d
        return vals

N, M = inpl()
Q = sorted([inpl() for _ in range(N)], key=itemgetter(2))
D = [int(input()) for _ in range(M)]
rD = {v:i for i, v in enumerate(D)}
ans = [-1]*(M)

dmap = DammyMap(D)

for s, t, x in Q:
    val = dmap.get_vals(s-x, t-1-x)
    for v in val:
        ans[rD[v]] = x
    dmap.remove(val)

print(*ans, sep="\n")