oj.uz

Submission #973855

# Submission time Handle Problem Language Result Execution time Memory
973855 2024-05-02T11:55:34 Z canadavid1 Spiral (BOI16_spiral) Python 3
29 / 100
 20 ms 3208 KB 
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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3164 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 3208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3164 KB Output is correct
2 Correct 16 ms 3164 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 3164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3164 KB Output is correct
2 Incorrect 20 ms 3208 KB Output isn't correct
3 Halted 0 ms 0 KB -