๐ค2023-08-12 02:49
___BELOW_IS_LESS_INTERESTING___
ๆฝ่ฑกๅใๅฟ
ใใใๅใงใชใใจใใ่ใๆนใฏใๅ
ทไฝ็ใชใใฎใๆใๅบใใใใฎใใใฏใใๅคๆงใชใใฎใ้ฃๆณใงใใ็ถๆ
ใไฟใคใใจใฎ้่ฆๆงใ็คบใใฆใใพใใใใใฏใ่จ่ใฎ้ฃๆณ็ๆๅณใงใคใชใใใใจใใใขใณใฑใผใ่ชฟๆปใใใฎKJๆณใ้ฃใใ็็ฑใจใ้ข้ฃใใฆใใพใใใพใใใ้ใกใฆๆนใใใใใใใ้ใกใจใใใใจใใใ่ซ่ชใใใใฎๅผ็จใฏใ้ใกใ็ฏใใใจ่ชไฝใฏไบบ้ใฎๆง่ณชใงใใใ้ฟใใใใชใใใใใฎ้ใกใ่ช่ญใใใใใๆนใใชใใใจใ็ใฎ้ใกใงใใใจใใๆใใ็คบใใฆใใพใใใใใฏใ็ ็ฉถใใใถใคใณใฎใใญใปในใซใใใฆใ้่ฆใชๆ่จใงใใใจๆใใพใใ
ๅ็ท ๅฝนใ็คพๅ
ๅ
ฌๅใใใจใใ่ใๆนใฏใๅ็ท ๅฝนใจใใๅฝน่ทใ้ๅธธใ็ตๅถในใญใซใฎๅฐ้ๅฎถใ็คพๅ
็งฉๅบใซใใใ้ท่ใจใใฆใฎๅฝนๅฒใๆใใใใใตใคใใฆใบใฎๅ
ฌๅๅ็ท ๅฝนใฏใใใงใฏใชใใจใใๆๆใใใใพใใๅ็ท ๅฝนใๅขใใใใจใซใใๆๆๆฑบๅฎใฎ้
ใใใใคใขในใๆธๅฟตใใใพใใใใตใคใใฆใบใฎใใใฃใฆใฟใฆๅ้กใๆใใใซใชใใฐใใใใใใใใจใใๆๅใใใไฝใๅ้กใใใใฐใใใใฐใใใจ่ใใใใฆใใพใใใใใฏใใใใ่ชไฝใๆ่ปฝใซใใใฏใขใใใใใจใใๆๆกใจ้ข้ฃใใใใใใงใใๅคงๅน
ใชๆงๆๅคๆดใใใใใใใใใๆใใจใใใทใใฅใจใผใทใงใณใใซใใผใใใใใซใใใใ่ชไฝใๆ่ปฝใซ่ค่ฃฝใใฆใใใฏใขใใใงใใใจ่ฏใใจใใๆๆกใใใใพใใใใใฏใ็ดใงไฝๆฅญใใใฆใใๆใซใฏๆฌ่ณช็ใซไธๅฏ่ฝใ ใฃใใใจใ ใใใใธใฟใซๅใซใใๅฏ่ฝใซใชใฃใใใใใฏใขใใใฏๅคๆดใใๆๆใ็ทฉๅใใๅนๆใใใใจ่ใใใใพใใ
ๅ่ๅผฑๆงใซใคใใฆใฎ่ใๆนใฏใใใๅ้ใงๅฎๅ
จ็ญใๅใ(=่ฒ ใฎใใฉใใฏในใฏใณใซๅฏพใใฆ้ ๅฅ)ใๅฅใฎๅ้ใง้ๅฎ็ใชในใฏใใใใใๅใใใจใงใๅคงๅใกใใๅคงใใชๅฉ็ใๅพใ(=ๆญฃใฎใใฉใใฏในใฏใณใๆฎใ)ใจใใใใฎใงใใใใใซใใฃใฆๅ่ใใๅฎ็พใใใจใใใฆใใพใใใพใใใฟใฌใใฏใๅ่ใใจใฏใชใใทใงใณใๆใคใใจใ ใจ่ฟฐในใฆใใพใใใใชใใทใงใณใจใฏ็งใใกใๅ่ใใใฆใใใใใฎใ ใใชใใทใงใณใใใใฐใไธ็ขบๅฎๆงใฎ่ฒ ใฎๅด้ขใใๆทฑๅปใชๅฎณใใใใใใใจใชใใไธ็ขบๅฎๆงใฎๆญฃใฎๅด้ขใใๅฉ็ใๅพใใใจใใงใใใฎใ ใใจใใ่ใๆนใฏใใชในใฏ็ฎก็ใซใใใฆ้่ฆใช่ฆ็นใจใชใใพใใ
่ฑ็ท=้ฃๆณ=ๆฐ็ตๅ็บ่ฆใจใใ่ใๆนใฏใๆฐใใช่ฆ็นใใขใคใใขใ็ใฟๅบใใใใฎ้่ฆใชใใญใปในใจ่ใใใใพใใใใใฏใๆ่ใฎ่ช็ฑๅบฆใ้ซใใๆฐใใช่ฆ็นใใขใคใใขใ็ใฟๅบใใใใฎ้่ฆใชใใญใปในใจ่ใใใใพใใ
KJๆณใฎ่กจๆญใใใคๅคๆดใใใฎใ(ไฝๆใใญใปใน)ใซใคใใฆใฏใไบๆใใชใใฃใใๆฐใใใใฎใใ็ใพใใใใใใฏใฏใฏใฏใใใใจใใ่ใๆนใ็คบใใใฆใใพใใใใใฏใๆฐใใช่ฆ็นใใขใคใใขใ็ใฟๅบใใใใฎ้่ฆใชใใญใปในใจ่ใใใใพใใ
SECIใขใใซใจPDCAใตใคใฏใซใซใคใใฆใฏใSECIใขใใซใจPDCAใตใคใฏใซใฎ้ขไฟใซ่จๅใใใฆใใพใใPDCAใฎๅใซS(
ๅ
ฑๅๅ)ใๅฟ
่ฆใจใใไธปๅผต
S-PDCAใใใใฆใใพใใใใใฏใPlanใจใฏใ่จ่ชๅใใใฆใชใๆ้ป็ฅใๅฝขๅผๅใใใใใ็ตๅใใฆไฝใใใใใฎใชใฎใงใไบๅใซๅ
ฑๅๅใใฆๆ้ป็ฅใๅ
ฑๆใใฆใใชใใจใ
็ดๅพๆใฎใชใ่จ็ปใใซใชใฃใฆใใพใใจใใ่ใๆนใ็คบใใฆใใพใใ
ใฎใ ใใ็ธๅฏพใปใฐใกใณใๆจใ ใ่ชไฝใณใผใใฎๆด็ใใพใ ใ ใฃใโฆ
ๆฎใ10ๅใ ใฃใใฎใง็ฆใฃใฆใใพใฃใ
ๅคใๅคๅใใ็นใไบๅๆข็ดขใจใใๆใใใ
ใ ใใPythonใฎbisectใฏใฝใผใๆธใฟ้
ๅใ่ฆๆฑใใ
ใใฎๅ้กๆกไปถใ ใจ้
ๅใธใฎๆฟๅ
ฅใ็บ็ใใฆO(N)ใซใชใใใ่ฏใใชใใญ
ๆฌ่ณช็ใซใฏPythonใงไฝฟใใๅนณ่กกไบๅๆจใใใๅใๅบใใฆไฝฟใใใใใซๆบๅใใจใในใใชใฎใใชใผ
ไปๅใฎๅ้กใซ้ใใฐใๅ
้ ญไปฅๅคใธใฎ่ฟฝๅ ใฏๅฟ
่ฆใชใใใฎใงใ้้ ใงๆใฆใฐๆซๅฐพ่ฟฝๅ ใงO(1)ใซใชใใใใใชใใญใผใ ใใชใ
้้ ใงๆใฃใฆไบๅๆข็ดขใใใใผใธใงใณ
pythondef 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