BELOW_IS_LESS_INTERESTING
็ ็ฉถใใผใ
ๆฝ่ฑกๅใๅฟ ใใใๅใงใชใใจใใ่ใๆนใฏใๅ ทไฝ็ใชใใฎใๆใๅบใใใใฎใใใฏใใๅคๆงใชใใฎใ้ฃๆณใงใใ็ถๆ ใไฟใคใใจใฎ้่ฆๆงใ็คบใใฆใใพใใใใใฏใ่จ่ใฎ้ฃๆณ็ๆๅณใงใคใชใใใใจใใใขใณใฑใผใ่ชฟๆปใใใฎKJๆณใ้ฃใใ็็ฑใจใ้ข้ฃใใฆใใพใใใพใใใ้ใกใฆๆนใใใใใใใ้ใกใจใใใใจใใใ่ซ่ชใใใใฎๅผ็จใฏใ้ใกใ็ฏใใใจ่ชไฝใฏไบบ้ใฎๆง่ณชใงใใใ้ฟใใใใชใใใใใฎ้ใกใ่ช่ญใใใใใๆนใใชใใใจใ็ใฎ้ใกใงใใใจใใๆใใ็คบใใฆใใพใใใใใฏใ็ ็ฉถใใใถใคใณใฎใใญใปในใซใใใฆใ้่ฆใชๆ่จใงใใใจๆใใพใใ
ๅ็ท ๅฝนใ็คพๅ ๅ ฌๅใใใจใใ่ใๆนใฏใๅ็ท ๅฝนใจใใๅฝน่ทใ้ๅธธใ็ตๅถในใญใซใฎๅฐ้ๅฎถใ็คพๅ ็งฉๅบใซใใใ้ท่ใจใใฆใฎๅฝนๅฒใๆใใใใใตใคใใฆใบใฎๅ ฌๅๅ็ท ๅฝนใฏใใใงใฏใชใใจใใๆๆใใใใพใใๅ็ท ๅฝนใๅขใใใใจใซใใๆๆๆฑบๅฎใฎ้ ใใใใคใขในใๆธๅฟตใใใพใใใใตใคใใฆใบใฎใใใฃใฆใฟใฆๅ้กใๆใใใซใชใใฐใใใใใใใใจใใๆๅใใใไฝใๅ้กใใใใฐใใใใฐใใใจ่ใใใใฆใใพใใใใใฏใใใใ่ชไฝใๆ่ปฝใซใใใฏใขใใใใใจใใๆๆกใจ้ข้ฃใใใใใใงใใๅคงๅน ใชๆงๆๅคๆดใใใใใใใใใๆใใจใใใทใใฅใจใผใทใงใณใใซใใผใใใใใซใใใใ่ชไฝใๆ่ปฝใซ่ค่ฃฝใใฆใใใฏใขใใใงใใใจ่ฏใใจใใๆๆกใใใใพใใใใใฏใ็ดใงไฝๆฅญใใใฆใใๆใซใฏๆฌ่ณช็ใซไธๅฏ่ฝใ ใฃใใใจใ ใใใใธใฟใซๅใซใใๅฏ่ฝใซใชใฃใใใใใฏใขใใใฏๅคๆดใใๆๆใ็ทฉๅใใๅนๆใใใใจ่ใใใใพใใ
ๅ่ๅผฑๆงใซใคใใฆใฎ่ใๆนใฏใใใๅ้ใงๅฎๅ จ็ญใๅใ(=่ฒ ใฎใใฉใใฏในใฏใณใซๅฏพใใฆ้ ๅฅ)ใๅฅใฎๅ้ใง้ๅฎ็ใชในใฏใใใใใๅใใใจใงใๅคงๅใกใใๅคงใใชๅฉ็ใๅพใ(=ๆญฃใฎใใฉใใฏในใฏใณใๆฎใ)ใจใใใใฎใงใใใใใซใใฃใฆๅ่ใใๅฎ็พใใใจใใใฆใใพใใใพใใใฟใฌใใฏใๅ่ใใจใฏใชใใทใงใณใๆใคใใจใ ใจ่ฟฐในใฆใใพใใใใชใใทใงใณใจใฏ็งใใกใๅ่ใใใฆใใใใใฎใ ใใชใใทใงใณใใใใฐใไธ็ขบๅฎๆงใฎ่ฒ ใฎๅด้ขใใๆทฑๅปใชๅฎณใใใใใใใจใชใใไธ็ขบๅฎๆงใฎๆญฃใฎๅด้ขใใๅฉ็ใๅพใใใจใใงใใใฎใ ใใจใใ่ใๆนใฏใใชในใฏ็ฎก็ใซใใใฆ้่ฆใช่ฆ็นใจใชใใพใใ
่ฑ็ท=้ฃๆณ=ๆฐ็ตๅ็บ่ฆใจใใ่ใๆนใฏใๆฐใใช่ฆ็นใใขใคใใขใ็ใฟๅบใใใใฎ้่ฆใชใใญใปในใจ่ใใใใพใใใใใฏใๆ่ใฎ่ช็ฑๅบฆใ้ซใใๆฐใใช่ฆ็นใใขใคใใขใ็ใฟๅบใใใใฎ้่ฆใชใใญใปในใจ่ใใใใพใใ
KJๆณใฎ่กจๆญใใใคๅคๆดใใใฎใ(ไฝๆใใญใปใน)ใซใคใใฆใฏใไบๆใใชใใฃใใๆฐใใใใฎใใ็ใพใใใใใใฏใฏใฏใฏใใใใจใใ่ใๆนใ็คบใใใฆใใพใใใใใฏใๆฐใใช่ฆ็นใใขใคใใขใ็ใฟๅบใใใใฎ้่ฆใชใใญใปในใจ่ใใใใพใใ
SECIใขใใซใจPDCAใตใคใฏใซใซใคใใฆใฏใSECIใขใใซใจPDCAใตใคใฏใซใฎ้ขไฟใซ่จๅใใใฆใใพใใPDCAใฎๅใซS(ๅ ฑๅๅ)ใๅฟ ่ฆใจใใไธปๅผตS-PDCAใใใใฆใใพใใใใใฏใPlanใจใฏใ่จ่ชๅใใใฆใชใๆ้ป็ฅใๅฝขๅผๅใใใใใ็ตๅใใฆไฝใใใใใฎใชใฎใงใไบๅใซๅ ฑๅๅใใฆๆ้ป็ฅใๅ ฑๆใใฆใใชใใจใ็ดๅพๆใฎใชใ่จ็ปใใซใชใฃใฆใใพใใจใใ่ใๆนใ็คบใใฆใใพใใ
ใใฉใฐใกใณใ
ABC179
- ใฎใ ใใ็ธๅฏพใปใฐใกใณใๆจใ ใ่ชไฝใณใผใใฎๆด็ใใพใ ใ ใฃใโฆ
- ๆฎใ10ๅใ ใฃใใฎใง็ฆใฃใฆใใพใฃใ
- ๅคใๅคๅใใ็นใไบๅๆข็ดขใจใใๆใใใ
- ใ ใใPythonใฎbisectใฏใฝใผใๆธใฟ้ ๅใ่ฆๆฑใใ
- ใใฎๅ้กๆกไปถใ ใจ้ ๅใธใฎๆฟๅ ฅใ็บ็ใใฆO(N)ใซใชใใใ่ฏใใชใใญ
- ๆฌ่ณช็ใซใฏPythonใงไฝฟใใๅนณ่กกไบๅๆจใใใๅใๅบใใฆไฝฟใใใใใซๆบๅใใจใในใใชใฎใใชใผ
- ไปๅใฎๅ้กใซ้ใใฐใๅ ้ ญไปฅๅคใธใฎ่ฟฝๅ ใฏๅฟ ่ฆใชใใใฎใงใ้้ ใงๆใฆใฐๆซๅฐพ่ฟฝๅ ใงO(1)ใซใชใใใใใชใใญใผใ ใใชใ
- ้้ ใงๆใฃใฆไบๅๆข็ดขใใใใผใธใงใณ python
def main():
from bisect import bisect_left
N, Q = map(int, input().split())
ret = (N - 2) ** 2
xs = [-N]
xvals = [N - 2]
ys = [-N]
yvals = [N - 2]
for _q in range(Q):
q, x = map(int, input().split())
if q == 1:
i = bisect_left(xs, -x)
ret -= xvals[i - 1]
if i == len(xs) and yvals[-1] > x - 2:
ys.append(-xvals[i - 1] - 2)
yvals.append(x - 2)
else:
y = x
i = bisect_left(ys, -y)
ret -= yvals[i - 1]
if i == len(ys) and xvals[-1] > y - 2:
xs.append(-yvals[i - 1] - 2)
xvals.append(y - 2)
print(ret)
- ็นๅๅพใ ใใ้ ๅปถใปใฐใกใณใๆจใใฏใชใๅๅฏพใปใฐใกใณใๆจใงๅๅใชใฎใ ใใ้ ๅปถใปใฐใกใณใๆจใไฝฟใฃใฆ่งฃใใฆใไบบใใใใใใใใใใใใงใใใฃใใฎใใใชใ
ไพ้ ผใๅ ๅปถใฐใใซใใ็ไพ
ไธ่จใฎใๅฃๅฎใใๅฃๅฎใ ใจๆใ็็ฑใฏใ่ชๅใงใใฃใใ้ๆใงใใ่ฆ่พผใฟใใใใชใใใใใชใใงๅ ๅปถใฐใใซใใใใจใใ็พ่ฑกใฏ็บ็ใใชใใ ใใใใใ ใ ใๆ้ใชใฝใผในใ่ถณใใชใใใใใใฐใใฐใๅพใใใใใฎใฎๆๅพ ๅคใไฝใใฎใงใๆ้ใชใฝใผในใๅชๅ ็ใซๅฒใๅฝใฆใๆๆๆฑบๅฎใใงใใชใใใจใใใใจใใๆ้ใใชใใใจใใ็บ่จใ่ฆณๆธฌใใใๆใฎใใใใ
extra info
json size: 40673012 pickle size: 735437681 previous notes size: 1314 previous notes: ๐ค2023-08-12 02:30 titles: ABC179, ไพ้ ผใๅ ๅปถใฐใใซใใ็ไพ, ppoi, AGC032B, Hatena2009-04-26, ใใใผใใฒใผใ ใจใใฆใฎใฏใชใผใณใฉใณใฒใผใธใใจใฏ, Hatena2009-05-14, ๅใคใถใใGLSL