Submission #36935205

Source Code Expand

from collections import defaultdict
n,d=map(int,input().split())
M=998244353
p2=[1]*400
for i in range(400-1): p2[i+1]=p2[i]*2%M

def calc(cnt):
  ans=0
  ans+=(p2[cnt[7]]-1)*p2[cnt[0]+cnt[1]+cnt[2]+cnt[3]+cnt[4]+cnt[5]+cnt[6]]
  ans+=(p2[cnt[6]]-1)*(p2[cnt[1]+cnt[3]+cnt[5]]-1)%M*p2[cnt[0]+cnt[2]+cnt[4]]
  ans+=(p2[cnt[5]]-1)*(p2[cnt[2]+cnt[3]]-1)%M*p2[cnt[0]+cnt[1]+cnt[4]]
  ans+=(p2[cnt[3]]-1)*(p2[cnt[4]]-1)%M*p2[cnt[0]+cnt[1]+cnt[2]]
  ans+=(p2[cnt[1]]-1)*(p2[cnt[2]]-1)%M*(p2[cnt[4]]-1)%M*p2[cnt[0]]
  return ans%M

def solve(pss,y,z):
  ans=0
  cnt=[0]*8
  pos=0
  n=len(pss)

  for ps in pss:
    while pos<n and pss[pos][0][0]<=ps[0][0]+d:
      for xx,yy,zz in pss[pos]:
        if y<=yy<=y+d and z<=zz<=z+d:
          cnt[((y==yy)<<1)|(z==zz)]+=1
      pos+=1

    for i in range(4,8):cnt[i]=0
    for xx,yy,zz in ps:
      if y<=yy<=y+d and z<=zz<=z+d:
        cnt[  ((y==yy)<<1)|(z==zz)]-=1
        cnt[4|((y==yy)<<1)|(z==zz)]+=1
    ans+=calc(cnt)
  return ans

ys=set()
zs=set()
pss=defaultdict(list)
for _ in range(n):
  p,q=map(int,input().split())
  x=p
  y=q-p
  z=-q
  pss[x].append((x,y,z))
  ys.add(y)
  zs.add(z)

_,pss=list(zip(*sorted((pss.items()))))
ans=0
for y in ys:
  for z in zs:
    ans+=solve(pss,y,z)

print(ans%M)

Submission Info

Submission Time
Task G - Do Use Hexagon Grid 2
User kyopro_friends
Language PyPy3 (7.3.0)
Score 600
Code Size 1304 Byte
Status AC
Exec Time 2757 ms
Memory 78148 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 40
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt, random_33.txt, random_34.txt, random_35.txt, random_36.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
hand.txt AC 67 ms 65036 KiB
random_01.txt AC 2757 ms 77288 KiB
random_02.txt AC 257 ms 75588 KiB
random_03.txt AC 2141 ms 76616 KiB
random_04.txt AC 1274 ms 76512 KiB
random_05.txt AC 1801 ms 76740 KiB
random_06.txt AC 126 ms 75412 KiB
random_07.txt AC 2134 ms 76832 KiB
random_08.txt AC 185 ms 76648 KiB
random_09.txt AC 2165 ms 78148 KiB
random_10.txt AC 284 ms 76400 KiB
random_11.txt AC 1882 ms 76800 KiB
random_12.txt AC 1854 ms 76000 KiB
random_13.txt AC 2119 ms 76468 KiB
random_14.txt AC 1480 ms 75892 KiB
random_15.txt AC 2165 ms 76188 KiB
random_16.txt AC 998 ms 76404 KiB
random_17.txt AC 329 ms 75472 KiB
random_18.txt AC 238 ms 75036 KiB
random_19.txt AC 322 ms 76080 KiB
random_20.txt AC 248 ms 75200 KiB
random_21.txt AC 279 ms 75488 KiB
random_22.txt AC 250 ms 75056 KiB
random_23.txt AC 344 ms 75784 KiB
random_24.txt AC 253 ms 75444 KiB
random_25.txt AC 355 ms 76464 KiB
random_26.txt AC 265 ms 75128 KiB
random_27.txt AC 343 ms 75180 KiB
random_28.txt AC 262 ms 74820 KiB
random_29.txt AC 320 ms 75076 KiB
random_30.txt AC 278 ms 75000 KiB
random_31.txt AC 316 ms 75232 KiB
random_32.txt AC 260 ms 74876 KiB
random_33.txt AC 298 ms 75876 KiB
random_34.txt AC 268 ms 74908 KiB
random_35.txt AC 290 ms 75404 KiB
random_36.txt AC 252 ms 74756 KiB
sample_01.txt AC 54 ms 65240 KiB
sample_02.txt AC 48 ms 65468 KiB
sample_03.txt AC 50 ms 65592 KiB