Submission #973898

#	Time	Username	Problem	Language	Result	Execution time	Memory
973898		canadavid1	Spiral (BOI16_spiral)	Cpython 3	100 / 100	15 ms	3164 KiB

spiral

def eval_poly(poly,num):return sum(v*num**i for i,v in enumerate(poly))
xpyp = [1,2,-4,2]
xnyp = [0,4,0,2]
xpyn = [-4,10,0,2]
xnyn = [-1,2,4,2]
diag = [[xnyn,xnyp],[xpyn,xpyp]]

xp = [19,-21,8]
xn = [13,15,8]
yp = [13,-15,8]
yn = [19,21,8]
col = [[xn,xp],[yn,yp]]
MOD = 10**9+7

def rc(x,y):
 X=abs(x);Y=abs(y)
 L=X<Y
 n = min(X,Y)
 N = max(X,Y)
 sm=[x,y][L]>=0
 sN=[y,x][L]>=0
 smi=-1 if(L!=(x >= 0))!=(y>=0)else 1
 rp=col[L][sm]
 sc=eval_poly(diag[x>=0][y>=0],n)+(N*eval_poly(rp,N)-n*eval_poly(rp,n))//6
 sc*=n
 f=n-sN
 if x>0 and y<0 and -y<x:sc-=8*y
 return sc+((N-n)*f*(f+1))//2 * smi

def rect(x,y,X,Y):
 X+=1
 Y+=1
 x=[x,X]
 y=[y,Y]
 s = 0
 for a in [0,1]:
  for b in [0,1]:
   s+=rc(x[a],y[b])*(1 if(x[0]*x[1]>0 and abs(x[a])<abs(x[1-a]))==(y[0]*y[1]>0 and abs(y[b])<abs(y[1-b]))else -1)
 return s%MOD


for i in range(int(input().split()[1])):
 print(rect(*map(int,input().split())))

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 31 / 31
• Subtask 5: 25 / 25