Problem:


Score : 500 points

Problem Statement

On a two-dimensional plane, there are m lines drawn parallel to the x axis, and n lines drawn parallel to the y axis.
Among the lines parallel to the x axis, the i-th from the bottom is represented by y = y_i.
Similarly, among the lines parallel to the y axis, the i-th from the left is represented by x = x_i.

For every rectangle that is formed by these lines, find its area, and print the total area modulo 10^9+7.

That is, for every quadruple (i,j,k,l) satisfying 1\leq i < j\leq n and 1\leq k < l\leq m, find the area of the rectangle formed by the lines x=x_i, x=x_j, y=y_k and y=y_l, and print the sum of these areas modulo 10^9+7.

Constraints

2 \leq n,m \leq 10^5

-10^9 \leq x_1 < ... < x_n \leq 10^9

-10^9 \leq y_1 < ... < y_m \leq 10^9

x_i and y_i are integers.

Input

Input is given from Standard Input in the following format:

n m
x_1 x_2 ... x_n
y_1 y_2 ... y_m

Output

Print the total area of the rectangles, modulo 10^9+7.

Sample Input 1

3 3
1 3 4
1 3 6

Sample Output 1

60

The following figure illustrates this input:

The total area of the nine rectangles A, B, ..., I shown in the following figure, is 60.

Sample Input 2

6 5
-790013317 -192321079 95834122 418379342 586260100 802780784
-253230108 193944314 363756450 712662868 735867677

Sample Output 2

835067060



Sample input:
3 3
1 3 4
1 3 6


Sample output:
60

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*- coding: utf-8 -*-
mod = 10**9 + 7

n, m = map(int, raw_input().split())
x = map(int, raw_input().split())
y = map(int, raw_input().split())

sx = sum(x)
sy = sum(y)
zx = 0
zy = 0
for i, xi in enumerate(x):
    zx += sx - (n - i)*xi
    sx -= xi
    zx %= mod
for i, yi in enumerate(y):
    zy += sy - (m - i)*yi
    sy -= yi
    zy %= mod
print zx*zy % mod

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
mod = 10**9 + 7

n, m = map(int, raw_input().split())
x = map(int, raw_input().split())
y = map(int, raw_input().split())

sx = sum(x)
sy = sum(y)
zx = 0
zy = 0
for i, xi in enumerate(x):
    zx += sx - (n - i)*xi
    sx -= xi
    zx = (zx + mod) % mod
for i, yi in enumerate(y):
    zy += sy - (m - i)*yi
    sy -= yi
    zy = (zy + mod) % mod

print zx*zy%mod

Submission status: Accepted

Solution code:
def getsum(x, n):
    ans = 0
    acu = 0
    for i in range(n // 2):
        acu += (x[n - i - 1] - x[i])
        ans = (ans + acu) % 1000000007
    if n % 2 == 0:
        ans = ans * 2 - acu
    else:
        ans = ans * 2
    return ans % 1000000007

n, m = (int(i) for i in input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

print(getsum(x, n) * getsum(y, m) % 1000000007)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
mod = 10**9 + 7
X = [int(i) for i in input().split()]
Y = [int(i) for i in input().split()]
ans = 0
for i in range(n):
	ans += X[i]*(n-2*i-1)%mod
t = 0
for j in range(m):
	t += Y[j]*(m-2*j-1)%mod
ans *= t%mod
print(ans%mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

N, M = map(int, input().split())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))
MOD = 1000000000 + 7
sub = 0
for i in range(N - 1):
    sub += (i + 1) * (N - i - 1) * (X[i + 1] - X[i])
    sub %= MOD
ans = 0
for i in range(M - 1):
    ans += (i + 1) * (M - i - 1) * (Y[i + 1] - Y[i])
    ans %= MOD
ans *= sub
print(ans % MOD)

Submission status: Accepted

Solution code:
from operator import sub
def coeff(n, i):
  return i*(i+1) + (n-2*i)*(i+1)
  
Mod = 10**9+7
n, m = map(int, input().split())
x = sorted(map(int, input().split()))
y = sorted(map(int, input().split()))
dx = map(sub, x[1:], x)
dy = map(sub, y[1:], y)

sx = 0
for i, v in enumerate(dx):
  sx += v * coeff(n-1, i)
  sx %= Mod
  #print(v, coeff(n-1, i), v * coeff(n-1, i), sx) 
  
sy = 0
for i, v in enumerate(dy):
  sy += v * coeff(m-1, i)
  sy %= Mod  
  #print(v, coeff(m-1, i), v * coeff(m-1, i), sy) 
  
print(sx * sy % Mod)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = map(int, input().split())
y = map(int, input().split())
x = list(x)
y = list(y)
x.sort()
y.sort()
M = 10 ** 9 + 7
a = sum([(2 * k - n + 1) * x[k] for k in range(n)])
b = sum([(2 * k - m + 1) * y[k] for k in range(m)])
a %= M
b %= M
res = a * b % M
print(res)

Submission status: Accepted

Solution code:
import sys

cin = sys.stdin
# cin = open("in.txt", "r")

MOD = int(1e9+7)

N, M = map(int, cin.readline().split())
x = list(map(int, cin.readline().split()))
y = list(map(int, cin.readline().split()))

def n2total(n):
    total = [0]*n
    cnt = 0
    for i in range((n+1)//2):
        cnt += 1 * (n-i*2)
        total[i] = total[n-1-i] = cnt
    return total

x_total = n2total(N-1)
# print(x_total)
y_total = n2total(M-1)
# print(y_total)
xlen = 0
for i in range(N-1):
    xlen += (x[i+1]-x[i])*x_total[i]
ylen = 0
for j in range(M-1):
    ylen += (y[j+1]-y[j])*y_total[j]

ans = xlen * ylen % MOD
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
xs = list(map(int, input().split()))
ys = list(map(int, input().split()))

MOD = int(1e9) + 7

def fn(ls):
    l = len(ls)
    ret = 0
    for i in range(l):
        c = l - 1 - 2 * i
        ret += c * ls[l-i-1]
        ret %= MOD
    return ret

x = fn(xs)
y = fn(ys)
ans = x * y % MOD
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys

MOD = 10**9 + 7

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

EPS = 1e-9

#http://www.deqnotes.net/acmicpc/2d_geometry/lines
def dot(a, b):
    return a.real * b.real + a.imag * b.imag

def cross(a, b):
    return a.real * b.imag - a.imag * b.real

def distance(a, b, c):
    if dot(b-a, c-a) <= EPS:
        return abs(c-a)
    if dot(a-b, c-b) <= EPS:
        return abs(c-b)
    return abs(cross(b-a, c-a)/(b-a))

def dijkstra(s):
    dist = z[:]
    dist[s] = 0
    heap = []
    heapq.heappush(heap, (0, s))
    
    while heap:
        dd, v = heapq.heappop(heap)
        dv = dist[v]
        if dv < dd:
            continue
        for i in path[v]:
            dvi = 1
            if dist[i] > dv + dvi:
                dist[i] = dv + dvi
                heapq.heappush(heap, (dist[i], i))
    return dist

n, m = ln()
X = ln()
Y = ln()
LX = len(X)
LY = len(Y)

for i in xrange(LX - 1, -1, -1):
    X[i] -= X[i - 1]

for i in xrange(LY - 1, -1, -1):
    Y[i] -= Y[i - 1]

for i in xrange(1, LX):
    X[i] *= i * (LX - i)

for i in xrange(1, LY):
    Y[i] *= i * (LY - i)

sum_x = 0
for i in xrange(1, LX):
    sum_x += X[i]
    sum_x %= MOD

sum_y = 0
for i in xrange(1, LY):
    sum_y += Y[i]
    sum_y %= MOD

print sum_x * sum_y % MOD

Submission status: Accepted

Solution code:
n,m = list(map(int,input().split(" ")))

x = list(map(int,input().split(" ")))
y = list(map(int,input().split(" ")))

def how(i):
    j = i
    l = [j-1 for i in range(i-1)]
    j = i-3
    for k in range(1,len(l)):
        l[k] = l[k-1]+j
        j -= 2
    return(l)

xh = how(n)
yh = how(m)

xd = [x[i+1]-x[i] for i in range(n-1)]
yd = [y[i+1]-y[i] for i in range(m-1)]

xs = sum([xd[i]*xh[i] for i in range(n-1)])
ys = sum([yd[i]*yh[i] for i in range(m-1)])

print((xs*ys)%(10**9+7))

Submission status: Accepted

Solution code:
n,m = map(int, input().split(' '))
x = list(map(int, input().split(' ')))
y = list(map(int, input().split(' ')))

x = [x[i+1]-x[i] for i in range(len(x)-1)]
y = [y[i+1]-y[i] for i in range(len(y)-1)]

total_x =0
for i in range(n-1):
    buf = min([i+1,n-1-i])
    buf = buf*(n-1)-buf*buf+buf
    total_x += x[i]*buf
    total_x %= 1000000007


total_y =0
for i in range(m-1):
    buf = min([i+1,m-1-i])
    buf = buf*(m-1)-buf*buf+buf
    total_y += y[i]*buf
    total_y %= 1000000007

print(total_x*total_y%1000000007)

Submission status: Accepted

Solution code:
n,m = list(map(int,input().split()))

X =list(map(int,input().split()))
Y = list(map(int,input().split()))


"""
3*2 * 5*2

"""
#print( (X[-1]-X[0])*(n-1) * (m-1)*(Y[-1]-Y[0]) )# %1000000007

def calc_diff(L):
    result = 0
    #n_of_diff
    for i,l in enumerate(L):
        if i==len(L)-1:
            break
            #hidari x migi
        result += (i+1)*(len(L)-i-1)* (L[i+1]-L[i])
        result = result %1000000007
        #print(result)
    return result

print(calc_diff(X) *calc_diff(Y) %1000000007 )

Submission status: Accepted

Solution code:
import numpy as np
n, m = map(int, input().split())
x = np.array(list(map(int, input().split())), dtype='int64')
y = np.array(list(map(int, input().split())), dtype='int64')

xsum = np.sum(x[:0:-1].cumsum() - x[n-2::-1] * np.arange(1,n))
ysum = np.sum(y[:0:-1].cumsum() - y[m-2::-1] * np.arange(1,m))

print((xsum % 1000000007) * (ysum % 1000000007) % 1000000007)

Submission status: Accepted

Solution code:
from sys import stdin
n,m = map(int,stdin.readline().split())
a = map(int,stdin.readline().split())
b = map(int,stdin.readline().split())
a.sort()
b.sort()
x = []
y = []
for i in xrange(1,n):
    x.append(a[i] - a[i-1])
for i in xrange(1,m):
    y.append(b[i] - b[i-1])   
fir = 0
sec = 0
n = len(x)
m = len(y)
for i in xrange(n):
    fir += (i+1) * (n-i)*x[i]
for i in xrange(m):
    sec += (i+1) * (m-i) * y[i]
mod = 10**9 + 7
print (fir * sec)%mod

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
x = map(int, raw_input().split())
y = map(int, raw_input().split())
M = 10**9+7
ansx = 0
for i in range(n-1):
    ansx += (x[i+1]-x[i])*(i+1)*(n-i-1)
    ansx %= M
ansy = 0
for j in range(m-1):
    ansy += (y[j+1]-y[j])*(j+1)*(m-j-1)
    ansy %= M
print (ansx*ansy)%M

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))

xs = 0
for i in range(N):
    xs += i  * X[i]
    xs -= (N - i - 1) * X[i]
    xs %= MOD
ys = 0
for i in range(M):
    ys += i  * Y[i]
    ys -= (M - i - 1) * Y[i]
    ys %= MOD
print(xs * ys % MOD)

Submission status: Runtime Error

Solution code:
ai = lambda: list(map(int, input().split()))

n,m = ai()
x = ai()
y = ai()
mod = 10**9+7
ans = 0

sx,ssx,sy,ssy = [x[0]], [x[-1]], [y[0]], [y[-1]]
for i in range(1, n):
    sx.append(sx[-1] + x[i])
    ssx.append(ssx[-1] + x[-i-1])
    sy.append(sy[-1] + y[i])
    ssy.append(ssy[-1] + y[-i-1])

a = sum(ssx[i] - sx[i] for i in range(n)) % mod
b = sum(ssy[i] - sy[i] for i in range(n)) % mod

ans = a*b % mod
print(ans)

Submission status: Runtime Error

Solution code:
n, m = [int(i) for i in input().split()]
X = [int(i) for i in input().split()]
Y = [int(i) for i in input().split()]

p = 10 ** 9 + 7

ans = 0
xc = n // 2
yc = m // 2
n -= 1
m -= 1
h = Y[-1] - Y[0]
w = X[-1] - X[0]

if n % 2 == 0 and m % 2 == 0:
    ans = n * m * h * w

elif n % 2 == 1 and m % 2 == 1:
    xd = X[xc] - X[xc-1]
    yd = Y[yc] - Y[yc-1]
    ans = n * (m+1) * d * (h - yd) + (n+1) * m * d * (w - xd) + (n+1) * (m+1) * yd * xd + n * m * (w - xd) * (h - yd)

elif n % 2 == 1:
    d = X[xc] - X[xc-1]
    ans = (n * (m+1) * d + (w - d)) * h

elif n % 2 == 1:
    d = Y[yc] - Y[yc-1]
    ans = ((n+1) * m * d + (h - d)) * w

print(ans % p)

Submission status: Runtime Error

Solution code:
#coding:utf-8

[n, m] = map(int, input().split(" "))
#n, m = 3,3
xs = map(int, input().split(" "))
ys = map(int, input().split(" "))
#xs = [1,3,4]
#ys = [1,3,6]

x_min, x_max = xs[0], xs[-1]
y_min, y_max = ys[0], ys[-1]
x_len = len(xs) - 2
y_len = len(ys) - 2

size = (x_max - x_min) * (y_max - y_min)
combs = pow(2, x_len + y_len)

result = size * combs
result = result % (pow(10, 9) + 7)
print result