Problem:

 

宝探し

太郎君はある広場にお宝を探しにやってきました。この広場にはたくさんのお宝が埋められていますが、太郎君は最新の機械を持っているので、どこにお宝が埋まっているかをすべて知っています。広場はとても広いので太郎君は領域を決めてお宝を探すことにしましたが、お宝はたくさんあるためどのお宝がその領域の中にあるかすぐにわかりません。そこで太郎君はその領域の中にあるお宝の数を数えることにしました。

Input

n m
x1 y1
x2 y2
...
xn yn
x11 y11 x12 y12
x21 y21 x22 y22
...
xm1 ym1 xm2 ym2

nは広場に埋まっているお宝の数を表す

mは調べる領域の数を表す

2行目からn+1行目はそれぞれのお宝が埋まっている座標を表す

n+2行目からn+m+1行目はそれぞれの調べる領域を表す

x軸の正の方向が東、y軸の正の方向が北を表す

それぞれの領域は長方形であり、xi1とyi1は長方形の南西の頂点の座標、xi2とyi2は長方形の北東の頂点の座標を表す

Constraints

1 ≤ n ≤ 5000
1 ≤ m ≤ 5&times;105
|xi|, |yi| ≤ 109 (1 ≤ i ≤ n)
|xi1|, |yi1|, |xi2|, |yi2| ≤ 109 (1 ≤ i ≤ m)
xi1 ≤ xi2, yi1 ≤ yi2 (1 ≤ i ≤ m)

すべての入力は整数で与えられる

Output

C1
C2
...
Cm

それぞれの領域に含まれるお宝の数を各行に出力せよ

Sample Input 1

3 1
1 1
2 4
5 3
0 0 5 5

Output for the Sample Input 1

3

領域の境界線上にあるお宝も領域に含まれるものとみなす

Sample Input 2

4 2
-1 1
0 3
4 0
2 1
-3 1 5 1
4 0 4 0

Output for the Sample Input 2

2
1

領域は直線や点のようになる場合もある

Sample Input 3

2 3
0 0
0 0
-1 -1 1 1
0 0 2 2
1 1 4 4

Output for the Sample Input 3

2
2
0

同じ場所に複数のお宝が存在する場合もある

Sample Input 4

5 5
10 5
-3 -8
2 11
6 0
-1 3
-3 1 3 13
-1 -1 9 5
-3 -8 10 11
0 0 5 5
-10 -9 15 10

Output for the Sample Input 4

2
2
5
0
4



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


Sample output:
3

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class Ruiwa():
    def __init__(self, a):
        self.H = h = len(a)
        self.W = w = len(a[0])
        self.R = r = a
        for i in range(h):
            for j in range(1,w):
                r[i][j] += r[i][j-1]

        for i in range(1,h):
            for j in range(w):
                r[i][j] += r[i-1][j]

    def search(self, x1, y1, x2, y2):
        print(x1, y1, x2, y2)
        if x1 > x2 or y1 > y2:
            return 0

        r = self.R
        rr = r[y2][x2]
        if x1 > 0 and y1 > 0:
            return rr - r[y1-1][x2] - r[y2][x1-1] + r[y1-1][x1-1]
        if x1 > 0:
            rr -= r[y2][x1-1]
        if y1 > 0:
            rr -= r[y1-1][x2]

        return rr

def main():
    n,m = LI()
    na = [LI() for _ in range(n)]
    ma = [LI() for _ in range(m)]
    xd = set()
    yd = set()
    for x,y in na:
        xd.add(x)
        yd.add(y)
    for x1,y1,x2,y2 in ma:
        xd.add(x1)
        yd.add(y1)
        xd.add(x2)
        yd.add(y2)
    xl = sorted(list(xd))
    yl = sorted(list(yd))
    xx = {}
    yy = {}
    for i in range(len(xl)):
        xx[xl[i]] = i
    for i in range(len(yl)):
        yy[yl[i]] = i
    a = [[0]*(len(yl)+1) for _ in range(len(xl)+1)]
    for x,y in na:
        a[xx[x]][yy[y]] += 1
    rui = Ruiwa(a)
    r = []
    for x1,y1,x2,y2 in ma:
        r.append(rui.search(yy[y1],xx[x1],yy[y2],xx[x2]))


    return '\n'.join(map(str,r))



print(main())

Submission status: Wrong Answer

Solution code:
import bisect
n,m = map(int,raw_input().split())
xy = sorted([map(int,raw_input().split()) for i in range(n)])
yx = sorted(xy, key = lambda x:x[1])
X = [i[0] for i in xy]
Y = [i[1] for i in yx]
xy = [str(i[0]) + "," + str(i[1]) for i in xy]
yx = [str(i[0]) + "," + str(i[1]) for i in yx]
for i in range(m):
	x1,y1,x2,y2 = map(int,raw_input().split())
	x1 = bisect.bisect_left(X,x1)
	y1 = bisect.bisect_left(Y,y1)
	x2 = bisect.bisect_right(X,x2)
	y2 = bisect.bisect_right(Y,y2)
	print len(set(xy[x1:x2])&set(yx[y1:y2]))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,raw_input().split())
xy = [map(int,raw_input().split()) for i in range(n)]
for i in range(m):
	x1,y1,x2,y2 = map(int,raw_input().split())
	print sum(1 for x,y in xy if x1<=x<=x2 and y1<=y<=y2)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,m = map(int,raw_input().split())
xy = sorted([map(int,raw_input().split()) + [i] for i in range(n)])
yx = sorted(xy, key = lambda x:x[1])
X = [i[0] for i in xy]
Y = [i[1] for i in yx]
xy = [str(i[0]) + "," + str(i[1]) + "_" + str(i[2]) for i in xy]
yx = [str(i[0]) + "," + str(i[1]) + "_" + str(i[2]) for i in yx]
for i in range(m):
	x1,y1,x2,y2 = map(int,raw_input().split())
	x1 = bisect.bisect_left(X,x1)
	y1 = bisect.bisect_left(Y,y1)
	x2 = bisect.bisect_right(X,x2)
	y2 = bisect.bisect_right(Y,y2)
	print len(set(xy[x1:x2])&set(yx[y1:y2]))

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,m = map(int,raw_input().split())
xy = sorted([map(int,raw_input().split()) + [i] for i in range(n)])
yx = sorted(xy, key = lambda x:x[1])
X = [i[0] for i in xy]
Y = [i[1] for i in yx]
xy = [str(i[0]) + "," + str(i[1]) + "_" + str(i[2]) for i in xy]
yx = [str(i[0]) + "," + str(i[1]) + "_" + str(i[2]) for i in yx]
ans = {}
for xi in range(n):
	for xj in range(xi,n+1):
		for yi in range(n):
			for yj in range(yi,n+1):
				ans[str(xi) + "_" +  str(xj) + "_" + str(yi) + "_" + str(yj)] = len(set(xy[xi:xj])&set(yx[yi:yj]))
for i in range(m):
	x1,y1,x2,y2 = map(int,raw_input().split())
	x1 = bisect.bisect_left(X,x1)
	y1 = bisect.bisect_left(Y,y1)
	x2 = bisect.bisect_right(X,x2)
	y2 = bisect.bisect_right(Y,y2)
	try: print ans[str(x1) + "_" +  str(x2) + "_" + str(y1) + "_" + str(y2)]
	except: print 0

Submission status: Memory Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class Ruiwa():
    def __init__(self, a):
        self.H = h = len(a)
        self.W = w = len(a[0])
        self.R = r = a
        for i in range(h):
            for j in range(1,w):
                r[i][j] += r[i][j-1]

        for i in range(1,h):
            for j in range(w):
                r[i][j] += r[i-1][j]

    def search(self, x1, y1, x2, y2):
        if x1 > x2 or y1 > y2:
            return 0

        r = self.R
        rr = r[y2][x2]
        if x1 > 0 and y1 > 0:
            return rr - r[y1-1][x2] - r[y2][x1-1] + r[y1-1][x1-1]
        if x1 > 0:
            rr -= r[y2][x1-1]
        if y1 > 0:
            rr -= r[y1-1][x2]

        return rr

def main():
    n,m = LI()
    na = [LI() for _ in range(n)]
    ma = [LI() for _ in range(m)]
    xd = set()
    yd = set()
    for x,y in na:
        xd.add(x)
        yd.add(y)
    for x1,y1,x2,y2 in ma:
        xd.add(x1)
        yd.add(y1)
        xd.add(x2)
        yd.add(y2)
    xl = sorted(list(xd))
    yl = sorted(list(yd))
    xx = {}
    yy = {}
    for i in range(len(xl)):
        xx[xl[i]] = i
    for i in range(len(yl)):
        yy[yl[i]] = i
    a = [[0]*(len(yl)+1) for _ in range(len(xl)+1)]
    for x,y in na:
        a[xx[x]][yy[y]] += 1
    rui = Ruiwa(a)
    r = []
    for x1,y1,x2,y2 in ma:
        r.append(rui.search(yy[y1],xx[x1],yy[y2],xx[x2]))


    return '\n'.join(map(str,r))



print(main())

Submission status: Memory Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class Ruiwa():
    def __init__(self, a):
        self.H = h = len(a)
        self.W = w = len(a[0])
        self.R = r = a
        for i in range(h):
            for j in range(1,w):
                r[i][j] += r[i][j-1]

        for i in range(1,h):
            for j in range(w):
                r[i][j] += r[i-1][j]

    def search(self, x1, y1, x2, y2):
        if x1 > x2 or y1 > y2:
            return 0

        r = self.R
        rr = r[y2][x2]
        if x1 > 0 and y1 > 0:
            return rr - r[y1-1][x2] - r[y2][x1-1] + r[y1-1][x1-1]
        if x1 > 0:
            rr -= r[y2][x1-1]
        if y1 > 0:
            rr -= r[y1-1][x2]

        return rr

def main():
    n,m = LI()
    na = [LI() for _ in range(n)]
    xd = set()
    yd = set()
    for x,y in na:
        xd.add(x)
        yd.add(y)

    xl = sorted(list(xd))
    yl = sorted(list(yd))
    xx = {}
    yy = {}
    for i in range(len(xl)):
        xx[xl[i]] = i
    for i in range(len(yl)):
        yy[yl[i]] = i
    a = [[0]*(len(yl)+1) for _ in range(len(xl)+1)]
    for x,y in na:
        a[xx[x]][yy[y]] += 1
    rui = Ruiwa(a)
    r = []
    for x1,y1,x2,y2 in [LI() for _ in range(m)]:
        xx1 = bisect.bisect_left(xl, x1)
        yy1 = bisect.bisect_left(yl, y1)
        xx2 = bisect.bisect(xl, x2) - 1
        yy2 = bisect.bisect(yl, y2) - 1
        r.append(rui.search(yy1,xx1,yy2,xx2))


    return '\n'.join(map(str,r))



print(main())

Submission status: Memory Limit Exceeded

Solution code:
import bisect
n,m = map(int,raw_input().split())
xy = sorted([map(int,raw_input().split()) + [i] for i in range(n)])
yx = sorted(xy, key = lambda x:x[1])
X = [i[0] for i in xy]
Y = [i[1] for i in yx]
xy = [str(i[0]) + "," + str(i[1]) + "_" + str(i[2]) for i in xy]
yx = [str(i[0]) + "," + str(i[1]) + "_" + str(i[2]) for i in yx]
ans = [[[[0]*(n+1) for i in range(n+1)] for j in range(n+1)] for k in range(n+1)]
for xi in range(n):
	for xj in range(xi,n+1):
		for yi in range(n):
			for yj in range(yi,n+1):
				ans[xi][xj][yi][yj] = len(set(xy[xi:xj])&set(yx[yi:yj]))
for i in range(m):
	x1,y1,x2,y2 = map(int,raw_input().split())
	x1 = bisect.bisect_left(X,x1)
	y1 = bisect.bisect_left(Y,y1)
	x2 = bisect.bisect_right(X,x2)
	y2 = bisect.bisect_right(Y,y2)
	print ans[x1][x2][y1][y2]

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class Ruiwa():
    def __init__(self, a):
        self.H = h = len(a)
        self.W = w = len(a[0])
        self.R = r = a
        for i in range(h):
            for j in range(1,w):
                r[i][j] += r[i][j-1]

        for i in range(1,h):
            for j in range(w):
                r[i][j] += r[i-1][j]

    def search(self, x1, y1, x2, y2):
        if x1 > x2 or y1 > y2:
            return 0

        r = self.R
        rr = r[y2][x2]
        if x1 > 0 and y1 > 0:
            return rr - r[y1-1][x2] - r[y2][x1-1] + r[y1-1][x1-1]
        if x1 > 0:
            rr -= r[y2][x1-1]
        if y1 > 0:
            rr -= r[y1-1][x2]

        return rr

def main():
    n,m = LI()
    na = [LI() for _ in range(n)]
    xd = set()
    yd = set()
    for x,y in na:
        xd.add(x)
        yd.add(y)

    xl = sorted(list(xd))
    yl = sorted(list(yd))
    xx = {}
    yy = {}
    for i in range(len(xl)):
        xx[xl[i]] = i
    for i in range(len(yl)):
        yy[yl[i]] = i
    a = [[0]*(len(yl)+1) for _ in range(len(xl)+1)]
    for x,y in na:
        a[xx[x]][yy[y]] += 1
    rui = Ruiwa(a)
    r = []
    for _ in range(m):
        x1,y1,x2,y2 = LI()
        xx1 = bisect.bisect_left(xl, x1)
        yy1 = bisect.bisect_left(yl, y1)
        xx2 = bisect.bisect(xl, x2) - 1
        yy2 = bisect.bisect(yl, y2) - 1
        r.append(rui.search(yy1,xx1,yy2,xx2))


    return '\n'.join(map(str,r))



print(main())

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
def main():
  n, m = map(int, input().split())
  plst = []
  xlst = set()
  ylst = set()
  for _ in range(n):
    x, y = map(int, input().split())
    plst.append((x, y))
    xlst.add(x)
    ylst.add(y)
  
  xlst = sorted(list(xlst))
  ylst = sorted(list(ylst))
  xdic = {}
  ydic = {}
  for i, x in enumerate(xlst):
    xdic[x] = i
  for i, y in enumerate(ylst):
    ydic[y] = i
  
  xlen = len(xlst)
  ylen = len(ylst)
  mp = [[0] * (xlen + 1) for _ in range(ylen + 1)]
  for x, y in plst:
    mp[ydic[y] + 1][xdic[x] + 1] += 1
  
  for y in range(1, ylen + 1):
    acc = 0
    for x in range(1, xlen + 1):
      acc += mp[y][x]
      mp[y][x] = acc + mp[y - 1][x]
  
  for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    x1i = bl(xlst, x1)
    y1i = bl(ylst, y1)
    x2i = bl(xlst, x2)
    y2i = bl(ylst, y2)
    if x2i < xlen and xlst[x2i] == x2:
      x2i += 1
    if y2i < ylen and ylst[y2i] == y2:
      y2i += 1
    print(mp[y2i][x2i] - mp[y2i][x1i] - mp[y1i][x2i] + mp[y1i][x1i])

main()

Submission status: Accepted

Solution code:
import bisect
inf = 1e10
n,m = map(int,raw_input().split())
xy = [map(int,raw_input().split()) for i in range(n)]
X = sorted([i[0] for i in xy] + [-inf-1] + [inf+1])
Y = sorted([i[1] for i in xy] + [-inf-1] + [inf+1])

s = [[0]*(n+10) for i in range(n+10)]
for i in range(n):
	a = bisect.bisect_left(X,xy[i][0])
	b = bisect.bisect_left(Y,xy[i][1])
	s[a][b] += 1

for i in range(n+2):
	for j in range(n+2):
		s[i+1][j+1] += s[i+1][j] + s[i][j+1] - s[i][j]

for i in range(m):
	x1,y1,x2,y2 = map(int,raw_input().split())
	x1 = bisect.bisect_left(X,x1) - 1
	y1 = bisect.bisect_left(Y,y1) - 1
	x2 = bisect.bisect_left(X,x2+1) - 1
	y2 = bisect.bisect_left(Y,y2+1) - 1
	print s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]

Submission status: Accepted

Solution code:
"""
AOJ 2426  Treasure Hunt


座標圧縮を二次元でやるっぽい
上の問題たちとちがうのは、ここからここまでが領域１です、みたいな形になっている点か。
また、例４をみると、ある領域の内側に小さな領域があるパターンもあり、小さいほうに入っている宝は両方に所属していることになるっぽい。

さっぱりなので写経
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2963309#1

二次元累積和がはじめてなので、そっちの練習がまず先に必要っぽい
"""

from bisect import bisect_left

def main():

    N,M = map(int, input().split())
    treasures = []

    # 宝のx,yの位置（ある宝のx,yの組ではなく、x,y座標的にどこに位置するか）
    Xs = set()
    Ys = set()

    for _ in range(N):
        x,y = map(int, input().split())
        treasures.append((x,y))
        Xs.add(x)
        Ys.add(y)


    # x,yそれぞれで座圧
    Xs = list(Xs)
    Xs.sort()
    Ys = list(Ys)
    Ys.sort()
    

    # 座標xはO番目、みたいな情報を作る
    Xd = {}
    Yd = {}
    for i,x in enumerate(Xs):
        Xd[x] = i
    for i,y in enumerate(Ys):
        Yd[y] = i


    lx = len(Xs)
    ly = len(Ys)
    # ここに宝があるよ、を座圧した情報にする
    compressd_treasures = [[0 for _ in range(lx + 1)] for _ in range(ly + 1)]
    for x,y in treasures:
        # yyy番目のy座標とxxx番目のxxx座標に宝があるよ
        compressd_treasures[Yd[y] + 1][Xd[x] + 1] += 1

    # 左下から右上に向かって、「下や左から（南から？）進んできて何個宝があるか」の累積和をとる
    # ここの操作後、comp~[y][x]で、（一番左下の座標（原点ではない））~(x,y)の長方形の中にある宝の数が得られるから、
    # うまいことやると(x1,y1)~(x2,y2)の範囲の宝の数が得られる
    for y in range(1, ly + 1):
        acc = 0
        for x in range(1, lx + 1):
            # accに足しておいて、xが進むごとに左から右へも累積和をとれる
            acc += compressd_treasures[y][x]
            # 下の所から積み上げて累積和
            compressd_treasures[y][x] = acc + compressd_treasures[y-1][x]

    for _ in range(M):
        x1, y1, x2, y2 = map(int, input().split())
        # それぞれの座標について、何番目の宝まで含みうるか考える
        idx_x1 = bisect_left(Xs, x1)
        idx_x2 = bisect_left(Xs, x2)
        idx_y1 = bisect_left(Ys, y1)
        idx_y2 = bisect_left(Ys, y2)

        # 宝が領域の境界線上にあるとき、加算する(bisectした値と同じものがXs,Ysにあるとき)
        if idx_x2 < lx and Xs[idx_x2] == x2:
            idx_x2 += 1
        if idx_y2 < ly and Ys[idx_y2] == y2:
            idx_y2 += 1
        
        # 累積和で出す。l~r = 0~r - 0~l-1　を二次元にしたバージョン
        ans = compressd_treasures[idx_y2][idx_x2] - compressd_treasures[idx_y2][idx_x1] - compressd_treasures[idx_y1][idx_x2] + compressd_treasures[idx_y1][idx_x1]
        print(ans)


if __name__ =="__main__":
    main()