Problem:


Score : 600 points

Problem Statement

We have a set S of N points in a two-dimensional plane. The coordinates of the i-th point are (x_i, y_i). The N points have distinct x-coordinates and distinct y-coordinates.

For a non-empty subset T of S, let f(T) be the number of points contained in the smallest rectangle, whose sides are parallel to the coordinate axes, that contains all the points in T. More formally, we define f(T) as follows:

f(T) :=  (the number of integers i (1 \leq i \leq N) such that a \leq x_i \leq b and c \leq y_i \leq d, where a, b, c, and d are the minimum x-coordinate, the maximum x-coordinate, the minimum y-coordinate, and the maximum y-coordinate of the points in T)

Find the sum of f(T) over all non-empty subset T of S. Since it can be enormous, print the sum modulo 998244353.

Constraints

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

-10^9 \leq x_i, y_i \leq 10^9

x_i \neq x_j (i \neq j)

y_i \neq y_j (i \neq j)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print the sum of f(T) over all non-empty subset T of S, modulo 998244353.

Sample Input 1

3
-1 3
2 1
3 -2

Sample Output 1

13

Let the first, second, and third points be P_1, P_2, and P_3, respectively. S = \{P_1, P_2, P_3\} has seven non-empty subsets, and f has the following values for each of them:

f(\{P_1\}) = 1

f(\{P_2\}) = 1

f(\{P_3\}) = 1

f(\{P_1, P_2\}) = 2

f(\{P_2, P_3\}) = 2

f(\{P_3, P_1\}) = 3

f(\{P_1, P_2, P_3\}) = 3

The sum of these is 13.

Sample Input 2

4
1 4
2 1
3 3
4 2

Sample Output 2

34

Sample Input 3

10
19 -11
-3 -12
5 3
3 -15
8 -14
-9 -20
10 -9
0 2
-7 17
6 -6

Sample Output 3

7222

Be sure to print the sum modulo 998244353.



Sample input:
3
-1 3
2 1
3 -2


Sample output:
13

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
import bisect
N = int(input())
P = [list(map(int,input().split())) for i in [0]*N]
class SegmentTree:
    def __init__(self,data):
        N = len(data)
        self.l = 2**((N-1).bit_length())
        self.data = [0]*self.l + data + [0]*(self.l-N)
        for i in range(self.l-1,0,-1):
            self.data[i] = self.data[2*i] + self.data[2*i+1]

    def set(self,i,val):
        i += self.l
        self.data[i] = val
        i = i//2
        while i > 0:
            self.data[i] = self.data[2*i] + self.data[2*i+1]
            i = i//2

    def get(self,i,j):
        i += self.l
        j += self.l
        s = 0
        while j-i > 0:
            if i & 1:
                s += self.data[i]
                i += 1
            if j & 1:
                s += self.data[j-1]
                j -= 1
            i = i//2
            j = j//2
        return s

X,Y = map(list,zip(*P))
X.sort()
Y.sort()
compY = {y:cp for cp,y in enumerate(Y)}
Psorted = sorted(P)
compP = [[n,compY[y]] for n,(_,y) in enumerate(Psorted)]

n1s = []
seg = SegmentTree([0]*N)
for _,y in compP[::-1]:
    n1s.append(seg.get(y,N))
    seg.set(y,1)
n1s = n1s[::-1]

ans = 0
for n,(x,y) in enumerate(Psorted):
    lower = bisect.bisect_left(Y,y)
    upper = N-1-lower
    left = n
    right = N-n-1
    n1 = n1s[n]
    n2 = upper - n1
    n3 = left - n2
    n4 = right - n1
    temp = pow(2,lower,MOD) + pow(2,upper,MOD) + pow(2,left,MOD) + pow(2,right,MOD)
    temp -= pow(2,n1,MOD)+pow(2,n2,MOD)+pow(2,n3,MOD)+pow(2,n4,MOD)
    temp += 1 # empty
    ans += pow(2,N,MOD) - temp
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
input = sys.stdin.readline
mod = 998244353
n = int(input())
p2t = [1]
for i in range(n):
  p2t.append(p2t[-1]*2%mod)
xy = [list(map(int,input().split())) for i in range(n)]
xy.sort()
yls = list(zip(*xy))[1]
yd = [(yls[i],i) for i in range(n)]
yd.sort()
yind = [0 for i in range(n)]
for i in range(n):
  y = yd[i][1]
  yind[y] = i
xyd = []
for i in range(n):
  xyd.append((i,yind[i]))
ans = 0
bit = Bit(n+1)
xyd.sort()
for i in range(n):
  x,y = xyd[i]
  upper = n-y-1
  right = n-x-1
  ld = bit.sum(y+1)
  ru = upper+right+ld-n+1
  rd = right-ru
  lu = upper-ru
  p2lu = p2t[lu]
  p2rd = p2t[rd]
  p2ru = p2t[ru]
  p2ld = p2t[ld]
  ans += ((p2lu-1)*(p2rd-1)*(p2t[ld+ru])%mod+(p2ld-1)*(p2ru-1)*(p2t[lu+rd])%mod+
  p2t[n-1]-(p2lu-1)*(p2rd-1)*(p2ld-1)*(p2ru-1)%mod)
  ans %= mod
  bit.add(y+1,1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
input = sys.stdin.readline
mod = 998244353
n = int(input())
p2t = [1]
for i in range(n):
  p2t.append(p2t[-1]*2%mod)
xy = [list(map(int,input().split())) for i in range(n)]
xls,yls = list(zip(*xy))
xi = [(xls[i],i) for i in range(n)]
yi = [(yls[i],i) for i in range(n)]
xi.sort()
yi.sort()
xd = [0 for i in range(n)]
yd = [0 for i in range(n)]
for i in range(n):
  x,ix = xi[i]
  y,iy = yi[i]
  xd[ix] = i
  yd[iy] = i
ans = 0
bit = Bit(n+1)
xyd = list(zip(xd,yd))
xyd.sort()
for i in range(n):
  x,y = xyd[i]
  upper = n-y-1
  right = n-x-1
  ld = bit.sum(y+1)
  ru = upper+right+ld-n+1
  rd = right-ru
  lu = upper-ru
  p2lu = p2t[lu]
  p2rd = p2t[rd]
  p2ru = p2t[ru]
  p2ld = p2t[ld]
  ans += ((p2lu-1)*(p2rd-1)*(p2t[ld+ru])%mod+(p2ld-1)*(p2ru-1)*(p2t[lu+rd])%mod+
  p2t[n-1]-(p2lu-1)*(p2rd-1)*(p2ld-1)*(p2ru-1)%mod)
  ans %= mod
  bit.add(y+1,1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
input = sys.stdin.readline
mod = 998244353
n = int(input())
p2t = [1]
for i in range(n):
  p2t.append(p2t[-1]*2%mod)
xy = [list(map(int,input().split())) for i in range(n)]
xls,yls = list(zip(*xy))
xi = [(xls[i],i) for i in range(n)]
yi = [(yls[i],i) for i in range(n)]
xi.sort()
yi.sort()
xd = [0 for i in range(n)]
yd = [0 for i in range(n)]
for i in range(n):
  x,ix = xi[i]
  y,iy = yi[i]
  xd[ix] = i
  yd[iy] = i
ans = 0
bit = Bit(n+1)
xyd = list(zip(xd,yd))
xyd.sort()
for i in range(n):
  x,y = xyd[i]
  upper = n-y-1
  right = n-x-1
  ld = bit.sum(y+1)
  ru = upper+right+ld-n+1
  rd = right-ru
  lu = upper-ru
  p2lu = p2t[lu]
  p2rd = p2t[rd]
  p2ru = p2t[ru]
  p2ld = p2t[ld]
  ans += ((p2lu-1)*(p2rd-1)*(p2t[ld+ru])%mod+(p2ld-1)*(p2ru-1)*(p2t[lu+rd])%mod+
  p2t[n-1]-(p2lu-1)*(p2rd-1)*(p2ld-1)*(p2ru-1)%mod)
  ans %= mod
  bit.add(y+1,1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
input = sys.stdin.readline
mod = 998244353
ptable = [1,2]
for i in range(20):
  ptable.append(ptable[-1]**2%mod)
def p2(x):
  if x == 0:
    return 1
  ret = 1
  for i in range(20):
    if x&1<<i:
      ret = (ret*ptable[i+1])%mod
  return ret
n = int(input())
p2t = [p2(i) for i in range(n+1)]
xy = [list(map(int,input().split())) for i in range(n)]
xls,yls = list(zip(*xy))
xi = [(xls[i],i) for i in range(n)]
yi = [(yls[i],i) for i in range(n)]
xi.sort()
yi.sort()
xd = [0 for i in range(n)]
yd = [0 for i in range(n)]
for i in range(n):
  x,ix = xi[i]
  y,iy = yi[i]
  xd[ix] = i
  yd[iy] = i
ans = 0
bit = Bit(n+1)
xyd = list(zip(xd,yd))
xyd.sort()
for i in range(n):
  x,y = xyd[i]
  upper = n-y-1
  right = n-x-1
  ld = bit.sum(y+1)
  ru = upper+right+ld-n+1
  rd = right-ru
  lu = upper-ru
  p2lu = p2t[lu]
  p2rd = p2t[rd]
  p2ru = p2t[ru]
  p2ld = p2t[ld]
  ans += ((p2lu-1)*(p2rd-1)*(p2t[ld+ru])+(p2ld-1)*(p2ru-1)*(p2t[lu+rd])+
  p2t[n-1]-(p2lu-1)*(p2rd-1)*(p2ld-1)*(p2ru-1))
  ans %= mod
  bit.add(y+1,1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
input = sys.stdin.readline
mod = 998244353
ptable = [1,2]
for i in range(20):
  ptable.append(ptable[-1]**2%mod)
def p2(x):
  if x == 0:
    return 1
  ret = 1
  for i in range(20):
    if x&1<<i:
      ret = (ret*ptable[i+1])%mod
  return ret
n = int(input())
xy = [list(map(int,input().split())) for i in range(n)]
xls,yls = map(list,list(zip(*xy)))
xi = [(xls[i],i) for i in range(n)]
yi = [(yls[i],i) for i in range(n)]
xi.sort()
yi.sort()
xd = [0 for i in range(n)]
yd = [0 for i in range(n)]
for i in range(n):
  x,ix = xi[i]
  y,iy = yi[i]
  xd[ix] = i
  yd[iy] = i
ans = 0
bit = Bit(n+1)
xyd = list(zip(xd,yd))
xyd.sort()
for i in range(n):
  x,y = xyd[i]
  upper = n-y-1
  right = n-x-1
  ld = bit.sum(y+1)
  ru = upper+right+ld-n+1
  rd = right-ru
  lu = upper-ru
  ans += ((p2(lu)-1)*(p2(rd)-1)*(p2(ld+ru))+(p2(ld)-1)*(p2(ru)-1)*(p2(lu+rd))+
  p2(n-1)-(p2(lu)-1)*(p2(rd)-1)*(p2(ld)-1)*(p2(ru)-1))
  ans %= mod
  bit.add(y+1,1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
input = sys.stdin.readline
mod = 998244353
ptable = [1,2]
for i in range(20):
  ptable.append(ptable[-1]**2%mod)
def p2(x):
  if x == 0:
    return 1
  ret = 1
  for i in range(20):
    if x&1<<i:
      ret = (ret*ptable[i+1])%mod
  return ret
n = int(input())
xy = [list(map(int,input().split())) for i in range(n)]
xls,yls = map(list,list(zip(*xy)))
xi = [(xls[i],i) for i in range(n)]
yi = [(yls[i],i) for i in range(n)]
xi.sort()
yi.sort()
xd = [0 for i in range(n)]
yd = [0 for i in range(n)]
for i in range(n):
  x,ix = xi[i]
  y,iy = yi[i]
  xd[ix] = i
  yd[iy] = i
ans = 0
bit = Bit(n+1)
xyd = list(zip(xd,yd))
xyd.sort()
for i in range(n):
  x,y = xyd[i]
  upper = n-y-1
  right = n-x-1
  ld = bit.sum(y+1)
  ru = upper+right+ld-n+1
  rd = right-ru
  lu = upper-ru
  ans += ((p2(lu)-1)*(p2(rd)-1)*(p2(ld+ru))+(p2(ld)-1)*(p2(ru)-1)*(p2(lu+rd))+
  p2(n-1)-(p2(lu)-1)*(p2(rd)-1)*(p2(ld)-1)*(p2(ru)-1))
  ans %= mod
  bit.add(y+1,1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
input = sys.stdin.readline
mod = 998244353
def p2(x): return pow(2,x,mod)
n = int(input())
xy = [list(map(int,input().split())) for i in range(n)]
xls,yls = map(list,list(zip(*xy)))
xi = [(xls[i],i) for i in range(n)]
yi = [(yls[i],i) for i in range(n)]
xi.sort()
yi.sort()
xd = [0 for i in range(n)]
yd = [0 for i in range(n)]
for i in range(n):
  x,ix = xi[i]
  y,iy = yi[i]
  xd[ix] = i
  yd[iy] = i
ans = 0
bit = Bit(n+1)
xyd = list(zip(xd,yd))
xyd.sort()
for i in range(n):
  x,y = xyd[i]
  upper = n-y-1
  right = n-x-1
  ld = bit.sum(y+1)
  ru = upper+right+ld-n+1
  rd = right-ru
  lu = upper-ru
  ans += ((p2(lu)-1)*(p2(rd)-1)*(p2(ld+ru))+(p2(ld)-1)*(p2(ru)-1)*(p2(lu+rd))+
  p2(n-1)-(p2(lu)-1)*(p2(rd)-1)*(p2(ld)-1)*(p2(ru)-1))
  ans %= mod
  bit.add(y+1,1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
mod=998244353
from collections import defaultdict
DX=defaultdict(int)
DY=defaultdict(int)
XY,X,Y=[],[],[]
for _ in range(n):
  x,y=map(int,input().split())
  X.append(x)
  Y.append(y)
  XY.append((x,y))
X.sort()
Y.sort()
XY.sort(key=lambda x:x[0])
for i,x in enumerate(X):
  DX[x]=i+1
for i,y in enumerate(Y):
  DY[y]=i+1
XY2=[]
for x,y in XY:
  XY2.append((DX[x],DY[y]))
A=[[0]*4 for _ in range(n)]

n_max=2*10**5
nn=n_max.bit_length()+1
BIT=[0]*(2**nn)
BIT.insert(0,0)
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s
def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT

for i in range(n):
  x,y=XY2[i]
  ct=bitsum(BIT,y)
  A[i][2]+=ct
  A[i][1]+=i-ct
  bitadd(BIT,y,1)

BIT=[0]*(2**nn)
BIT.insert(0,0)
for i in range(n)[::-1]:
  x,y=XY2[i]
  ct=bitsum(BIT,y)
  A[i][3]+=ct
  A[i][0]+=(n-1-i)-ct
  bitadd(BIT,y,1)

def f(x):
  return pow(2,x,mod)

ans=0
for a,b,c,d in A:
  ans+=2*f(a+b+c+d)-f(a+b)-f(b+c)-f(c+d)-f(d+a)+f(a)+f(b)+f(c)+f(d)-1
  ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353

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

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

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

N, *XY = map(int, open(0).read().split())
X, Y = XY[::2], XY[1::2]

memo = {y: i for i, y in enumerate(sorted(Y))}
Y = [y for x, y in sorted(zip(X, map(memo.get, Y)), key=lambda p: p[0])]

P = [1]
for i in range(N):
    P.append(P[-1] * 2 % mod)

ans = P[N - 1] * N % mod
bit = BIT(N)
for i, y in enumerate(Y):
    bit.add(y + 1, 1)

    ld = bit.sum(y)
    lu = i - ld

    rd = y - ld
    ru = N - y - 1 - lu

    A, B, C, D = P[ru], P[lu], P[ld], P[rd]

    ans += ((C - 1) * (A - 1) % mod) * (B * D % mod) % mod
    ans += ((B - 1) * (D - 1) % mod) * (C * A % mod) % mod
    ans -= ((C - 1) * (A - 1) % mod) * ((D - 1) * (B - 1) % mod) % mod
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/abc136/tasks/abc136_f

やっぱりある点基準に寄与を考える？
長方形を決めるのは最小2点、最大4点

では、逆に含まないのを考える？

0 1
 X
3 2

ある点を中心に,4つの象限に分ける
この時、Xが含まれないのは、差が2(mod4)の範囲に含まれる点が同時に存在しないこと
よって、

(2^N-1) - (0,1内のみ点からなる部分集合) - (1,2)-(2,3)-(3,0) + (0のみから～)+(1)+(2)+(3)
となる (0この場合は毎回ちゃんと取り除いておく)

よって、座圧して2次元累積和を用いれば、O(N)で解ける??
2次元累積和、使えなくね

その点より上下左右にある数、ならO(N)でわかる
→問題は上式の+ (0のみから～)+(1)+(2)+(3)の部分

左上の数を方程式で解ける？
→むりぽ

上と左の点をbitsetでもっておいてand演算？　→　できなくはないけど速くなるか…？

======答えを見る======
BITを持っておき、xが小さい方から見ていく
y座標に関して座圧して置き既にみたBITと、まだ見てないBITを持っておけば、
log(N)で第1象限にある点の数を計算できる
→片方の軸基準で考えるのは典型か…(2D Plane 2N Pointsっぽい)

"""

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret

N = int(input())

xyi = []
yi  = []

for i in range(N):

    x,y = map(int,input().split())
    xyi.append([x,y,i])
    yi.append([y,i])

xyi.sort()
yi.sort()

i_to_psy = [None] * N
for j in range(N):

    y,i = yi[j]
    i_to_psy[i] = j+1

YetBIT = [0] * (N+1)
AftBIT = [0] * (N+1)

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

powlis = [1]
for i in range(N+10):
    powlis.append(powlis[-1]*2%mod)

for i in range(N):
    bitadd(i+1,1,YetBIT)

for loop in range(N):

    x,y,ind = xyi[loop]
    psy = i_to_psy[ind]
    #print (psy)
    bitadd(psy,-1,YetBIT)
    
    L = N-loop-1
    R = loop

    ul = bitsum(psy,YetBIT)
    ur = bitsum(psy,AftBIT)

    U = ul+ur
    D = N - U - 1
    dl = L - ul
    dr = R - ur

    now = (powlis[ul]+powlis[ur]+powlis[dl]+powlis[dr]-4) - (powlis[U]+powlis[D]+powlis[L]+powlis[R]-4)
    #print (ind,ul,ur,dl,dr)
    now %= mod
    ans += now
    ans %= mod

    bitadd(psy,1,AftBIT)


print (ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter


class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目にvalを加える"""
        i += 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)
      

n = int(input())
info = [tuple([i] + list(map(int, input().split()))) for i in range(n)]
MOD = 998244353

ans = [[0] * n for i in range(4)]

info = sorted(info, key = itemgetter(1))
to_ind = {x[2]: ind for ind, x in enumerate(sorted(info, key = itemgetter(2)))}

bit = BIT(n)
for j in range(n):
    i, x, y = info[j]
    tmp = bit.get_sum(0, to_ind[y])
    ans[2][i]= tmp
    ans[3][i] = j - tmp
    bit.add(to_ind[y], 1)
    
bit = BIT(n)
for j in range(n)[::-1]:
    i, x, y = info[j]
    tmp = bit.get_sum(0, to_ind[y])
    ans[1][i] = tmp
    ans[0][i] = n - j - 1 - tmp
    bit.add(to_ind[y], 1)

res = 0
pow2 = [1] * (n + 10)
for i in range(n):
    pow2[i + 1] = pow2[i] * 2
    pow2[i + 1] %= MOD

ans = list(zip(*ans))
for a1, a2, b1, b2 in ans:
    res += (pow2[a1] - 1) * (pow2[b1] - 1) * (pow2[a2 + b2])
    res %= MOD
    res += (pow2[a2] - 1) * (pow2[b2] - 1) * (pow2[a1 + b1])
    res %= MOD
    res += pow2[n - 1]
    res -= (pow2[a1] - 1) * (pow2[a2] - 1) * (pow2[b1] - 1) * (pow2[b2] - 1)
    res %= MOD
print(res % MOD)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter


class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目にvalを加える"""
        i += 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)
      

n = int(input())
info = [tuple([i] + list(map(int, input().split()))) for i in range(n)]
MOD = 998244353

ans = [[0, 0, 0, 0] for i in range(n)]

info = sorted(info, key = itemgetter(1))
to_ind = {x[2]: ind for ind, x in enumerate(sorted(info, key = itemgetter(2)))}

bit = BIT(n)
for j in range(n):
    i, x, y = info[j]
    tmp = bit.get_sum(0, to_ind[y])
    ans[i][2] = tmp
    ans[i][3] = j - tmp
    bit.add(to_ind[y], 1)
    
bit = BIT(n)
for j in range(n)[::-1]:
    i, x, y = info[j]
    tmp = bit.get_sum(0, to_ind[y])
    ans[i][1] = tmp
    ans[i][0] = n - j - 1 - tmp
    bit.add(to_ind[y], 1)

res = 0
pow2 = [1] * (n + 10)
for i in range(n):
    pow2[i + 1] = pow2[i] * 2
    pow2[i + 1] %= MOD

for i in range(n):
    a1, a2, b1, b2 = ans[i]
    res += (pow2[a1] - 1) * (pow2[b1] - 1) * (pow2[a2 + b2])
    res %= MOD
    res += (pow2[a2] - 1) * (pow2[b2] - 1) * (pow2[a1 + b1])
    res %= MOD
    res += pow2[n - 1]
    res -= (pow2[a1] - 1) * (pow2[a2] - 1) * (pow2[b1] - 1) * (pow2[b2] - 1)
    res %= MOD
print(res % MOD)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter


class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目にvalを加える"""
        i += 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)
      

n = int(input())
info = [tuple([i] + list(map(int, input().split()))) for i in range(n)]
MOD = 998244353

ans = [[0, 0, 0, 0] for i in range(n)]

info = sorted(info, key = itemgetter(1))
to_ind = {x[2]: ind for ind, x in enumerate(sorted(info, key = itemgetter(2)))}

bit = BIT(n)
for j in range(n):
    i, x, y = info[j]
    tmp = bit.get_sum(0, to_ind[y])
    ans[i][2] = tmp
    ans[i][3] = j - tmp
    bit.add(to_ind[y], 1)
    
bit = BIT(n)
for j in range(n)[::-1]:
    i, x, y = info[j]
    tmp = bit.get_sum(0, to_ind[y])
    ans[i][1] = tmp
    ans[i][0] = n - j - 1 - tmp
    bit.add(to_ind[y], 1)

res = 0
pow2 = [1] * (n + 10)
for i in range(n):
    pow2[i + 1] = pow2[i] * 2
    pow2[i + 1] %= MOD

for i in range(n):
    a1, a2, b1, b2 = ans[i]
    res += (pow2[a1] - 1) * (pow2[b1] - 1) * (pow2[a2 + b2])
    res += (pow2[a2] - 1) * (pow2[b2] - 1) * (pow2[a1 + b1])
    res += pow2[n - 1]
    res -= (pow2[a1] - 1) * (pow2[a2] - 1) * (pow2[b1] - 1) * (pow2[b2] - 1)
    res %= MOD
print(res % MOD)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from operator import itemgetter
    input = sys.stdin.readline

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

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

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

    mod = 998244353
    N = int(input())
    X_raw = [0] * N
    Y_raw = [0] * N
    for i in range(N):
        x, y = map(int, input().split())
        X_raw[i] = x
        Y_raw[i] = y

    val2idx_X = {}
    val2idx_Y = {}
    for i in range(N):
        val2idx_X[X_raw[i]] = i
        val2idx_Y[Y_raw[i]] = i
    X_raw.sort()
    Y_raw.sort()
    X = [0] * N
    Y = [0] * N
    for i in range(N):
        X[val2idx_X[X_raw[i]]] = i+1
        Y[val2idx_Y[Y_raw[i]]] = i+1

    XY = [(x, y) for x, y in zip(X, Y)]
    XY.sort(key=itemgetter(0))

    bit_ul = Bit(N + 2)
    bit_ur = Bit(N+2)
    ul = []
    ur = []
    for x, y in XY:
        ul.append(bit_ul.sum(y))
        ur.append(bit_ur.sum(N+1) - bit_ur.sum(y))
        bit_ul.add(y, 1)
        bit_ur.add(y, 1)

    bit_dl = Bit(N + 2)
    bit_dr = Bit(N + 2)
    dl = []
    dr = []
    for x, y in reversed(XY):
        dl.append(bit_dl.sum(y))
        dr.append(bit_dr.sum(N + 1) - bit_dr.sum(y))
        bit_dl.add(y, 1)
        bit_dr.add(y, 1)
    dl.reverse()
    dr.reverse()

    ans = 0
    for i in range(N):
        ans = ((ans + pow(2, N, mod) - 1)%mod
               - (pow(2, ul[i]+ur[i], mod)
               + pow(2, dl[i]+dr[i], mod))%mod
               - (pow(2, ul[i]+dl[i], mod)
               + pow(2, ur[i]+dr[i], mod))%mod
               + (pow(2, ul[i], mod)
               + pow(2, ur[i], mod))%mod
               + (pow(2, dl[i], mod)
               + pow(2, dr[i], mod))%mod)%mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from operator import itemgetter
    input = sys.stdin.readline

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

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

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

    mod = 998244353
    N = int(input())
    X_raw = [0] * N
    Y_raw = [0] * N
    for i in range(N):
        x, y = map(int, input().split())
        X_raw[i] = x
        Y_raw[i] = y

    val2idx_X = {}
    val2idx_Y = {}
    for i in range(N):
        val2idx_X[X_raw[i]] = i
        val2idx_Y[Y_raw[i]] = i
    X_raw.sort()
    Y_raw.sort()
    X = [0] * N
    Y = [0] * N
    for i in range(N):
        X[val2idx_X[X_raw[i]]] = i+1
        Y[val2idx_Y[Y_raw[i]]] = i+1

    XY = [(x, y) for x, y in zip(X, Y)]
    XY.sort(key=itemgetter(0))

    bit_ul = Bit(N + 2)
    bit_ur = Bit(N+2)
    ul = []
    ur = []
    for x, y in XY:
        ul.append(bit_ul.sum(y))
        ur.append(bit_ur.sum(N+1) - bit_ur.sum(y))
        bit_ul.add(y, 1)
        bit_ur.add(y, 1)

    bit_dl = Bit(N + 2)
    bit_dr = Bit(N + 2)
    dl = []
    dr = []
    for x, y in reversed(XY):
        dl.append(bit_dl.sum(y))
        dr.append(bit_dr.sum(N + 1) - bit_dr.sum(y))
        bit_dl.add(y, 1)
        bit_dr.add(y, 1)
    dl.reverse()
    dr.reverse()

    ans = 0
    for i in range(N):
        ans = (ans + pow(2, N, mod) - 1
               - pow(2, ul[i]+ur[i], mod)
               - pow(2, dl[i]+dr[i], mod)
               - pow(2, ul[i]+dl[i], mod)
               - pow(2, ur[i]+dr[i], mod)
               + pow(2, ul[i], mod)
               + pow(2, ur[i], mod)
               + pow(2, dl[i], mod)
               + pow(2, dr[i], mod))%mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

MOD = 998244353
class Rsum():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [0] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Add(self, x, val):
		x += self.n-1
		self.node[x] += val
		while x > 0:
			x = (x-1)//2
			self.node[x] = self.node[2*x+1] + self.node[2*x+2]
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = 0
		while L<R:
			if R & 1:
				R -= 1
				s += self.node[R-1]
			if L & 1:
				s += self.node[L-1]
				L += 1
			L >>= 1
			R >>= 1
		return s

n = int(input())
d = []
for i in range(n):
	x, yy = map(int, input().split())
	d.append((x, yy, i))
y = [-1 for _ in range(n)]
d.sort(key=lambda x: x[1])
for i, x in enumerate(d):
	y[x[2]] = i

d.sort()
lus = [-1 for _ in range(n)]
lds = [-1 for _ in range(n)]
rus = [-1 for _ in range(n)]
rds = [-1 for _ in range(n)]

st = Rsum(n)
for i in range(n):
	pnt = y[d[i][2]]
	g = st.Get(pnt, n)
	lus[i] = g
	lds[i] = i - g
	st.Add(pnt, 1)

st = Rsum(n)
for i in range(n-1, -1, -1):
	pnt = y[d[i][2]]
	g = st.Get(pnt, n)
	rus[i] = g
	rds[i] = n-1-i - g
	st.Add(pnt, 1)

pws = [1]
for _ in range(n-1):
	pws.append((pws[-1] * 2) % MOD)

ans = (n * pws[n-1]) % MOD
for lu, ld, ru, rd in zip(lus, lds, rus, rds):
	ans += ((pws[lu]-1) * (pws[rd]-1))
	ans += ((pws[ld]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[rd]-1))
	ans += ((pws[lu]-1) * (pws[rd]-1) * (pws[ru]-1))
	ans += ((pws[ld]-1) * (pws[rd]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1) * (pws[rd]-1))
	ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

MOD = 998244353
class Rsum():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [0] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Add(self, x, val):
		x += self.n-1
		self.node[x] += val
		while x > 0:
			x = (x-1)//2
			self.node[x] = self.node[2*x+1] + self.node[2*x+2]
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = 0
		while L<R:
			if R & 1:
				R -= 1
				s += self.node[R-1]
			if L & 1:
				s += self.node[L-1]
				L += 1
			L >>= 1
			R >>= 1
		return s

n = int(input())
d = []
for i in range(n):
	x, yy = map(int, input().split())
	d.append((x, yy, i))
y = [-1 for _ in range(n)]
d.sort(key=lambda x: x[1])
for i, x in enumerate(d):
	y[x[2]] = i

d.sort()
lus = [-1 for _ in range(n)]
lds = [-1 for _ in range(n)]
rus = [-1 for _ in range(n)]
rds = [-1 for _ in range(n)]

st = Rsum(n)
for i in range(n):
	pnt = y[d[i][2]]
	lus[i] = st.Get(pnt, n)
	lds[i] = i - lus[i]
	st.Add(pnt, 1)
del st
st = Rsum(n)
for i in range(n-1, -1, -1):
	pnt = y[d[i][2]]
	rus[i] = st.Get(pnt, n)
	rds[i] = n-1-i - rus[i]
	st.Add(pnt, 1)

pws = [1]
for _ in range(n-1):
	pws.append((pws[-1] * 2) % MOD)

ans = (n * pws[n-1]) % MOD
for lu, ld, ru, rd in zip(lus, lds, rus, rds):
	ans += ((pws[lu]-1) * (pws[rd]-1))
	ans += ((pws[ld]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[rd]-1))
	ans += ((pws[lu]-1) * (pws[rd]-1) * (pws[ru]-1))
	ans += ((pws[ld]-1) * (pws[rd]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1) * (pws[rd]-1))
	ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

MOD = 998244353
class Rsum():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [0] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Add(self, x, val):
		x += self.n-1
		self.node[x] += val
		while x > 0:
			x = (x-1)//2
			self.node[x] = self.node[2*x+1] + self.node[2*x+2]
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = 0
		while L<R:
			if R & 1:
				R -= 1
				s += self.node[R-1]
			if L & 1:
				s += self.node[L-1]
				L += 1
			L >>= 1
			R >>= 1
		return s

n = int(input())
d = []
for i in range(n):
	x, yy = map(int, input().split())
	d.append((x, yy, i))
y = [-1 for _ in range(n)]
d.sort(key=lambda x: x[1])
for i, x in enumerate(d):
	y[x[2]] = i

d.sort()
lus = [-1 for _ in range(n)]
lds = [-1 for _ in range(n)]
rus = [-1 for _ in range(n)]
rds = [-1 for _ in range(n)]

st = Rsum(n)
for i in range(n):
	pnt = y[d[i][2]]
	lus[i] = st.Get(pnt, n)
	lds[i] = i - lus[i]
	st.Add(pnt, 1)

st = Rsum(n)
for i in range(n-1, -1, -1):
	pnt = y[d[i][2]]
	rus[i] = st.Get(pnt, n)
	rds[i] = n-1-i - rus[i]
	st.Add(pnt, 1)

pws = [1]
for _ in range(n-1):
	pws.append((pws[-1] * 2) % MOD)

ans = (n * pws[n-1]) % MOD
for lu, ld, ru, rd in zip(lus, lds, rus, rds):
	ans += ((pws[lu]-1) * (pws[rd]-1))
	ans += ((pws[ld]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[rd]-1))
	ans += ((pws[lu]-1) * (pws[rd]-1) * (pws[ru]-1))
	ans += ((pws[ld]-1) * (pws[rd]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1) * (pws[rd]-1))
	ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

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

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

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
xy.sort(key=lambda x:x[1])
for i in range(N):
    xy[i][1] = i
xy.sort()

mod = 998244353
p2 = [1]*(N+1)
for i in range(N):
    p2[i+1] = p2[i]*2%mod

bit = BIT(N)

ans = 0

for i in range(N):
    y = xy[i][1]
    bit.add(y,1)
    n1 = i+1-bit.sum(y)
    n2 = i-n1
    n3 = N-y-1-n1
    n4 = N-i-1-n3
    ans += 1
    ans += (p2[n1]-1)+(p2[n2]-1)+(p2[n3]-1)+(p2[n4]-1)
    ans += (p2[n1]-1)*(p2[n2]-1)+(p2[n3]-1)*(p2[n4]-1)+(p2[n1]-1)*(p2[n3]-1)+(p2[n2]-1)*(p2[n4]-1)+2*(p2[n1]-1)*(p2[n4]-1)+2*(p2[n2]-1)*(p2[n3]-1)
    ans += 2*((p2[n1]-1)*(p2[n2]-1)*(p2[n3]-1)+(p2[n1]-1)*(p2[n2]-1)*(p2[n4]-1)+(p2[n1]-1)*(p2[n3]-1)*(p2[n4]-1)+(p2[n2]-1)*(p2[n3]-1)*(p2[n4]-1))
    ans += 2*(p2[n1]-1)*(p2[n2]-1)*(p2[n3]-1)*(p2[n4]-1)
    ans %= mod
print(ans)