Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

The Maximum Number of Overlaps

  Given a set of $N$ axis-aligned rectangular seals, find the number of overlapped seals on the region which has the maximum number of overlapped seals.

Input

  The input is given in the following format.

$N$

$x1_1$ $y1_1$ $x2_1$ $y2_1$

$x1_2$ $y1_2$ $x2_2$ $y2_2$

:

$x1_N$ $y1_N$ $x2_N$ $y2_N$

($x1_i, y1_i$) and ($x2_i, y2_i$) are the coordinates of the top-left and the bottom-right corner of the $i$-th seal respectively.
  

Constraints

$ 1 \leq N \leq 100000 $

$ 0 \leq x1_i < x2_i \leq 1000 $

$ 0 \leq y1_i < y2_i \leq 1000 $

$ x1_i, y1_i, x2_i, y2_i$ are given in integers

Output

  Print the maximum number of overlapped seals in a line.

Sample Input 1

2
0 0 3 2
2 1 4 3

Sample Output 1

2

Sample Input 2

2
0 0 2 2
2 0 4 2

Sample Output 2

1

Sample Input 3

3
0 0 2 2
0 0 2 2
0 0 2 2

Sample Output 3

3



Sample input:
2
0 0 3 2
2 1 4 3


Sample output:
2

Submission status: Wrong Answer

Solution code:
N = int(input())
xys = []
m_x = 0
m_y = 0
for i in range(N):
	xy = list(map(int, input().split()))
	xys += [xy]
	x_1,y_1,x_2,y_2 = xy
	m_x = max(x_2, m_x)
	m_y = max(y_2, m_y)
im = [[0]*(m_x+1) for i in range(m_y+1)]
for xy in xys:
	x_1,y_1,x_2,y_2 = xy
	im[y_1][x_1] += 1
	im[y_1][x_2] -= 1
	im[y_2][x_1] -= 1
	im[y_2][x_2] += 1

num = 0
for y in range(m_y+1):
	for x in range(1, m_x+1):
		im[y][x] += im[y][x-1]
		
m = 0
for x in range(m_x+1):
	for y in range(1, m_y+1):
		im[y][x] += im[y-1][x]
		m = max(im[y][x], m)
print(m)

Submission status: Wrong Answer

Solution code:
N = int(input())
xys = []
"""
m_x = 0
m_y = 0

for i in range(N):
	xy = list(map(int, input().split()))
	xys += [xy]
	x_1,y_1,x_2,y_2 = xy
	m_x = max(x_2, m_x)
	m_y = max(y_2, m_y)
"""
xys = [list(map(int, input().split())) for i in range(N)]
#im = [[0 for i in range(m_x+1)] for j in range(m_y+1)]
im = [[0]*1010 for i in range(1010)]
for xy in xys:
	x_1,y_1,x_2,y_2 = xy
	im[y_1][x_1] += 1
	im[y_1][x_2] -= 1
	im[y_2][x_1] -= 1
	im[y_2][x_2] += 1

"""
for y in range(m_y+1):
	for x in range(1, m_x+1):
		im[y][x] += im[y][x-1]
		
m = 0
for x in range(m_x+1):
	for y in range(1, m_y+1):
		im[y][x] += im[y-1][x]
		m = max(im[y][x], m)
"""
for y in range(1010):
	for x in range(1, 1010):
		im[y][x] += im[y][x-1]
		
m = 0
for x in range(1010):
	for y in range(1, 1010):
		im[y][x] += im[y-1][x]
		m = max(im[y][x], m)
print(m)

Submission status: Accepted

Solution code:
from itertools import accumulate

n = int(input())
a = [[0] * 1001 for _ in range(1001)]
for x1, y1, x2, y2 in (map(int, input().split()) for _ in range(n)):
    a[x1][y1] += 1
    a[x1][y2] -= 1
    a[x2][y1] -= 1
    a[x2][y2] += 1
print(max(map(max, map(accumulate, zip(*map(accumulate, a))))))

Submission status: Accepted

Solution code:
from itertools import accumulate

N = int(input())
xys = []
m_x = 0
m_y = 0

for i in range(N):
	xy = list(map(int, input().split()))
	xys += [xy]
	x_1,y_1,x_2,y_2 = xy
	m_x = max(x_2, m_x)
	m_y = max(y_2, m_y)

im = [[0]*(m_x+1) for i in range(m_y+1)]

for xy in xys:
	x_1,y_1,x_2,y_2 = xy
	im[y_1][x_1] += 1
	im[y_1][x_2] -= 1
	im[y_2][x_1] -= 1
	im[y_2][x_2] += 1

print(max(map(max, map(accumulate, zip(*map(accumulate, im))))))

Submission status: Accepted

Solution code:
from itertools import accumulate
im = [[0]*1001 for i in range(1001)]
for x_1, y_1, x_2, y_2 in (map(int, input().split()) for _ in range(int(input()))):
	im[x_1][y_1] += 1
	im[x_1][y_2] -= 1
	im[x_2][y_1] -= 1
	im[x_2][y_2] += 1
print(max(map(max, map(accumulate, zip(*map(accumulate, im))))))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())

imos = [[0 for j in range(1001)] for i in range(1001)]

for _ in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    imos[x1][y1] += 1
    imos[x2][y2] += 1
    imos[x2][y1] -= 1
    imos[x1][y2] -= 1

for i in range(1001):
    for j in range(1000):
        imos[i][j + 1] += imos[i][j]

for j in range(1001):
    for i in range(1000):
        imos[i + 1][j] += imos[i][j]

res = 0

for i in range(1001):
    res = max(res, max(imos[i]))

print(res)

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
grid = [[0] * 1002 for _ in range(1002)]
for _ in range(N):
    x, y, xx, yy = map(int, input().split())
    grid[x][y] += 1
    grid[x][yy] -= 1
    grid[xx][y] -= 1
    grid[xx][yy] += 1

for i in range(1002):
    grid[i] = list(accumulate(grid[i]))
for i in range(1001):
    for j in range(1002):
        grid[i + 1][j] += grid[i][j]

ans = max(max(x) for x in grid)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
Xsize = 1001 # 0-1000
Ysize = 1001 # 0-1000
Data = [[0]*(Xsize) for _ in range (Ysize)]
Tmp  = [[0]*(Xsize) for _ in range (Ysize)]
Ans  = [[0]*(Xsize) for _ in range (Ysize)]

for _ in range(N):
    x1,y1,x2,y2 = map(int,input().split())
    Data[y1][x1] += 1
    Data[y1][x2] -= 1
    Data[y2][x1] -= 1
    Data[y2][x2] += 1

#x方向の累積和 
for y in range(Ysize):
    Tmp[y][0] = Data[y][0]
    for x in range(1,Xsize):
        Tmp[y][x] = Data[y][x] + Tmp[y][x-1]
#y方向の累積和 
for x in range(Xsize):
    Ans[0][x] = Tmp[0][x]
    for y in range(1,Ysize):
        Ans[y][x] = Tmp[y][x] + Ans[y-1][x]
#最大値
ans = 0
for y in range(Ysize):
    ans = max(ans,max(Ans[y]))
print(ans)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    N = int(input())
    MAX_COORDINATE = 1000
    table = [[0] * (MAX_COORDINATE + 1) for idx in range(MAX_COORDINATE + 1)]

    for _ in range(N):
        x1, y1, x2, y2 = map(lambda x: int(x), input().split())
        table[y1][x1] += 1
        table[y1][x2] -= 1
        table[y2][x1] -= 1
        table[y2][x2] += 1
    for i in range(MAX_COORDINATE):
        for j in range(MAX_COORDINATE):
            table[i][j + 1] += table[i][j]
    for j in range(MAX_COORDINATE):
        for i in range(MAX_COORDINATE):
            table[i + 1][j] += table[i][j]

    print(max(max(val) for val in table))

Submission status: Accepted

Solution code:
N = int(input())

xs = set();ys = set()
P = []
for i in range(N):
    x1,y1,x2,y2 = map(int, input().split())
    xs.add(x1);xs.add(x2)
    ys.add(y1);ys.add(y2)
    P.append((x1,x2,y1,y2))
    
X = sorted(xs);Y = sorted(ys)
MX = {x: i for i, x in enumerate(X)}
MY = {y: i for i, y in enumerate(Y)}

H = len(Y);W = len(X)
S = [[0]*(W+1) for i in range(H+1)]
for x1, x2, y1, y2 in P:
    p1 = MY[y1]; q1 = MX[x1]
    p2 = MY[y2]; q2 = MX[x2]
    
    S[p1][q1] += 1
    S[p1][q2] -= 1
    S[p2][q1] -= 1
    S[p2][q2] += 1


for i in range(H):
    for j in range(W):
        S[i][j+1] += S[i][j]
ans = 0
for j in range(W):
    for i in range(H):
        S[i+1][j]+= S[i][j]
        ans = max(ans,S[i][j])
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
n=int(input())
size=1005
sheet=[[0for i in range(size)] for i in range(size)]
for i in range(n):
    a,b,c,d=map(int,input().split())
    sheet[b][a]+=1
    sheet[b][c]-=1
    sheet[d][a]-=1
    sheet[d][c]+=1
for i in range(size):
    sheet[i]=list(accumulate(sheet[i]))
mx=max(sheet[0])
for i in range(1,size):
    for j in range(size):
        sheet[i][j]+=sheet[i-1][j]
    mx=max(mx,max(sheet[i]))
print(mx)

Submission status: Accepted

Solution code:
N = int(input())
Z = 1000
D = [[0]*(Z+1) for i in range(Z+1)]
for i in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    D[y1][x1] += 1
    D[y1][x2] -= 1
    D[y2][x1] -= 1
    D[y2][x2] += 1
for i in range(Z):
    for j in range(Z):
        D[i][j+1] += D[i][j]
for j in range(Z):
    for i in range(Z):
        D[i+1][j] += D[i][j]
print(max(max(d) for d in D))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# DSL_5_B: The Maximum Number of Overlaps

from itertools import accumulate
import sys


if __name__ == '__main__':
    n = int(input())

    ys = [0] * 1001
    rects = [None] * 2 * n
    i = 0
    for line in sys.stdin:
        x1, y1, x2, y2 = [int(j) for j in line.split()]
        rects[i] = (x2, -1, y1, y2)
        rects[i+n] = (x1, 1, y1, y2)
        i += 1

    rects.sort(key=lambda x: x[0])

    max_overlap = 0
    for x, t, y1, y2 in rects:
        if t > 0:
            ys[y1] += 1
            ys[y2] -= 1
        else:
            overlap = max(accumulate(ys))
            if overlap > max_overlap:
                max_overlap = overlap
            ys[y1] -= 1
            ys[y2] += 1

    print(max_overlap)

Submission status: Accepted

Solution code:
n = int(input())
lec = [[0 for i in range(1001)] for j in range(1001)]
max_x = 0
max_y = 0
for i in range(n):
    x,y,s,t = map(int, input().split(" "))
    lec[y][x] += 1
    lec[y][s] -= 1
    lec[t][x] -= 1
    lec[t][s] += 1
    max_x = max(max_x, s)
    max_y = max(max_y, t)

for i in range(max_y+1):
    for j in range(1, max_x+1):
        lec[i][j] += lec[i][j-1]

for i in range(1, max_y+1):
    for j in range(max_x+1):
        lec[i][j] += lec[i-1][j]

ans = 0
for i in range(max_y+1):
    for j in range(max_x+1):
        ans = max(ans, lec[i][j])

print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate

n = int(input())
a = [[0] * 10 for _ in range(10)]
for x1, y1, x2, y2 in (map(int, input().split()) for _ in range(n)):
    a[x1][y1] += 1
    a[x1][y2] -= 1
    a[x2][y1] -= 1
    a[x2][y2] += 1
print(max(map(max, map(accumulate, zip(*map(accumulate, a))))))