Problem p02956 (python)

Fixed submission:

import sys
input = sys.stdin.readline


class SegmentTree:
    def __init__(self, L, op, default_val):
        self.op = op
        self.default_val = default_val
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.default_val]*(2*self.n-1)

        for i in range(self.sz):
            self.node[i+self.n-1] = L[i]

        for i in range(self.n-2,-1,-1):
            self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def get(self, l, r):
        res = self.default_val
        n = self.n
        if self.sz <= r or 0 > l:
            print("ERROR: the indice are wrong.")
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        n1 = n//2        
        #left
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        n1 = n//2        
        #right
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res

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

point.sort(lambda x: x[1])
for i in range(len(point)):
    point[i][1] = i

mod = 998244353

ans = ((N-4)*pow(2,N,mod)+3*N+4)%mod

pow2 = []
a = 1
for i in range(N+1):
    pow2.append(a)
    a *= 2
    a %= mod

point.sort(lambda x: x[0])

ST = SegmentTree([0]*len(point), lambda a,b:a+b, 0)


for i,(x,y) in enumerate(point):
    if point[i][1] > 0:
        ld = ST.get(0,y-1)
        #ls = i//2
    else:
        ld = 0
    lu = i-ld
    rd = y - ld
    ru = N - i - 1 - rd    
    ans += pow2[lu]-1
    ans += pow2[ld]-1
    ans += pow2[ru]-1
    ans += pow2[rd]-1
    ans %= mod
    ST.add(point[i][1],1)

print(ans)

Buggy submission (verdict: Runtime Error):
import sys
from operator import itemgetter

input = sys.stdin.readline
 
 
class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)
 
    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break
 
    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret
 
 
N = int(input())
point = [list(map(int,input().split())) for i in range(N)]
 
point.sort(itemgetter(1))
for i in range(len(point)):
    point[i][1] = i
 
mod = 998244353
 
ans = ((N-4)*pow(2,N,mod)+3*N+4)%mod
 
pow2 = []
a = 1
for i in range(N+1):
    pow2.append(a)
    a *= 2
    a %= mod
 
point.sort(itemgetter(0))
 
bit = BIT([0]*len(point))
 
 
for i,(x,y) in enumerate(point):
    if y > 0:
        ld = bit.sum(y-1)
 
    else:
        ld = 0
    lu = i-ld
    rd = y - ld
    ru = N - i - 1 - rd    
    ans += pow2[lu]-1
    ans += pow2[ld]-1
    ans += pow2[ru]-1
    ans += pow2[rd]-1
    ans %= mod
    bit.add(y,1)
 
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
from operator import itemgetter

input = sys.stdin.readline
 
 
class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)
 
    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break
 
    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret
 
 
N = int(input())
point = [list(map(int,input().split())) for i in range(N)]
 
point.sort(lambda x: x[1])
for i in range(len(point)):
    point[i][1] = i
 
mod = 998244353
 
ans = ((N-4)*pow(2,N,mod)+3*N+4)%mod
 
pow2 = []
a = 1
for i in range(N+1):
    pow2.append(a)
    a *= 2
    a %= mod
 
point.sort(lambda x: x[0])
 
bit = BIT([0]*len(point))
 
 
for i,(x,y) in enumerate(point):
    if y > 0:
        ld = bit.sum(y-1)
        #ls = i//2
    else:
        ld = 0
    lu = i-ld
    rd = y - ld
    ru = N - i - 1 - rd    
    ans += pow2[lu]-1
    ans += pow2[ld]-1
    ans += pow2[ru]-1
    ans += pow2[rd]-1
    ans %= mod
    bit.add(y,1)
 
print(ans)
import sys
input = sys.stdin.readline
 

class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret

 
N = int(input())
point = [list(map(int,input().split())) for i in range(N)]
 
point.sort(itemgetter(1))
for i in range(len(point)):
    point[i][1] = i
 
mod = 998244353
 
ans = ((N-4)*pow(2,N,mod)+3*N+4)%mod
 
pow2 = []
a = 1
for i in range(N+1):
    pow2.append(a)
    a *= 2
    a %= mod
 
point.sort(itemgetter(0))
 
bit = BIT([0]*len(point))
 
 
for i,(x,y) in enumerate(point):
    if y > 0:
        ld = bit.sum(y-1)
        #ls = i//2
    else:
        ld = 0
    lu = i-ld
    rd = y - ld
    ru = N - i - 1 - rd    
    ans += pow2[lu]-1
    ans += pow2[ld]-1
    ans += pow2[ru]-1
    ans += pow2[rd]-1
    ans %= mod
    bit.add(y,1)
 
print(ans)

Buggy submission (verdict: Runtime Error):

class SegmentTree:
    def __init__(self, L, op, default_val):
        self.op = op
        self.default_val = default_val
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.default_val]*(2*self.n-1)

        for i in range(self.sz):
            self.node[i+self.n-1] = L[i]

        for i in range(self.n-2,-1,-1):
            self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def get(self, l, r):
        res = self.default_val
        n = self.n
        if self.sz <= r or 0 > l:
            print("ERROR: the indice are wrong.")
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        n1 = n//2        
        #left
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        n1 = n//2        
        #right
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res

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

point.sort(lambda x: x[1])
for i in range(len(point)):
    point[i][1] = i

mod = 998244353

ans = ((N-4)*pow(2,N,mod)+3*N+4)%mod

pow2 = []
a = 1
for i in range(N+1):
    pow2.append(a)
    a *= 2
    a %= mod

point.sort(lambda x: x[0])

ST = SegmentTree([0]*len(point), lambda a,b:a+b, 0)


for i,(x,y) in enumerate(point):
    if point[i][1] > 0:
        ld = ST.get(0,y-1)
        #ls = i//2
    else:
        ls = 0
    lu = i-ld
    rd = y - ld
    ru = N - i - 1 - rd    
    ans += pow2[lu]-1
    ans += pow2[ld]-1
    ans += pow2[ru]-1
    ans += pow2[rd]-1
    ans %= mod
    ST.add(point[i][1],1)

print(ans)

Buggy submission (verdict: Runtime Error):


class SegmentTree:
    def __init__(self, L, op, default_val):
        self.op = op
        self.default_val = default_val
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.default_val]*(2*self.n-1)

        for i in range(self.sz):
            self.node[i+self.n-1] = L[i]

        for i in range(self.n-2,-1,-1):
            self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def get(self, l, r):
        res = self.default_val
        n = self.n
        if self.sz <= r or 0 > l:
            print("ERROR: the indice are wrong.")
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        n1 = n//2        
        #left
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        n1 = n//2        
        #right
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res

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

point.sort(lambda x: x[1])
for i in range(len(point)):
    point[i][1] = i

mod = 998244353

ans = ((N-4)*pow(2,N,mod)+3*N+4)%mod

pow2 = []
a = 1
for i in range(N+1):
    pow2.append(a)
    a *= 2
    a %= mod

point.sort(lambda x: x[0])

ST = SegmentTree([0]*len(y), lambda a,b:a+b, 0)


for i in range(len(point)):
    if point[i][1] > 0:
        ls = ST.get(0,point[i][1]-1)
    else:
        ls = 0
    rs = i-ls
    ans += pow2[ls]-1
    ans += pow2[rs]-1
    ans %= mod
    ST.add(point[i][1],1)

point.sort(lambda x: x[0],reverse=True)

ST = SegmentTree([0]*len(y), lambda a,b:a+b, 0)

for i in range(len(point)):
    if point[i][1] > 0:
        ls = ST.get(0,point[i][1]-1)
    else:
        ls = 0
    rs = i-ls
    ans += pow2[ls]-1
    ans += pow2[rs]-1
    ans %= mod
    ST.add(point[i][1],1)

print(ans)

Buggy submission (verdict: Runtime Error):


class SegmentTree:
    def __init__(self, L, op, default_val):
        self.op = op
        self.default_val = default_val
        self.sz = len(L)
        self.n = 1
        self.s = 1
        while self.n < self.sz:
            self.n *= 2
            self.s += 1
        self.node = [self.default_val]*(2*self.n-1)

        for i in range(self.sz):
            self.node[i+self.n-1] = L[i]

        for i in range(self.n-2,-1,-1):
            self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def get(self, l, r):
        res = self.default_val
        n = self.n
        if self.sz <= r or 0 > l:
            print("ERROR: the indice are wrong.")
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        n1 = n//2        
        #left
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        n1 = n//2        
        #right
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res

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

x = []
y = []
for p in point:
    x.append(p[0])
    y.append(p[1])

x.sort()
y.sort()

x_dict = {}
y_dict = {}

for i in range(len(x)):
    x_dict[x[i]] = i

for i in range(len(y)):
    y_dict[y[i]] = i

mod = 998244353

ans = (N*(pow(2,N,mod)-1))%mod


point.sort(lambda x: x[0])

ST = SegmentTree([0]*len(y), lambda a,b:a+b, 0)


for i in range(len(point)):
    if y_dict[point[i][1]] > 0:
        #ls = ST.get(0,y_dict[point[i][1]]-1)
        ls = N
    else:
        ls = 0
    rs = i-ls
    ans -= 4*(pow(2,i,mod)-1)
    ans += pow(2,ls,mod)-1
    ans += pow(2,rs,mod)-1
    ans %= mod
    ST.add(y_dict[point[i][1]],1)

point.sort(lambda x: x[0],reverse=True)

ST = SegmentTree([0]*len(y), lambda a,b:a+b, 0)

for i in range(len(point)):
    if y_dict[point[i][1]] > 0:
        #ls = ST.get(0,y_dict[point[i][1]]-1)
        ls = N
    else:
        ls = 0
    rs = i-ls
    ans += pow(2,ls,mod)-1
    ans += pow(2,rs,mod)-1
    ans %= mod
    ST.add(y_dict[point[i][1]],1)

print(ans)