Submission #973855

#	Time	Username	Problem	Language	Result	Execution time	Memory
973855		canadavid1	Spiral (BOI16_spiral)	Cpython 3	29 / 100	20 ms	3208 KiB

spiral

def eval_poly(poly,num,mod=None):
    a = round(sum(v*pow(num,i,mod) for i,v in enumerate(poly)))
    if mod is not None: a %= mod
    return a

xpyp = [0,1,2,-4,2]
xnyp = [0,0,4,0,2]
xpyn = [0,-4,10,0,2]
xnyn = [0,-1,2,4,2]
diag = [[xnyn,xnyp],[xpyn,xpyp]]

xp = [0,19/6,-7/2,4/3]
xn = [0,13/6,5/2,4/3]
yp = [0,13/6,-5/2,4/3]
yn = [0,19/6,7/2,4/3]
col = [[xn,xp],[yn,yp]]
MOD = 10**9+7

def rect_center(x: int,y: int): # rectangle from the lower left corner of (0,0) to lower left of (x,y)
    ygtx = abs(x) < abs(y)
    sm = [x,y][ygtx]>=0
    sN = [y,x][ygtx]>=0
    smi = -1 if (ygtx != (x >= 0)) != (y >= 0) else 1
    n = min(abs(x),abs(y))
    N = max(abs(x),abs(y))
    sqp = diag[x >= 0][y >= 0]
    square = eval_poly(sqp,n,MOD)
    rp = col[ygtx][sm]
    sc: int = (eval_poly(rp,N)-eval_poly(rp,n))
    sc *= n
    f = n-sN
    sc += ((N-n)*f*(f+1))//2 * smi
    if x > 0 and y < 0 and -y < x: sc -= 8*y
    return (square + sc)%MOD

def rect(xA,yA,xB,yB):
    x = sorted([xA,xB])
    x[1]+=1
    y = sorted([yA,yB])
    y[1]+=1
    
    s = 0
    for a in [0,1]:
        for b in [0,1]:
            s += rect_center(x[a],y[b]) * (-1 if x[0]*x[1]>0 and abs(x[a])<abs(x[1-a]) else 1) \
                                        * (-1 if y[0]*y[1]>0 and abs(y[b])<abs(y[1-b]) else 1)
    return s%MOD

_,q = map(int,input().split())
for i in range(q):
    print(rect(*map(int,input().split())))

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