Problem:
 Score : 500 points    Problem Statement We have a two-dimensional grid with H \times W squares. There are M targets to destroy in this grid - the position of the i -th target is \left(h_i, w_i \right) .  Takahashi will choose one square in this grid, place a bomb there, and ignite it. The bomb will destroy all targets that are in the row or the column where the bomb is placed. It is possible to place the bomb at a square with a target.  Takahashi is trying to maximize the number of targets to destroy. Find the maximum number of targets that can be destroyed.      Constraints  All values in input are integers.  1 \leq H, W \leq 3 \times 10^5  1 \leq M \leq \min\left(H\times W, 3 \times 10^5\right)  1 \leq h_i \leq H  1 \leq w_i \leq W  \left(h_i, w_i\right) \neq \left(h_j, w_j\right) \left(i \neq j\right)         Input Input is given from Standard Input in the following format:  H  W  M  h_1  w_1  \vdots  h_M  w_M       Output Print the answer.        Sample Input 1 2 3 3
2 2
1 1
1 3      Sample Output 1 3  We can destroy all the targets by placing the bomb at \left(1, 2\right) .       Sample Input 2 3 3 4
3 3
3 1
1 1
1 2      Sample Output 2 3       Sample Input 3 5 5 10
2 5
4 3
2 3
5 5
2 2
5 4
5 3
5 1
3 5
1 4      Sample Output 3 6

Solution (Python):
from collections import Counter
h, w, m = map(int, input().split())
cr = Counter()
cc = Counter()
s = set()
for _ in range(m):
    hi, wi = map(int, input().split())
    s.add((hi, wi))
    cr[hi] += 1
    cc[wi] += 1
cr = sorted(cr.items(), key=lambda x: x[1], reverse=True)
cc = sorted(cc.items(), key=lambda x: x[1], reverse=True)
mxr = cr[0][1]
mxc = cc[0][1]
ans = mxr + mxc - 1
cr = list(filter(lambda x: x[1] == mxr, cr))
cc = list(filter(lambda x: x[1] == mxc, cc))
for i, _ in cr:
    for j, _ in cc:
        if (i, j) not in s:
            print(ans + 1)
            exit()
print(ans)

Solution (Python):
h,w,m=[int(i) for i in raw_input().split()]
r=[0 for i in range(h)]
c=[0 for i in range(w)]
d={}
for i in range(m):
    h1,w1=[int(j)-1 for j in raw_input().split()]
    r[h1]+=1
    c[w1]+=1
    x=str(h1)+'
    d[x]=d.get(x,0)+1
maxx=max(r)
r1=[]
for i in range(len(r)):
    if maxx==r[i]:
        r1.append(i)
maxx=max(c)
c1=[]
for i in range(len(c)):
    if maxx==c[i]:
        c1.append(i)
maxx1=0;flag=0
for i in r1:
    for j in c1:
        x=str(i)+'
        if(d.get(x,0)==0):
            maxx1=max(maxx1,r[i]+c[j])
            flag=1
        else:
            maxx1=max(maxx1,r[i]+c[j]-d[x])
    if flag:
        break
print maxx1

Solution (Python):

import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

h,w,m = ip()
y = [0]*h
x = [0]*w
dt = {}
for i in range(m):
    a,b = ip()
    y[a-1] += 1
    x[b-1] += 1
    dt[(a-1,b-1)] = 1
ans = 0
mx = max(x)
my = max(y)
xx = [i for i in range(w) if x[i] == mx]
yy = [i for i in range(h) if y[i] == my]

for i in xx:
    for j in yy:
        if dt.get((j,i),0):
            ans = max(ans,x[i]+y[j]-1)
        else:
            ans = max(ans,x[i]+y[j])
        if ans == mx+my:
            break
print(ans)

Solution (Python):
I = lambda : list(map(int,input().split()))
h,w,m=I()
x={};y={}
l=[];dic={}
for i in range(m):
  a,b=I()
  l.append([a,b])
  dic[(a,b)]=1
  x[a]=x.get(a,0)+1
  y[b]=y.get(b,0)+1
p,q=max(x.values()),max(y.values())
a,b=[i for i in x if x[i]==p],[i for i in y if y[i]==q]
an=p+q;fl=0
for i in a:
  for j in b:
    if dic.get((i,j),-1)==-1:
      fl=1;break
  if fl:
    break
an-=(fl==0)
print(an)

Solution (Python):
def main():
    H, W, M = map(int, input().split())
    hw = [tuple(list(map(int, input().split()))) for _ in [0]*M]
    hw_set = set(hw)
    h_count = [0 for i in range(H+1)]
    w_count = [0 for i in range(W+1)]
    for h, w in hw:
        h_count[h] += 1
        w_count[w] += 1
    h_m = max(h_count)
    w_m = max(w_count)
    h_list = []
    w_list = []
    for i in range(H+1):
        if h_count[i] == h_m:
            h_list.append(i)
    for i in range(W+1):
        if w_count[i] == w_m:
            w_list.append(i)
    
    for i in h_list:
        for j in w_list:
            if (i, j) not in hw_set:
                print(h_m+w_m)
                return
    print(h_m+w_m-1)


main()

Solution (Python):






H,W,M = map(int,input().split())
targetList = []
rowCount = [0] * H
columnCount = [0] * W
for _ in range(M):
    p,q = map(int,input().split())
    targetList.append((p-1,q-1))
    rowCount[p-1] += 1
    columnCount[q-1] += 1
rowCountLabelled = []
columnCountLabelled = []
for i in range(H):
    rowCountLabelled.append((rowCount[i],i))
for i in range(W):
    columnCountLabelled.append((columnCount[i],i))
rowCountLabelled.sort(reverse = True)
columnCountLabelled.sort(reverse = True)
targetList.sort()
maxi = rowCountLabelled[0][0] + columnCountLabelled[0][0]
isMaxAchievable = False
for elem1 in rowCountLabelled:
    if elem1[0] != rowCountLabelled[0][0]:
        break
    for elem2 in columnCountLabelled:
        if elem2[0] != columnCountLabelled[0][0]:
            break
        target = (elem1[1],elem2[1])
        l = 0
        r = len(targetList) - 1
        while l < r:
            m = (l + r) // 2
            if target == targetList[m]:
                l = m
                r = m
                break
            elif target < targetList[m]:
                r = m-1
            elif target > targetList[m]:
                l = m + 1
        if (l >= len(targetList) or target != targetList[l]) and target != targetList[r]:
            isMaxAchievable = True
            break
    if isMaxAchievable:
        break
if isMaxAchievable:
    print(maxi)
else:
    print(maxi - 1)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from copy import deepcopy

INF = float('inf')


def LI(): return list(map(int, sys.stdin.readline().split()))


def I(): return int(sys.stdin.readline())


def LS(): return sys.stdin.readline().split()


def S(): return sys.stdin.readline().strip()


def IR(n): return [I() for i in range(n)]


def LIR(n): return [LI() for i in range(n)]


def SR(n): return [S() for i in range(n)]


def LSR(n): return [LS() for i in range(n)]


def SRL(n): return [list(S()) for i in range(n)]


def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


mod = 10 ** 9 + 7

h,w,m= LI()
s=set()
D1=defaultdict(int)
D2=defaultdict(int)
for _ in range(m):
    h,w=LI()
    D1[h-1]+=1
    D2[w-1]+=1
    s.add((h-1,w-1))

A=[[v,i] for i,v in D1.items()]+[[-INF,-INF]]
B=[[v,i] for i,v in D2.items()]+[[-INF,-INF]]
A.sort(reverse=True)
B.sort(reverse=True)
a_now=0
b_now=0
ans=-INF
for i in range(3*10**5):
    av,ak=A[a_now]
    bv,bk = B[b_now]
    res=av+bv-int((ak,bk) in s)
    ans=max(ans,res)
    if a_now==len(A)-2 and b_now==len(B)-2:
        break
    elif A[a_now+1][0]+B[b_now][0]>A[a_now][0]+B[b_now+1][0]:
        a_now+=1
    else:
        b_now+=1

print(ans)

Solution (Python):
from collections import defaultdict
import sys

input = sys.stdin.buffer.readline

h, w, m = map(int, input().split())
xkouho = defaultdict(int)
ykouho = defaultdict(int)
kouho = set()
for _ in range(m):
    x, y = map(int, input().split())
    kouho.add((x, y))
    xkouho[x] += 1
    ykouho[y] += 1

max_x = []
max_xval = -1
for key, val in xkouho.items():
    if val > max_xval:
        max_x = [key]
        max_xval = val
    elif val == max_xval:
        max_x.append(key)
    else:
        continue

max_y = []
max_yval = -1
for key, val in ykouho.items():
    if val > max_yval:
        max_y = [key]
        max_yval = val
    elif val == max_yval:
        max_y.append(key)
    else:
        continue
ans = max_xval + max_yval
for x in max_x:
    for y in max_y:
        if (x, y) not in kouho:
            print(ans)
            exit()
ans -= 1
print(ans)

Solution (Python):
H, W, M = map(int, input().split())

objects = set()
sum_h = [0] * W
sum_w = [0] * H
for _ in range(M):
    h, w = map(int, input().split())
    h -= 1
    w -= 1
    objects.add((h, w))
    sum_h[w] += 1
    sum_w[h] += 1

max_sum_h = max(sum_h)
max_sum_w = max(sum_w)

ans = max_sum_h + max_sum_w - 1

arg_max_h = [h for h in range(H) if sum_w[h] == max_sum_w]
arg_max_w = [w for w in range(W) if sum_h[w] == max_sum_h]
for h in arg_max_h:
    for w in arg_max_w:
        if (h, w) not in objects:
            ans = max_sum_h + max_sum_w
            break
    else:
        continue
    break

print(ans)

Solution (Python):
from bisect import bisect_left, bisect_right, insort_right


class SquareSkipList:
    
    
    
    
    
    
    
    
    
    
    def __init__(self, values=None, sorted_=False, square=1000, seed=42, inf=float("inf")):
        
        
        
        
        
        self.square = square
        if values is None:
            self.rand_y = seed
            self.layer1 = [inf]
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            y = seed
            l0 = []
            for v in values:
                y ^= (y & 0x7ffff) << 13
                y ^= y >> 17
                y ^= (y & 0x7ffffff) << 5
                if y % square == 0:
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer1.append(inf)
            layer0.append(l0)
            self.rand_y = y

    def add(self, x):  
        
        y = self.rand_y
        y ^= (y & 0x7ffff) << 13
        y ^= y >> 17
        y ^= (y & 0x7ffffff) << 5
        self.rand_y = y

        if y % self.square == 0:
            layer1, layer0 = self.layer1, self.layer0
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1 + 1, layer0_idx1[idx0:])  
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(self.layer1, x)
            insort_right(self.layer0[idx1], x)

    def remove(self, x):  
        
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            del self.layer1[idx1]
            self.layer0[idx1] += self.layer0.pop(idx1 + 1)
        else:
            del layer0_idx1[idx0]

    def search_higher_equal(self, x):  
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return self.layer1[idx1]
        return layer0_idx1[idx0]

    def search_higher(self, x):  
        idx1 = bisect_right(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_right(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return self.layer1[idx1]
        return layer0_idx1[idx0]

    def search_lower(self, x):  
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == 0:  
            return self.layer1[idx1 - 1]
        return layer0_idx1[idx0 - 1]

    def pop(self, idx):
        
        
        
        layer0 = self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s == idx:
            layer0[i] += layer0.pop(i + 1)
            return self.layer1.pop(i)
        else:
            return layer0[i].pop(idx - s)

    def pop_max(self):
        
        
        if self.layer0[-1]:
            return self.layer0[-1].pop()
        else:
            del self.layer0[-1]
            return self.layer1.pop(-2)

    def __getitem__(self, item):
        
        layer0 = self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= item:
                break
        if s == item:
            return self.layer1[i]
        else:
            return layer0[i][item - s]

    def min(self):  
        return self.layer0[0][0] if self.layer0[0] else self.layer1[0]

    def max(self):  
        return self.layer0[-1][-1] if self.layer0[-1] else self.layer1[-2]

    def merge(self, r):  
        self.layer0[-1] += r.layer0[0]
        self.layer0 += r.layer0[1:]
        del self.layer1[-1]
        self.layer1 += r.layer1

    def split(self, k):  
        idx1 = bisect_left(self.layer1, k)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, k)
        r = SquareSkipList(square=self.square, seed=self.rand_y)
        r.layer1 = self.layer1[idx1:]
        r.layer0 = [layer0_idx1[idx0:]] + self.layer0[idx1 + 1:]
        del self.layer1[idx1:-1], layer0_idx1[idx0:], self.layer0[idx1 + 1:]
        return r

    def print(self):
        print(self.layer1)
        print(self.layer0)

    def __iter__(self):
        layer1 = self.layer1
        layer0 = self.layer0
        idx1 = idx0 = 0
        layer0_idx1 = layer0[idx1]
        while True:
            if len(layer0_idx1) == idx0:
                if len(layer1) - 1 == idx1:
                    return
                yield layer1[idx1]
                idx1 += 1
                layer0_idx1 = layer0[idx1]
                idx0 = 0
            else:
                yield layer0_idx1[idx0]
                idx0 += 1


import sys
from operator import itemgetter
from itertools import groupby
def main():
    H, W, M = map(int, sys.stdin.buffer.readline().split())
    hw = map(int, sys.stdin.buffer.read().split())
    hw = sorted(zip(hw, hw), key=itemgetter(0))
    Cnt_w = [0] * (W+1)
    for _, w in hw:
        Cnt_w[w] += 1
    sl = SquareSkipList(Cnt_w[:])
    ans = 0
    for h, group in groupby(hw, key=itemgetter(0)):
        group = list(group)
        for _, w in group:
            cnt = Cnt_w[w]
            sl.remove(cnt)
            sl.add(cnt-1)
            Cnt_w[w] -= 1
        an = len(group) + sl.max()
        if ans < an:
            ans = an
        for _, w in group:
            cnt = Cnt_w[w]
            sl.remove(cnt)
            sl.add(cnt+1)
            Cnt_w[w] += 1
    print(ans)

main()

Solution (Python):
from bisect import bisect_left, bisect_right, insort_right


class SquareSkipList:
    
    
    
    
    
    
    
    
    
    
    def __init__(self, values=None, sorted_=False, square=1000, seed=42, inf=float("inf")):
        
        
        
        
        
        self.square = square
        if values is None:
            self.rand_y = seed
            self.layer1 = [inf]
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            y = seed
            l0 = []
            for v in values:
                y ^= (y & 0x7ffff) << 13
                y ^= y >> 17
                y ^= (y & 0x7ffffff) << 5
                if y % square == 0:
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer1.append(inf)
            layer0.append(l0)
            self.rand_y = y

    def add(self, x):  
        
        y = self.rand_y
        y ^= (y & 0x7ffff) << 13
        y ^= y >> 17
        y ^= (y & 0x7ffffff) << 5
        self.rand_y = y

        if y % self.square == 0:
            layer1, layer0 = self.layer1, self.layer0
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1 + 1, layer0_idx1[idx0:])  
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(self.layer1, x)
            insort_right(self.layer0[idx1], x)

    def remove(self, x):  
        
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            del self.layer1[idx1]
            self.layer0[idx1] += self.layer0.pop(idx1 + 1)
        else:
            del layer0_idx1[idx0]

    def search_higher_equal(self, x):  
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return self.layer1[idx1]
        return layer0_idx1[idx0]

    def search_higher(self, x):  
        idx1 = bisect_right(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_right(layer0_idx1, x)
        if idx0 == len(layer0_idx1):
            return self.layer1[idx1]
        return layer0_idx1[idx0]

    def search_lower(self, x):  
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == 0:  
            return self.layer1[idx1 - 1]
        return layer0_idx1[idx0 - 1]

    def pop(self, idx):
        
        
        
        layer0 = self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s == idx:
            layer0[i] += layer0.pop(i + 1)
            return self.layer1.pop(i)
        else:
            return layer0[i].pop(idx - s)

    def pop_max(self):
        
        
        if self.layer0[-1]:
            return self.layer0[-1].pop()
        else:
            del self.layer0[-1]
            return self.layer1.pop(-2)

    def __getitem__(self, item):
        
        layer0 = self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= item:
                break
        if s == item:
            return self.layer1[i]
        else:
            return layer0[i][item - s]

    def min(self):  
        return self.layer0[0][0] if self.layer0[0] else self.layer1[0]

    def max(self):  
        return self.layer0[-1][-1] if self.layer0[-1] else self.layer1[-2]

    def merge(self, r):  
        self.layer0[-1] += r.layer0[0]
        self.layer0 += r.layer0[1:]
        del self.layer1[-1]
        self.layer1 += r.layer1

    def split(self, k):  
        idx1 = bisect_left(self.layer1, k)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, k)
        r = SquareSkipList(square=self.square, seed=self.rand_y)
        r.layer1 = self.layer1[idx1:]
        r.layer0 = [layer0_idx1[idx0:]] + self.layer0[idx1 + 1:]
        del self.layer1[idx1:-1], layer0_idx1[idx0:], self.layer0[idx1 + 1:]
        return r

    def print(self):
        print(self.layer1)
        print(self.layer0)

    def __iter__(self):
        layer1 = self.layer1
        layer0 = self.layer0
        idx1 = idx0 = 0
        layer0_idx1 = layer0[idx1]
        while True:
            if len(layer0_idx1) == idx0:
                if len(layer1) - 1 == idx1:
                    return
                yield layer1[idx1]
                idx1 += 1
                layer0_idx1 = layer0[idx1]
                idx0 = 0
            else:
                yield layer0_idx1[idx0]
                idx0 += 1


import sys
from operator import itemgetter
from itertools import groupby
def main():
    H, W, M = map(int, sys.stdin.buffer.readline().split())
    hw = map(int, sys.stdin.buffer.read().split())
    hw = sorted(zip(hw, hw), key=itemgetter(0))
    Cnt_w = [0] * (W+1)
    for _, w in hw:
        Cnt_w[w] += 1
    sl = SquareSkipList(Cnt_w[:])
    ans = 0
    for h, group in groupby(hw, key=itemgetter(0)):
        group = list(group)
        for _, w in group:
            cnt = Cnt_w[w]
            sl.remove(cnt)
            sl.add(cnt-1)
            Cnt_w[w] -= 1
        an = len(group) + sl.max()
        if ans < an:
            ans = an
        for _, w in group:
            cnt = Cnt_w[w]
            sl.remove(cnt)
            sl.add(cnt+1)
            Cnt_w[w] += 1
    print(ans)

main()

Solution (Python):
h,w,m=map(int,input().split())
p=[]
for i in range(m):
  p.append(tuple(map(lambda x:int(x)-1,input().split())))
p.sort()
hc=[0 for i in range(h)]
wc=[0 for i in range(w)]
hm=0
wm=0
hp=[]
wp=[]
for i in p:
  hc[i[0]]+=1
  if hc[i[0]]>hm:
    hm=hc[i[0]]
    hp=[i[0]]
  elif hc[i[0]]==hm:
    hp.append(i[0])
   
  wc[i[1]]+=1
  if wc[i[1]]>wm:
    wm=wc[i[1]]
    wp=[i[1]]
  elif wc[i[1]]==wm:
    wp.append(i[1])

f=0
for i in hp:
  for j in wp:
    s,t=0,m
    while t-s>1:
      x=(s+t)//2
      if p[x]>(i,j):
        t=x
      else:
        s=x
    if p[s]!=(i,j):
      f=1
      break
  if f:
    break

print(hm+wm-1+f)

Solution (Python):
from collections import defaultdict
H,W,M = map(int,input().split())
bomb = [set() for _ in range(H+1)]
hdic = [0]*(H+1)
wdic = [0]*(W+1)
for i in range(M):
    hi,wi = map(int,input().split())
    hdic[hi] += 1
    wdic[wi] += 1
    bomb[hi].add(wi)
hmax = 0
hlist = []
wmax = 0
wlist = []
for i in range(1,H+1):
    if hdic[i] > hmax:
        hlist = [i]
        hmax = hdic[i]
    elif hdic[i] == hmax:
        hlist.append(i)
for i in range(1,W+1):
    if wdic[i] > wmax:
        wlist = [i]
        wmax = wdic[i]
    elif wdic[i] == wmax:
        wlist.append(i)
for i in hlist:
    for j in wlist:
        if j not in bomb[i]:
            print(hmax+wmax)
            exit()
print(hmax+wmax-1)

Solution (Python):
from copy import *

def init(N,node,unit,func):
  n=1
  while n<N:
    n<<=1
  for i in range(n*2-1):
    if len(node)<=i:
      node.append(deepcopy(unit))
    else:
      node[i]=deepcopy(unit)
  node.append(func)
  node.append(unit)

def upd(node,x,a):
  y=(len(node)>>1)+x-1
  node[y]=a
  while y:
    y=(y-1)>>1
    node[y]=node[-2](node[(y<<1)+1],node[(y+1)<<1])

def query(node,l_q,r_q,k,l_m,r_m):
  if r_q<=l_m or r_m<=l_q:
    return node[-1]
  if l_q<=l_m and r_m<=r_q:
    return node[k]
  l_a=query(node,l_q,r_q,2*k+1,l_m,(l_m+r_m)//2)
  r_a=query(node,l_q,r_q,2*k+2,(l_m+r_m)//2,r_m)
  return node[-2](l_a,r_a)

H,W,N=map(int,input().split())
S=[[] for i in range(H+1)]
T=[]
init(W+3,T,0,lambda x,y:max(x,y))
X=[tuple(map(int,input().split())) for i in range(N)]
for i in range(N):
  S[X[i][0]].append(X[i][1])
  upd(T,X[i][1]+1,T[(len(T)>>1)+X[i][1]]+1)
P=0
Q=0
for i in range(1,H+1):
  Q=len(S[i])
  for j in range(len(S[i])):
    upd(T,S[i][j]+1,T[(len(T)>>1)+S[i][j]]-1)
  P=max(P,Q+T[0])
  for j in range(len(S[i])):
    upd(T,S[i][j]+1,T[(len(T)>>1)+S[i][j]]+1)
print(P)

Solution (Python):
h, w, m = map(int, input().split())
memo_h = [0 for _ in range(h)]
memo_w = [0 for _ in range(w)]

where = []
for _ in range(m):
    x, y = map(int, input().split())
    where.append((x-1, y-1))
    memo_h[x-1] += 1
    memo_w[y-1] += 1

from collections import Counter
h_cnt = Counter(memo_h)
w_cnt = Counter(memo_w)
h_max = max(memo_h)
w_max = max(memo_w)

ans = h_max + w_max
tmp = 0
for x, y in where:
    if memo_h[x] + memo_w[y] == ans:
        tmp += 1

if tmp == h_cnt[h_max] * w_cnt[w_max]:
    print(ans - 1)
else:
    print(ans)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
H, W, M = map(int, input().split())
X = [0] * H
Y = [0] * W
Z = []
for _ in range(M):
    h, w = map(int, input().split())
    h, w = h-1, w-1
    X[h] += 1
    Y[w] += 1
    Z.append((h, w))
mX = max(X)
mY = max(Y)
cX = X.count(mX)
cY = Y.count(mY)
c = 0
for h, w in Z:
    if X[h] == mX and Y[w] == mY:
        c += 1

print(mX + mY - (0 if c < cX * cY else 1))

Solution (Python):

H, W, M = map(int,input().split())
h_count = [0] * (H+1)
w_count = [0] * (W+1)
memo = set()

for _ in range(M):
    h, w = map(int,input().split())
    memo.add((h,w))
    h_count[h] += 1
    w_count[w] += 1

h_memo = []
temp = 0
h_max = max(h_count)
for idx, i in enumerate(h_count):
    if i == h_max:
        h_memo.append(idx)

w_memo = []
temp = 0
w_max = max(w_count)
for idx, i in enumerate(w_count):
    if i == w_max:
        w_memo.append(idx)

for i in h_memo:
    for j in w_memo:
        if (i,j) not in memo:
            print(h_max + w_max)
            quit()
print(h_max + w_max - 1)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

h,w,m = map(int,input().split())

cnth = [0]*h
cntw = [0]*w
target = set()
for i in range(m):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    cnth[x] += 1
    cntｗ[y] += 1
    target.add(x*10**20 + y)

maxh = max(cnth)
maxw = max(cntw)
ans = maxh + maxw

H, W = set(),set()
for i,c in enumerate(cnth):
    if c == maxh:
        H.add(i)
for i,c in enumerate(cntw):
    if c == maxw:
        W.add(i)
if len(H)*len(W) > m:
    print(ans)
else:
    for h in H:
        for w in W:
            if h*10**20 + w not in target:
                print(ans)
                exit()
    print(ans-1)

Solution (Python):
H, W, M = map(int, input().split())
hws = [tuple(map(int, input().split())) for _ in range(M)]

hws_set = set(hws)
h_count = [0] * (H+1)
w_count = [0] * (W+1)
for h, w in hws:
    h_count[h] += 1
    w_count[w] += 1

max_h_count = max(h_count)
max_h_count_index = [i for i, c in enumerate(h_count) if c == max_h_count]
max_w_count = max(w_count)
max_w_count_index = [i for i, c in enumerate(w_count) if c == max_w_count]

if len(max_h_count_index) * len(max_w_count_index) > M:
    ans = max_h_count + max_w_count
else:
    ans = max_h_count + max_w_count - 1
    for i in max_h_count_index:
        for j in max_w_count_index:
            if (i, j) not in hws_set:
                ans += 1
                break
        else:
            continue
        break

print(ans)

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    h,w,m = map(int,ipt().split())
    hs = [0]*h
    ws = [0]*w
    base = 3*10**5
    st = set()
    for i in range(m):
        hi,wi = map(int,ipt().split())
        hs[hi-1] += 1
        ws[wi-1] += 1
        st.add((hi-1,wi-1))

    hma = max(hs)
    mah = []
    for i,hi in enumerate(hs):
        if hi == hma:
            mah.append(i)
    wma = max(ws)
    maw = []
    for i,wi in enumerate(ws):
        if wi == wma:
            maw.append(i)

    for i in mah:
        for j in maw:
            if not (i,j) in st:
                print(hma+wma)
                exit()

    print(hma+wma-1)

    return None

if __name__ == '__main__':
    main()

Solution (Python):

"""

縦横の最大の組を抽出
組の数の積がMより大きかったら和を出せばいい
それ以外は全探索

"""

from sys import stdin
import sys
H,W,M = map(int,stdin.readline().split())

Hdic = {}
Wdic = {}
HW = {}

for i in range(M):

    h,w = map(int,stdin.readline().split())
    HW[(h,w)] = i

    if h not in Hdic:
        Hdic[h] = []
    Hdic[h].append(w)

    if w not in Wdic:
        Wdic[w] = []
    Wdic[w].append(h)

hmax = 0
hmlis = []

for i in Hdic:
    if len(Hdic[i]) > hmax:
        hmax = len(Hdic[i])
        hmlis = []

    if len(Hdic[i]) == hmax:
        hmlis.append(i)

wmax = 0
wmlis = []

for i in Wdic:
    if len(Wdic[i]) > wmax:
        wmax = len(Wdic[i])
        wmlis = []

    if len(Wdic[i]) == wmax:
        wmlis.append(i)

if len(hmlis) * len(wmlis) > M:
    print (hmax + wmax)
else:

    for h in hmlis:
        for w in wmlis:
            if (h,w) not in HW:
                print (hmax + wmax)
                sys.exit()

    print (hmax + wmax - 1)

Solution (Python):
import sys
from collections import Counter

stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    h, w, m = nm()
    H = []
    W = []
    for i in range(m):
        hh, ww = nm()
        H.append(hh)
        W.append(ww)
    h_m = Counter(H).most_common()[0]
    w_m = Counter(W).most_common()[0]
    ans_1 = h_m[1]
    ans_2 = w_m[1]
    WW = []
    HH = []

    for i in range(m):
        if H[i] == h_m[0]:
            continue
        WW.append(W[i])

    for i in range(m):
        if W[i] == w_m[0]:
            continue
        HH.append(H[i])
    if WW:
        ans_1 += Counter(WW).most_common()[0][1]
    if HH:
        ans_2 += Counter(HH).most_common()[0][1]

    print(max(ans_1, ans_2))


if __name__ == '__main__':
    main()

Solution (Python):
h,w,m = map(int,input().split())
br = [[i, 0] for i in range(h)]
bc = [[i, 0] for i in range(w)]
bsr = [set() for i in range(h)]
bsc = [set() for i in range(w)]
for _ in range(m):
    i, j = map(int,input().split())
    br[i-1][1] += 1
    bc[j-1][1] += 1
    bsr[i-1].add(j-1)
    bsc[j-1].add(i-1)
br.sort(key=lambda x: x[1], reverse=True)
bc.sort(key=lambda x: x[1], reverse=True)
rmax = br[0][1]
cmax = bc[0][1]
for i,bi in br:
    if bi < rmax:
        break
    for j, bj in bc:
        if bj < cmax:
            break
        if not j in bsr[i]:
            print(rmax + cmax)
            exit()

print(rmax + cmax - 1)

Solution (Python):
h, w, m = map(int, input().split())
a = [0] * h
b = [0] * w
g = [[] for _ in range(h)]
for _ in range(m):
    y, x = map(int, input().split())
    a[y - 1] += 1
    b[x - 1] += 1
    g[y - 1].append(x - 1)
ma = max(a)
mb = max(b)
c = b.count(mb)
for i in range(h):
    if a[i] == ma:
        res = 0
        for p in g[i]:
            if b[p] == mb:
                res += 1
        if res < c:
            print(ma + mb)
            exit(0)
print(ma + mb - 1)

Solution (Python):
import sys
h,w,n=map(int,input().split())
obj=set()
hor=[0]*(h+1)
ver=[0]*(w+1)
for i in range(n):
  x,y=map(int,input().split())
  obj.add((x-1)+(y-1)*h)
  hor[x]+=1
  ver[y]+=1
maxh=max(hor)
maxv=max(ver)
maxhct=0
maxvct=0
hs=[]
vs=[]
for i in range(1,h+1):
  if hor[i]==maxh:
    maxhct+=1
    hs.append(i)
for i in range(1,w+1):
  if ver[i]==maxv:
    maxvct+=1
    vs.append(i)
if maxhct*maxvct>n:
  print(maxh+maxv)
  sys.exit()
for i in hs:
  for j in vs:
    if not (((i-1)+(j-1)*h) in obj):
      print(maxh+maxv)
      sys.exit()
print(maxh+maxv-1)

Solution (Python):
h, w, m = map(int, input().split())
lo = 0x80000
t = [tuple(map(int, input().split())) for _ in range(m)]
seg = [0] * (lo * 2)
def modify(k, v):
    i = k + lo
    seg[i] += v
    i >>= 1
    while i:
        seg[i] = max(seg[i << 1], seg[(i << 1) | 1])
        i >>= 1
wow = [[] for _ in range(h + 3)]
for x, y in t:
    wow[x].append(y)
    modify(y, 1)
ans = 0
for x in range(1, h + 1):
    cc = 0
    for y in wow[x]:
        cc += 1
        modify(y, -1)
    ans = max(ans, cc + seg[1])
    for y in wow[x]:
        modify(y, 1)
print(ans)

Solution (Python):
h, w, m = map(int, input().split())
H = [0 for i in range(h + 1)]
W = [0 for i in range(w + 1)]
b = set()
for i in range(m):
    hi, wi = map(int, input().split())
    H[hi] += 1
    W[wi] += 1
    b.add((hi, wi))
h_list = []
w_list = []
temp = max(H)
for i in range(len(H)):
    if H[i] == temp:
        h_list.append(i)
temp2 = max(W)
for i in range(len(W)):
    if W[i] == temp2:
        w_list.append(i)
flag = False
for i in h_list:
    for j in w_list:
        if (i, j) not in b:
            flag = True
            break
    if flag == True:
        break
if flag == True:
    print(temp + temp2)
else:
    print(temp + temp2 - 1)