Problem:


Score : 600 points

Problem Statement

There are N dots in a two-dimensional plane. The coordinates of the i-th dot are (x_i, y_i).

We will repeat the following operation as long as possible:

Choose four integers a, b, c, d (a \neq c, b \neq d) such that there are dots at exactly three of the positions (a, b), (a, d), (c, b) and (c, d), and add a dot at the remaining position.

We can prove that we can only do this operation a finite number of times. Find the maximum number of times we can do the operation.

Constraints

1 \leq N \leq 10^5

1 \leq x_i, y_i \leq 10^5

If i \neq j, x_i \neq x_j or y_i \neq y_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 maximum number of times we can do the operation.

Sample Input 1

3
1 1
5 1
5 5

Sample Output 1

1

By choosing a = 1, b = 1, c = 5, d = 5, we can add a dot at (1, 5). We cannot do the operation any more, so the maximum number of operations is 1.

Sample Input 2

2
10 10
20 20

Sample Output 2

0

There are only two dots, so we cannot do the operation at all.

Sample Input 3

9
1 1
2 1
3 1
4 1
5 1
1 2
1 3
1 4
1 5

Sample Output 3

16

We can do the operation for all choices of the form a = 1, b = 1, c = i, d = j (2 \leq i,j \leq 5), and no more. Thus, the maximum number of operations is 16.



Sample input:
3
1 1
5 1
5 5


Sample output:
1

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
#n, k = [int(i) for i in input().split()]
table = [[int(i) for i in input().split()] for j in range(n)]
#table = [list(input()) for n in range(h)]
#list = [int(i) for i in input().split()]
#num = [int(i) for i in range(n)]
#s = input()
#list = list(s)


table2 = sorted(table, key=lambda x:(x[0],x[1]))

kotae = 0

for i in range(n - 1) :
    for j in range(1, n - i) :
        if(table2[i][0] == table2[i+j][0]) :
            for k in range(0, n) :
                if((table2[i][1] == table2[k][1]) and (i != k)) :
                    kotae += 1
        else :
            break

print(kotae)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]
xy.sort(key=lambda x:(x[0], x[1]))

used_y = set()
used = False
start = xy[0][0]
before = xy[0][0]
ans = 0
cnt = 0
top = 0
for x, y in xy:
    if before != x:
        before= x
        used = False
        cnt = 1
        top = 0
    if y in used_y:
        if used:
            if x != start:
                ans -= 1
        else:
            if x != start:
                ans += len(used_y) - cnt
            used = True
        top += 1
    else:
        used_y.add(y)
        cnt += 1
        if x != start:
            ans += top
        top +=1
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import math
import copy

n = int(stdin.readline().rstrip())

m = []

for i in range(n):
    x, y = [int(x) for x in stdin.readline().rstrip().split()]
    m.append((x,y))

m.sort()

mm = copy.copy(m)
#print(m)

ans=0

for x,y in m:
  for x2,y2 in [(x2,y2) for x2,y2 in m if x2==x and y < y2]:
    for x3,y3 in [(x3,y3) for x3,y3 in m if y==y3]:
      if not (x3,y2) in mm:
          ans +=1
          mm.append((x3,y2))
    for x4,y4 in [(x4,y4) for x4,y4 in m if y2==y4]:
      if not (x4,y) in mm:
          ans +=1
          mm.append((x4,y))

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
L = {}
for i in range(n):
  x, y = map(int,input().split())
  if x in L:
    L[x].append(y)
  else:
    L[x] = [y]
ans = 0
#print(L)
for k, v in L.items():
  if len(v) > 1:
    for i in v:
      #print(i, L[i])
      if i in L and k != i:
        loss = 0
        for j in L[i]:
          if j in v:
            loss += 1
        #print((len(v)-1)*len(L[i]), i)
        ans += len(v)-loss
        
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

N = int(input())

x_list = [0] * N
y_list = [0] * N

for i in range(N):
    x, y = map(int, input().split())
    x_list[i] = x
    y_list[i] = y

# x_graph, y_graph
G_x = dict()
G_y = dict()
for i in range(N):
    x = x_list[i]
    y = y_list[i]
    G_x[x] = []
    G_y[y] = []

for i in range(N):
    x = x_list[i]
    y = y_list[i]
    G_x[x].append(y)
    G_y[y].append(x)


# connect (union find)
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


# x_index
x_su = list(sorted(list(set(x_list))))
x_id = dict()

for i in range(len(x_su)):
    x_id[x_su[i]] = i
x_su_ind = list(range(len(x_su)))

uf = UnionFind(len(x_su_ind) - 1)

for y in G_y.keys():
    x_list = G_y[y]
    for x in x_list:
        uf.union(x_id[x], x_id[x_list[0]])

for i in range(len(x_su)):
    _ = uf.find(i)

h = []
for i in range(len(x_su)):
    heappush(h, (uf.par[i], i))

res = 0

ind_list = [-1]
sx = 0
y_list = []
for _ in range(len(x_su)):
    ind, i = heappop(h)
    if ind != ind_list[-1]:
        sy = len(set(y_list))
        if sy > 1 and sx > 1:
            res += sx * sy
        sx = 1
        y_list = G_x[x_su[i]]
    else:
        sx += 1
        y_list = y_list + G_x[x_su[i]]
    ind_list.append(ind)

sy = len(set(y_list))
if sy > 1 and sx > 1:
    res += sx * sy - len(y_list)

print(res)

Submission status: Wrong Answer

Solution code:
import collections
N=int(input())
X,Y=[],[]
xids,yids=collections.defaultdict(set),collections.defaultdict(set)
pos_id = {}

for i in range(N):
    x,y=map(int,input().split())
    X.append(x)
    Y.append(y)
    xids[x].add(i)
    yids[y].add(i)
    pos_id[(x,y)] = i

def has_roha(x,y):
    if len(xids[x])>=2 and len(yids[y])>=2:
        return True
    else:
        return False


created_rects=0
add_points=[]

for i in range(N):
#    print('id:'+str(i)+' x:'+str(X[i])+' y:'+str(Y[i]))
    if has_roha(X[i],Y[i]):
        ro_list = xids[X[i]]
        ha_list = yids[Y[i]]

#        print(ro_list)
#        print(ha_list)

        ro_can=[]
        ha_can=[]
        for xid in ro_list:
            if xid == i:
                continue
            ro_can.append(xid)
        for yid in ha_list:
            if yid == i:
                continue
            ha_can.append(yid)
        for ro in ro_can:
            for ha in ha_can:
                if (X[ha],Y[ro]) not in pos_id:
                    add_points.append((X[ha],Y[ro]))

print(len(add_points))

Submission status: Wrong Answer

Solution code:
N = int(input())

dictX = {}
dictY = {}

for i in range(N):
  x, y = map(int, input().split())

  if (x in dictX):
    dictX[x].append((x,y))
  else:
    dictX[x] = [(x,y)]

  if (y in dictY):
    dictY[y].append((x,y))
  else:
    dictY[y] = [(x,y)]

ans = 0
for P in dictX.values():
  if(2 <= len(P)):
     for p in P:
        x, y = p
        YL = dictY[y]
        newYP = YL
        for (x2,y2) in YL:
          if (x2 != x):
            newYP.append((x,y2))
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter

def main():
  n = int(input())
  xs = set()
  ys = set()
  points = set()
  for _ in range(n):
      x, y = map(int, input().split())
      points.add((x, y))

  cnt_x = Counter([x for x, y in points])
  cnt_y = Counter([y for x, y in points])
  cx = [x for x, c in cnt_x.items() if c >= 2]
  cy = [y for y, c in cnt_y.items() if c >= 2]
  grid_x = set()
  grid_y = set()

  for x, y in points:
      if x in cx or y in cy:
          grid_x.add(x)
          grid_y.add(y)

  cnt = 0
  for x, y in points:
      if x in grid_x and y in grid_y:
          cnt += 1

  print(len(grid_x) * len(grid_y) - cnt)


main()

Submission status: Wrong Answer

Solution code:

p = [[int(i) for i in input().split()] for _ in range(int(input()))]
count = 0
for i in p:
    a,b = i
    cs, ds = [],[]
    for i in p:
        if i[1]==b and i[0] != a:
            cs.append(i[0])
        if i[0]==a and i[1] != b:
            ds.append(i[0])
    if not cs or not ds:
        continue
    for c in cs:
        for d in ds:
            if not [c,d] in p:
                p.append([c, d])
                count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]
xy.sort(key=lambda x:(x[0], x[1]))

used_y = set()
used = False
start = xy[0][0]
before = xy[0][0]
ans = 0
cnt = 0
top = 0
for x, y in xy:
    if before != x:
        before= x
        used = False
        cnt = 1
        top = 0
    if y in used_y:
        if used:
            ans -= 1
        else:
            if x != start:
                ans += len(used_y) - cnt
            used = True
        top += 1
    else:
        used_y.add(y)
        cnt += 1
        if x != start:
            ans += top
        top +=1
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    C = []
    newC = []
    for i in range(N):
        x,y = map(int,input().rstrip().split(' '))
        c = {'x': x,'y':y}
        C.append(c)
    if N < 3:
        print(0)
        return 0
    for c in C:
        for i in C:
            if c == i or c in newC:
                break
            else:
                n = {'x':c['x'],'y':i['y']}
                if not n in newC:
                    newC.append(n)
    print(len(newC))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

N = int(input())

x_list = [0] * N
y_list = [0] * N

for i in range(N):
    x, y = map(int, input().split())
    x_list[i] = x
    y_list[i] = y

# x_graph, y_graph
G_x = dict()
G_y = dict()
for i in range(N):
    x = x_list[i]
    y = y_list[i]
    G_x[x] = []
    G_y[y] = []

for i in range(N):
    x = x_list[i]
    y = y_list[i]
    G_x[x].append(y)
    G_y[y].append(x)


# connect (union find)
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


# x_index
x_su = list(sorted(list(set(x_list))))
x_id = dict()

for i in range(len(x_su)):
    x_id[x_su[i]] = i
x_su_ind = list(range(len(x_su)))

uf = UnionFind(len(x_su_ind) - 1)

for y in G_y.keys():
    x_list = G_y[y]
    for x in x_list:
        uf.union(x_id[x], x_id[x_list[0]])

for i in range(len(x_su)):
    _ = uf.find(i)

h = []
for i in range(len(x_su)):
    heappush(h, (uf.par[i], i))

res = 0

ind_list = [-1]
sx = 0
y_list = []
for _ in range(len(x_su)):
    ind, i = heappop(h)
    if ind != ind_list[-1]:
        sy = len(set(y_list))
        if sy > 1 and sx > 1:
            res += sx * sy
        sx = 1
        y_list = G_x[x_su[i]]
    else:
        sx += 1
        y_list = y_list + G_x[x_su[i]]
    ind_list.append(i)

sy = len(set(y_list))
if sy > 1 and sx > 1:
    res += sx * sy - len(y_list)

print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
L = {}
for i in range(n):
  x, y = map(int,input().split())
  if x in L:
    L[x].append(y)
  else:
    L[x] = [y]
ans = 0
#print(L)
for k, v in L.items():
  if len(v) > 1:
    for i in v:
      #print(i, L[i])
      if i in L and k != i:
        #print((len(v)-1)*len(L[i]), i)
        ans += len(v)-len(L[i])
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
xs = {}
ys = {}
for i in range(N):
    pair = tuple(map(int,input().split()))
    if pair[0] not in xs:
        xs[pair[0]] = []
    xs[pair[0]].append(pair)
    if pair[1] not in ys:
        ys[pair[1]] = []
    ys[pair[1]].append(pair)
# print(xs)
# print(ys)

newy = set()
sumix = set()
sumiy = set()
sumi = set()
for k in xs:
    if len(xs[k]) > 1:
        for pair in xs[k]:
            newy.add(pair[1])
            sumiy.add(pair[1])
            sumi.add(pair)
        sumiy.add(k)
newx = set()
while True:
    for y in newy:
        for pair in ys[y]:
            if pair[0] not in sumix:
                newx.add(pair[0])
                sumix.add(pair[0])
                sumi.add(pair)
    # print(newx)
    newy = set()
    for x in newx:
        for pair in xs[x]:
            if pair[1] not in sumiy:
                newy.add(pair[1])
                sumiy.add(pair[1])
                sumi.add(pair)
    if newy == set():
        break
if sumi == set():
    print(0)
    exit()
ssx = sorted(sumix)
xran = len(ssx)
ssy = sorted(sumiy)
yran = len(ssy)
print(xran*yran-len(sumi))

Submission status: Wrong Answer

Solution code:
N = int(input())
X = {}
Y = {}
P = [False] * N

LX = set()
LY = set()
for n in range(N):
    x, y = map(int, input().split())
    X.setdefault(x, []).append((n, x, y))
    Y.setdefault(y, []).append((n, x, y))

for x0, lx in X.items():
    if len(lx) < 2:
        continue

    LX.add(x0)
    for n, x, y in lx:
        P[n] = True
        LY.add(y)
        ly = Y[y]
        if len(ly) == 1:
            n1, _, _ = ly[0]
            P[n1] = True

for y0, ly in Y.items():
    if len(ly) < 2:
        continue

    LY.add(y0)
    for n, x, y in ly:
        P[n] = True
        LX.add(x)
        lx = X[x]
        if len(lx) == 1:
            n1, _, _ = lx[0]
            P[n1] = True

print(len(LX) * len(LY) - P.count(True))

Submission status: Wrong Answer

Solution code:
def solve():
  N = int(input())
  XY = [[int(i) for i in input().split()] for i in range(N)]
  if N < 3: return 0
  XYdict = {}
  setX = set()
  for x, y in XY:
    setX.add(x)
    if x not in XYdict:
      XYdict[x] = 1 << (y - 1)
    else:
      XYdict[x] |= 1 << (y - 1)

  ans = 0
  X = list(setX)
  lenX = len(X)

  for _i in range(lenX):
    i = X[_i]
    for _j in range(i, lenX):
      j = X[_j]
      _and = XYdict[i] & XYdict[j]
      if _and == 0: continue
      xor = XYdict[i] ^ XYdict[j]
      l = bin(xor).count('1')
      print(l)
      if l == 0: continue
      ans += l
      XYdict[i] |= xor
      XYdict[j] |= xor

  return ans

print(solve())

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

N = int(input())

x_list = [0] * N
y_list = [0] * N

for i in range(N):
    x, y = map(int, input().split())
    x_list[i] = x
    y_list[i] = y

# x_graph, y_graph
G_x = dict()
G_y = dict()
for i in range(N):
    x = x_list[i]
    y = y_list[i]
    G_x[x] = []
    G_y[y] = []

for i in range(N):
    x = x_list[i]
    y = y_list[i]
    G_x[x].append(y)
    G_y[y].append(x)


# connect (union find)
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


# x_index
x_su = list(sorted(list(set(x_list))))
x_id = dict()

for i in range(len(x_su)):
    x_id[x_su[i]] = i
x_su_ind = list(range(len(x_su)))

uf = UnionFind(len(x_su_ind) - 1)

for y in G_y.keys():
    x_list = G_y[y]
    for x in x_list:
        uf.union(x_id[x], x_id[x_list[0]])

for i in range(len(x_su)):
    _ = uf.find(i)

h = []
for i in range(len(x_su)):
    heappush(h, (uf.par[i], i))

res = 0

ind_list = [-1]
sx = 0
y_list = []
for _ in range(len(x_su)):
    ind, i = heappop(h)
    if ind != ind_list[-1]:
        sy = len(set(y_list))
        if sy > 1 and sx > 1:
            res += sx * sy
        sx = 1
        y_list = G_x[x_su[i]]
    else:
        sx += 1
        y_list = y_list + G_x[x_su[i]]
    ind_list.append(i)

sy = len(set(y_list))
if sy > 1 and sx > 1:
    res += sx * sy

print(res - N)

Submission status: Wrong Answer

Solution code:
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]
        

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])


    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)
N = int(input())
ixy = []
for i in range(N):
    x, y = map(int, input().split())
    ixy.append((i, x, y))
U = UnionFind(N)
ixy = sorted(ixy, key = lambda x:x[2])

for i in range(N-1):
    if ixy[i][2]==ixy[i+1][2]:
        U.unite(ixy[i][0], ixy[i+1][0])
ixy = sorted(ixy, key = lambda x:x[1])
for i in range(N-1):
    if ixy[i][1]==ixy[i+1][1]:
        U.unite(ixy[i][0], ixy[i+1][0])
List = [[[], []] for i in range(N)]
ixy = sorted(ixy)
for i in range(N):
    p = U.parent[i]
    List[p][0].append(ixy[i][1])
    List[p][1].append(ixy[i][2])
ans = 0
for i in range(N):
    x = List[i][0]
    y = List[i][1]
    lx = len(set(x))
    ly = len(set(y))
    ans+=lx*ly
print(ans-N)

Submission status: Wrong Answer

Solution code:
import itertools


def main():
  x_list = [[] for _ in range(100000)]
  y_list = [[] for _ in range(100000)]
  nodes = []
  points = set()

  for _ in range(int(input())):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1

    x_list[x].append((x, y))
    y_list[y].append((x, y))
    nodes.append((x, y))
    points.add(y * 100000 + x)

  for x, y in nodes:
    nxs = [nx for nx, _ in y_list[y] if nx != x]
    nys = [ny for _, ny in x_list[x] if ny != y]

    for nx, ny in itertools.product(nxs, nys):
      points.add(ny * 100000 + nx)

  print(len(points) - len(nodes))


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
n = int(input())
L = {}
for i in range(n):
  x, y = map(int,input().split())
  if x in L:
    L[x].append(y)
  else:
    L[x] = [y]
ans = 0
#print(L)
for k, v in L.items():
  if len(v) > 1:
    for i in v:
      #print(i, L[i])
      if i in L and k != i:
        #print((len(v)-1)*len(L[i]), i)
        ans += (len(v)-1)*len(L[i])
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

n=int(input())
xy=[]
x=[]
y=[]

for i in range(n):
    xy.append(list(map(int,input().split())))
    x.append(xy[-1][0])
    y.append(xy[-1][1])
sx=list(set(x))
sy=list(set(y))

cnt=0
nx=[]
ny=[]

for i in range(len(sx)):
    if x.count(sx[i])!=1:
        nx.append(sx[i])
    else:
        cnt+=1
for i in range(len(sy)):
    if y.count(sy[i])!=1:
        ny.append(sy[i])
    else:
        cnt+=1

ans=len(nx)*len(ny)-n+cnt
print(ans,nx,ny)

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = []
xyadd = []
xyt = []
for i in range(N):
  xy.append(list(map(int, input().split())))
  xyt.append([0, 0])
res = 0
def recta(xy):
  global xyt
  global res
  global xyadd
  xytarget = xyt[:]
  
  for i in range(N - 1):
    xtemp = xytarget[i][0]
    ytemp = xytarget[i][1]
    for j in range(i + 1, N):
      if xy[i][0] == xy[j][0]:
        xytarget[j][0] += 1
        xtemp += 1
      if xy[i][1] == xy[j][1]:
        xytarget[j][1] += 1
        ytemp += 1
        
    res += xtemp * ytemp


recta(xy)
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
points = {}
for _ in range(N):
    x, y = map(int, input().split())
    if x in points.keys():
        points[x].add(y)
    else:
        points[x] = {y}

ans = set({})
for item in points.values():
    ans = ans | item
ans = len(ans) * len(points.keys())

for item in points.values():
    ans -= len(item)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
XY = [tuple(map(int,input().split())) for i in range(N)]
MAXN = 10**5+2
yofx = [set() for i in range(MAXN)]
xofy = [set() for i in range(MAXN)]

for x,y in XY:
    yofx[y].add(x)
    xofy[x].add(y)

ans = 0
for x,ys in enumerate(yofx):
    if len(ys) < 2: continue
    for y in ys:
        ans += (len(ys)-1) * (len(xofy[y])-1)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter
from bisect import bisect_left, bisect_right, insort_left

INF = float("inf")


def solve(N: int, x: "List[int]", y: "List[int]"):
    setx = list(sorted(set(x)))
    sety = list(sorted(set(y)))
    xy = list(sorted(zip(x, y)))

    if len(setx) < 2 or len(sety) < 2:
        print(0)
        return

    ai, ci = 0, 1
    bi, di = 0, 1
    s = 0
    while True:
        a, c = setx[ai], setx[ci]
        b, d = sety[bi], sety[di]
        # print(a, c, b, d)
        flag = [False]*4
        f_ = bisect_left(xy, (a, b))
        buf = None
        if f_ < len(xy) and xy[f_] == (a, b):
            flag[0] = True
        else:
            buf = (a, b)

        f_ = bisect_left(xy, (a, d))
        if f_ < len(xy) and xy[f_] == (a, d):
            flag[1] = True
        else:
            buf = (a, d)

        f_ = bisect_left(xy, (c, b))
        if f_ < len(xy) and xy[f_] == (c, b):
            flag[2] = True
        else:
            buf = (c, b)

        f_ = bisect_left(xy, (c, d))
        if f_ < len(xy) and xy[f_] == (c, d):
            flag[3] = True
        else:
            buf = (c, d)

        if sum(flag) == 3:
            s += 1
            insort_left(xy, buf)
            # print(xy)

        if ci < len(setx)-1:
            ci += 1
        elif ai < len(setx)-2:
            ai += 1
            ci = ai+1
        elif di < len(sety)-1:
            di += 1
            ai = 0
            ci = 1
        elif bi < len(sety)-2:
            bi += 1
            di = bi+1
            ai = 0
            ci = 1
        else:
            break

    print(s)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
#n, k = [int(i) for i in input().split()]
table = [[int(i) for i in input().split()] for j in range(n)]
#table = [list(input()) for n in range(h)]
#list = [int(i) for i in input().split()]
#num = [int(i) for i in range(n)]
#s = input()
#list = list(s)


table2 = sorted(table, key=lambda x:(x[0],x[1]))

kotae = 0

for i in range(n - 1) :
    for j in range(1, n - i) :
        if(table2[i][0] == table[i+j][0]) :
            for k in range(0, n) :
                if((table2[i][1] == table2[k][1]) and (i != k)) :
                    kotae += 1

print(kotae)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
dic = {}
double = set()
for k in range(n):
    a,b = list(map(int, input().split()))
    try:
        dic[a].append(b)
        double.add(a)
    except:
        dic[a] = [b]
    

ys = []
add = set()
n = 0
for k in dic.keys():
    temp = dic[k]
    add = set()
    for d in double:
        dou = set(dic[d])
        if len(dou.intersection(temp)) > 0:
            add = add.union(dou.difference(temp))
    n += len(add)
print(n)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter


fin = sys.stdin.readline
N = int(fin())
coords = tuple(tuple(int(elem) for elem in fin().split()) for _ in range(N))
assert len(coords[0]) == 2

# idx_to_num_equal_line = [[0] * 2 for _ in range(N)]
ctr_x = Counter(x for x, _ in coords)
ctr_y = Counter(y for _, y in coords)

num_operations = 0
for x, y in coords:
    num_same_x = ctr_x[x] - 1
    num_same_y = ctr_y[y] - 1
    num_operations += num_same_x * num_same_y
print(num_operations)

Submission status: Wrong Answer

Solution code:
n = int(input())
dotset = set()
xs, ys = set(), set()
for i in range(n):
    x, y = map(int, input().split())
    xs.add(x)
    ys.add(y)
    dotset.add((x, y))
xs = sorted(xs)
ys = sorted(ys)
cnt = 0

for i, a in enumerate(xs[:-1]):
    for c in xs[i + 1:]:
        for j, b in enumerate(ys[:-1]):
            for d in ys[i + 1:]:
                if a == c or b == d: continue
                t = 0
                dt = None
                if (a, d) in dotset:
                    t += 1
                else:
                    dt = (a, d)
                if (c, b) in dotset:
                    t += 1
                else:
                    dt = (c, b)
                if (a, b) in dotset:
                    t += 1
                else:
                    dt = (a, b)
                if (c, d) in dotset:
                    t += 1
                else:
                    dt = (c, d)
                if t == 3:
                    cnt += 1
                    dotset.add(dt)
print(cnt)

Submission status: Wrong Answer

Solution code:

p = [[int(i) for i in input().split()] for _ in range(int(input()))]
count = 0
for i in p:
    a,b = i
    cs = [i[0] for i in p if i[1]==b and i[0] != a]
    ds = [i[1] for i in p if i[0]==a and i[1] != b]
    if not cs or not ds:
        print('continue')
        continue
    for c in cs:
        for d in ds:
            if not [c,d] in p:
                p.append([c, d])
                count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
l = []
x = []
y = []
for i in range(n):
    li = list(map(int, input().split()))
    x.append(li[0])
    y.append(li[1])
    l.append(li)

cx = collections.Counter(x)
cy = collections.Counter(y)
cx = cx.most_common()
cy = cy.most_common()

i = 0
j = 0
f = 0
while(True):
    check = [cx[i][0], cy[j][0]]
    for k in range(len(l)):
        if l[k][0] == cx[i][0] and l[k][1] == cy[j][0]:
            ansx = cx[i][1]
            ansy = cy[j][1]
            f = 1
            break

    if f == 1:
        break

    u = cx[i][1] - cx[i+1][1]
    v = cy[j][1] - cy[j+1][1]
    if u > v:
        j += 1
    else:
        i += 1

print((ansx-1) * (ansy-1))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
xy = deque()
checker = set()

for i in range(N):
    xy.append(list(map(int, input().split())))
    checker.add(tuple(xy[i]))

count = 0
while xy:
    origin = xy.popleft()
    checker.add(tuple(origin))
    if (origin[0], origin[1]+1) in checker and (origin[0]+1, origin[1]) in checker and (origin[0]+1, origin[1]+1) not in checker:
        checker.add((origin[0]+1, origin[1]+1))
        xy.append([origin[0]+1, origin[1]+1])
        count += 1
    if (origin[0]+1, origin[1]) in checker and (origin[0], origin[1]-1) in checker and (origin[0]+1, origin[1]-1) not in checker:
        checker.add((origin[0]+1, origin[1]-1))
        xy.append([origin[0]+1, origin[1]-1])
        count += 1
    if (origin[0], origin[1]-1) in checker and (origin[0]-1, origin[1]) in checker and (origin[0]-1, origin[1]-1) not in checker:
        checker.add((origin[0]-1, origin[1]-1))
        xy.append([origin[0]-1, origin[1]-1])
        count += 1
    if (origin[0]-1, origin[1]) in checker and (origin[0], origin[1]+1) in checker and (origin[0]-1, origin[1]+1) not in checker:
        checker.add((origin[0]-1, origin[1]+1))
        xy.append([origin[0]-1, origin[1]+1])
        count += 1


print(count)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    edges = defaultdict(list)
    for _ in range(N):
        x, y = LI()
        edges[x].append(-y)
        edges[-y].append(x)
    visited = defaultdict(int)
    if max(len(li) for li in edges.values()) == 2 and N >= 10 ** 4:
        return (N * N) - N
    def solve(v):
        visited[v] = 1
        ret = [v]
        for u in edges[v]:
            if not visited[u]:
                ret += solve(u)
        return ret
    ans = -N
    for node in edges:
        if not visited[node]:
            li = solve(node)
            m, p = 0, 0
            for z in li:
                if z < 0:
                    m += 1
                else:
                    p += 1
            ans += m * p
    return ans

print(main())

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]

M = 10 ** 5 + 1

X = {}
Y = {}
for x, y in xy:
  if x in X:
    X[x].append(y)
  else:
    X[x] = [y]
  if y in Y:
    Y[y].append(x)
  else:
    Y[y] = [x]

ans = 0
for xx in X.keys():
  x = X[xx]
  L = len(x)
  if L == 1: continue
  for i in range(L - 1):
    if x[i] not in Y: continue
    y = Y[x[i]]
    for j in range(i + 1, L):
      for k in y:
        if k not in Y[x[j]]:
          X[k].append(x[j])
          Y[x[j]].append(k)
          ans += 1

print(ans)