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



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


Sample output:
3

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 19 + 7
EPS = 10 ** -10

class BIT:
    """ BIT汎用版 """

    def __init__(self, n, func, init):
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.func = func
        self.init = init
        self.tree = [init] * nv
    
    def query(self, i):
        """ [0, i]の値を取得 """
        s = self.init
        i += 1
        while i > 0:
            s = self.func(s, self.tree[i-1])
            i -= i & -i
        return s
    
    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] = self.func(self.tree[i-1], x)
            i += i & -i


class SegTree:
    """
    セグメント木
    1.update: i番目の値をxに更新する
    2.query: 区間[l, r)の値を得る
    """

    def __init__(self, n, func, intv, A=[]):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max, add, gcdなど)
        :param intv: 要素の初期値(単位元)
        :param A: 初期化に使うリスト(オプション)
        """
        self.n = n
        self.func = func
        self.intv = intv
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.intv] * (n2 << 1)
        if A:
            for i in range(n):
                self.tree[n2+i] = A[i]
            for i in range(n2-1, -1, -1):
                self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 0:
            i >>= 1
            self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def add(self, i, x):
        self.update(i, self.get(i) + x)

    def query(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = self.intv
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.tree[r])
            if l & 1:
                s = self.func(s, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1
        return s

    def get(self, i):
        """ 一点取得 """
        return self.tree[i+self.n2]

    def all(self):
        """ 全区間[0, n)の取得 """
        return self.tree[1]

    def print(self):
        for i in range(self.n):
            print(self.get(i), end=' ')
        print()

H, W, M = MAP()
seg = SegTree(W+1, max, -INF, [0]*(W+1))
adjli = [[] for i in range(H+1)]
C = [0] * (W+1)
for i in range(M):
    h, w = MAP()
    seg.add(w, 1)
    adjli[h].append(w)

ans = 0
for h in range(1, H+1):
    rowcnt = len(adjli[h])
    for w in adjli[h]:
        seg.add(w, -1)
    ans = max(ans, rowcnt+seg.all())
    for w in adjli[h]:
        seg.add(w, 1)
print(ans)

Submission status: Accepted

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

target = set()
rows = [0] * h
cols = [0] * w
for i in range(m):
    y, x = map(lambda x: int(x) - 1, input().split())
    rows[y] += 1
    cols[x] += 1
    target.add((y, x))

rows_sorted = [(a, i) for i, a in enumerate(rows)]
rows_sorted.sort(reverse=True)
cols_sorted = [(a, i) for i, a in enumerate(cols)]
cols_sorted.sort(reverse=True)

max_r = rows_sorted[0][0]
max_c = cols_sorted[0][0]

i = 0
max_val = max(max_r, max_c)
while i < h and rows_sorted[i][0] == max_r:
    j = 0
    while j < w and cols_sorted[j][0] == max_c:
        val = rows_sorted[i][0] + cols_sorted[j][0]
        if (rows_sorted[i][1], cols_sorted[j][1]) in target:
            val -= 1
        else:
            max_val = val
            break
        max_val = max(max_val, val)
        j += 1
    i += 1
print(max_val)

Submission status: Accepted

Solution code:

def get_count(li,c):
    if(li==[]):
        return ((0,0))
    m=(li[0][c],1)
    h={}
    h[li[0][c]]=1
    for i in li[1:]:
        if(i[c] in h):
            h[i[c]]+=1
        else:
            h[i[c]]=1
        if(m[1]<h[i[c]]):
            m=(i[c],h[i[c]])
    return m


h,w,n=list(map(int,input().split()))

if(h==1 or w==1 or n<=1):
    li = []
    for i in range(n):
        li.append(tuple(map(int, input().split())))
    print(n)
else:
    li=[]
    for i in range(n):
        li.append(tuple(map(int,input().split())))
    li=list(set(li))
    r=get_count(li,0)
    c=get_count(li,1)
    # print(r,c)
    s=0
    if(r[1]>c[1]):
        temp=[]
        for i in li:
            if(i[0]!=r[0]):
                temp.append(i)
        s+=r[1]+get_count(temp,1)[1]
    else:
        temp=[]
        for i in li:
            if(i[1]!=c[0]):
                temp.append(i)
        s+=c[1]+get_count(temp,0)[1]

    print(s)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
input = lambda : sys.stdin.readline().rstrip()

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

xs = []
ys = []
for i in range(m):
    x, y = map(int, input().split(" "))
    xs.append(x)
    ys.append(y)

xcounter = Counter(xs)
ycounter = Counter(ys)

x_most, x_most_num = xcounter.most_common(1)[0]
#y_most, y_most_num = ycounter.most_common(1)[0]

#if x_most_num < y_most_num:
#    x_most_num = y_most_num
#    tmp = ys
#    ys = xs
#    xs = tmp
#
out1 = x_most_num

if x_most_num < m:
    y2s = [] 
    for i in range(m):
        if xs[i] == x_most:
            continue
        else:  
            y2s.append(ys[i])
        
    y2counter = Counter(y2s)
    y2_most, y2_most_num = y2counter.most_common(1)[0]
    out1 += y2_most_num


y_most, y_most_num = ycounter.most_common(1)[0]

out2 = y_most_num

if y_most_num < m:
    x2s = [] 
    for i in range(m):
        if ys[i] == y_most:
            continue
        else:  
            x2s.append(xs[i])
        
    x2counter = Counter(x2s)
    x2_most, x2_most_num = x2counter.most_common(1)[0]
    out2 += x2_most_num

out = max(out1, out2)

print(out)

Submission status: Accepted

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

A = [0 for _ in range(H)]
B = [0 for _ in range(W)]
C = set()

for _ in range(M):
  h, w = map(int, input().split())
  A[h-1] += 1
  B[w-1] += 1
  C.add((h-1, w-1))
  
d = max(A)
e = max(B)
ans = d+e

F = set()
G = set()
for h in range(H):
  if A[h] == d:
    F.add(h)
for w in range(W):
  if B[w] == e:
    G.add(w)
  
spot = len(F)*len(G)
spt_bm = 0

for c in C:
  if c[0] in F and c[1] in G:
    #print(c)
    spt_bm += 1
    
if spt_bm == spot:
  ans -= 1
  
#print(A, d, F)
#print(B, e, G)
#print(spt_bm, spot)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("## ",*x,file=sys.stderr) if LOCAL else 0
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

class segtree():#seg=segtree(A),単位元とsegfuncを指定すること
    def __init__(self,A,ide=0):#単位元とsegfuncを指定すること
        n=len(A)
        num=2**(n-1).bit_length()#n以上の最小の2のべき乗
        seg=[ide]*(2*num-1)
        segfunc=self.segfunc
        self.ide,self.n,self.num,self.seg = ide, n, num, seg
        for i in range(n): seg[i+num-1]=A[i]#setvalue
        for i in range(num-2,-1,-1):seg[i]=segfunc(seg[2*i+1],seg[2*i+2])#build
    
    def segfunc(self,x,y):return max(x,y) #seg木の基本関数
    
    def update(self,k,x):#Aのk番目の要素をxに置き換える,計算量log(N)
        k += self.num-1
        seg,segfunc=self.seg,self.segfunc
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
    def query(self,p,q):#区間[p,q)の累積segfuncを求める,計算量log(N)
        if q<=p: return self.ide
        num,segfunc,seg=self.num,self.segfunc,self.seg
        p += num-1; q += num-2
        res=self.ide
        while q-p>1:
            if p&1 == 0: res = segfunc(res,seg[p])
            if q&1 == 1:
                res = segfunc(res,seg[q])
                q -= 1
            p,q = p//2, (q-1)//2
        if p == q: res = segfunc(res,seg[p])
        else: res = segfunc(segfunc(res,seg[p]),seg[q])
        return res 

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    H,W,M = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = tuple(tuple(map(int, input().split())) for i in range(M)) #改行行列

    lis=[set() for _ in range(H)]
    l=[0]*W
    seg=segtree(l)
    
    for h,w, in S:
        h-=1
        w-=1
        lis[h].add(w)
        if h!=0:
            l[w]+=1
            seg.update(w,l[w])
    ans=0
    for h in range(H):
        ans=max(ans,seg.query(0,W)+len(lis[h]))

        if h==H-1:
            break
        for w in lis[h]:
            l[w]+=1
            seg.update(w,l[w])
        for w in lis[h+1]:
            l[w]-=1
            seg.update(w,l[w])
    print(ans)
    #printe(lis)
            



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    H, W, M = map(int, input().split())
    Bomb = dict()
    Hc = [0] * H
    Wc = [0] * W
    for _ in range(M):
        h, w = map(int, input().split())
        Bomb[(h-1, w-1)] = 0
        Hc[h-1] += 1
        Wc[w-1] += 1
    maxH, maxW = max(Hc), max(Wc)
    maxHs = []
    for i, h in enumerate(Hc):
        if h == maxH: maxHs.append(i)
    maxWs = []
    for i, w in enumerate(Wc):
        if w == maxW: maxWs.append(i)
    
    ans = maxH + maxW - 1
    for h in maxHs:
        for w in maxWs:
            if (h, w) not in Bomb:
                ans += 1
                break
        if ans == maxH + maxW:
            break
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)+'#'+str(w1)
    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)+'#'+str(j)
        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

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
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]
#print(x,y,xx,yy)
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# Fast IO (be careful about bytestring)

# import os,io
# input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline


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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right, insort_right


class SquareSkipList:
    # SkipList の層数を 2 にした感じの何か
    # std::multiset の代用になる
    # 検証1 (add, pop) データ構造: https://atcoder.jp/contests/arc033/submissions/14718760
    # 検証2 (init, add, remove, search_higher_equal) Exclusive OR Queries: https://atcoder.jp/contests/cpsco2019-s1/submissions/14705333
    # 検証3 (add, search_higher, search_lower) Second Sum: https://atcoder.jp/contests/abc140/submissions/7488469
    # 検証4 (add, __getitem__) [CF] Optimal Subsequences (Hard Version): https://codeforces.com/contest/1261/submission/65643461
    # 検証5 (init, add, pop) Dinner Planning: https://atcoder.jp/contests/code-festival-2018-final-open/submissions/13916065
    # 検証6 (要素がタプル, init, add, remove, max, pop_max) Lake: https://atcoder.jp/contests/snuke21/submissions/14718529
    # 検証7 (init, add, remove, pop, max, pop_max) ドーナツの箱詰め: https://atcoder.jp/contests/donuts-2015/submissions/14829916
    # 検証8 (init, add, remove, min, max) Smart Infants: https://atcoder.jp/contests/abc170/submissions/15264112
    def __init__(self, values=None, sorted_=False, square=1000, seed=42, inf=float("inf")):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # square: 最大データ数の平方根
        # seed: 乱数のシード
        # inf: 番兵（要素がタプルのときは (float("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):  # 要素の追加  # O(sqrt(n))
        # xorshift
        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:])  # layer0 は dict で管理した方が良いかもしれない  # dict 微妙だった
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(self.layer1, x)
            insort_right(self.layer0[idx1], x)

    def remove(self, x):  # 要素の削除  # O(sqrt(n))
        # x が存在しない場合、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):  # x 以上の最小の値を返す  O(log(n))
        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):  # x を超える最小の値を返す  O(log(n))
        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):  # x 未満の最大の値を返す  O(log(n))
        idx1 = bisect_left(self.layer1, x)
        layer0_idx1 = self.layer0[idx1]
        idx0 = bisect_left(layer0_idx1, x)
        if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
            return self.layer1[idx1 - 1]
        return layer0_idx1[idx0 - 1]

    def pop(self, idx):
        # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
        # O(sqrt(n))
        # for を回すので重め、使うなら square パラメータを大きめにするべき
        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):
        # 最大値を削除してその要素を返す（0-indexed） O(1)
        # 空ならエラー
        if self.layer0[-1]:
            return self.layer0[-1].pop()
        else:
            del self.layer0[-1]
            return self.layer1.pop(-2)

    def __getitem__(self, item):
        # 小さい方から idx 番目の要素を返す  O(sqrt(N))
        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):  # 最小値を返す  空なら inf を返す  O(1)
        return self.layer0[0][0] if self.layer0[0] else self.layer1[0]

    def max(self):  # 最大値を返す  空ならエラー  O(1)
        return self.layer0[-1][-1] if self.layer0[-1] else self.layer1[-2]

    def merge(self, r):  # 結合  O(sqrt(n))
        self.layer0[-1] += r.layer0[0]
        self.layer0 += r.layer0[1:]
        del self.layer1[-1]
        self.layer1 += r.layer1

    def split(self, k):  # k 以上を切り離す  O(sqrt(n))
        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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))