Submission #544727

#	Time	Username	Problem	Language	Result	Execution time	Memory
544727		rainboy	Spiral (BOI16_spiral)	C11	100 / 100	1 ms	288 KiB

spiral

#include <stdio.h>

#define MD	1000000007
#define INV2	500000004
#define INV4	250000002
#define INV6	166666668
#define INV30	233333335

long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }

long long sum0(long long n) {
	return n;
}

long long sum1(long long n) {
	return n * (n + 1) % MD * INV2 % MD;
}

long long sum2(long long n) {
	return n * (n + 1) % MD * (n * 2 + 1) % MD * INV6 % MD;
}

long long sum3(long long n) {
	return n * (n + 1) % MD * n % MD * (n + 1) % MD * INV4 % MD;
}

long long sum4(long long n) {
	return n * (n + 1) % MD * (n * 2 + 1) % MD * ((n * n * 3 + n * 3 - 1) % MD) % MD * INV30 % MD;
}

long long sum0_(long long l, long long r) {
	return (sum0(r) - sum0(l - 1)) % MD;
}

long long sum1_(long long l, long long r) {
	return (sum1(r) - sum1(l - 1)) % MD;
}

long long sum2_(long long l, long long r) {
	return (sum2(r) - sum2(l - 1)) % MD;
}

long long sum3_(long long l, long long r) {
	return (sum3(r) - sum3(l - 1)) % MD;
}

long long sum4_(long long l, long long r) {
	return (sum4(r) - sum4(l - 1)) % MD;
}

int main() {
	int n, q;

	scanf("%d%d", &n, &q);
	while (q--) {
		long long x1, x2, y1, y2, l, r, ans;

		scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
		ans = x1 <= 0 && 0 <= x2 && y1 <= 0 && 0 <= y2;
		/* x > 0, -x < y <= x
		 * A(x, y) = (2 x - 1)^2 + y + x = 4 x^2 - 3 x + y + 1
		 * A(x, x) = 4 x^2 - 2 x + 1
		 * A(x, -x) = 4 x^2 - 4 x + 1
		 *
		 * A(x, y) (A(x, y) + 1) / 2
		 * = (4 x^2 - 3 x + y + 1)(4 x^2 - 3 x + y + 2) / 2
		 * = (16 x^4 - 24 x^3 + (8 y + 21) x^2 - (6 y + 9) x + (y + 1) (y + 2)) / 2
		 *
		 * A(x, x) (A(x, x) + 1) / 2
		 * = (4 x^2 - 2 x + 1) (4 x^2 - 2 x + 2) / 2
		 * = 8 x^4 - 8 x^3 + 8 x^2 - 3 x + 1
		 *
		 * A(x, -x) (A(x, -x) + 1) / 2
		 * = (4 x^2 - 4 x + 1) (4 x^2 - 4 x + 2) / 2
		 * = 8 x^4 - 16 x^3 + 14 x^2 - 6 x + 1
		 */
		l = max(x1, max(max(y1, -y2 + 1), 1)), r = min(x2, y2 - 1);
		if (l <= r)
			ans = (ans + (sum4_(l, r) * 8
						- sum3_(l, r) * 8
						+ sum2_(l, r) * 8
						- sum1_(l, r) * 3
						+ sum0_(l, r))) % MD;
		l = max(l, y2), r = x2;
		if (l <= r)
			ans = (ans + (sum4_(l, r) * 16
						- sum3_(l, r) * 24
						+ sum2_(l, r) * (y2 * 8 + 21) % MD
						- sum1_(l, r) * (y2 * 6 + 9) % MD
						+ sum0_(l, r) * (y2 + 1) % MD * (y2 + 2) % MD) % MD * INV2) % MD;
		l = max(x1, max(max(y1, -y2 + 1), 1)), r = min(x2, -y1);
		if (l <= r)
			ans = (ans - (sum4_(l, r) * 8
						- sum3_(l, r) * 16
						+ sum2_(l, r) * 14
						- sum1_(l, r) * 6
						+ sum0_(l, r))) % MD;
		l = max(l, -y1 + 1), r = x2;
		if (l <= r)
			ans = (ans - (sum4_(l, r) * 16
						- sum3_(l, r) * 24
						+ sum2_(l, r) * ((y1 - 1) * 8 + 21) % MD
						- sum1_(l, r) * ((y1 - 1) * 6 + 9) % MD
						+ sum0_(l, r) * y1 % MD * (y1 + 1) % MD) % MD * INV2) % MD;
		/* y > 0, y > x >= -y
		 * A(x, y) = (2 y - 1)^2 + 2 y + y - x = 4 y^2 - y - x + 1
		 * A(-y, y) = 4 y^2 + 1
		 * A(y, y) = 4 y^2 - 2 y + 1
		 *
		 * A(x, y) * (A(x, y) + 1) / 2
		 * = (4 y^2 - y - x + 1) * (4 y^2 - y - x + 2) / 2
		 * = (16 y^4 - 8 y^3 - (8x - 13) y^2 + (2 x - 3) y + (x - 1) (x - 2)) / 2
		 *
		 * A(-y, y) * (A(-y, y) + 1) / 2
		 * = (4 y^2 + 1) * (4 y^2 + 2) / 2
		 * = 8 y^4 + 6 y^2 + 1
		 *
		 * A(y, y) * (A(y, y) + 1) / 2
		 * = (4 y^2 - 2 y + 1) * (4 y^2 - 2 y + 2) / 2
		 * = 8 y^4 - 8 y^3 + 8 y^2 - 3 y + 1
		 */
		l = max(y1, max(max(-x2, x1 + 1), 1)), r = min(y2, -x1 - 1);
		if (l <= r)
			ans = (ans + (sum4_(l, r) * 8
						+ sum2_(l, r) * 6
						+ sum0_(l, r))) % MD;
		l = max(l, -x1), r = y2;
		if (l <= r)
			ans = (ans + (sum4_(l, r) * 16
						- sum3_(l, r) * 8
						- sum2_(l, r) * (x1 * 8 - 13) % MD
						+ sum1_(l, r) * (x1 * 2 - 3) % MD
						+ sum0_(l, r) * (x1 - 1) % MD * (x1 - 2) % MD) % MD * INV2) % MD;
		l = max(y1, max(max(-x2, x1 + 1), 1)), r = min(y2, x2);
		if (l <= r)
			ans = (ans - (sum4_(l, r) * 8
						- sum3_(l, r) * 8
						+ sum2_(l, r) * 8
						- sum1_(l, r) * 3
						+ sum0_(l, r))) % MD;
		l = max(l, x2 + 1), r = y2;
		if (l <= r)
			ans = (ans - (sum4_(l, r) * 16
						- sum3_(l, r) * 8
						- sum2_(l, r) * ((x2 + 1) * 8 - 13) % MD
						+ sum1_(l, r) * ((x2 + 1) * 2 - 3) % MD
						+ sum0_(l, r) * x2 % MD * (x2 - 1) % MD) % MD * INV2) % MD;
		/* x < 0, -x > y >= x
		 * A(x, y) = (2 x + 1)^2 - 4 x - x - y = 4 x^2 - x - y + 1
		 * A(x, x) = 4 x^2 - 2 x + 1
		 * A(x, -x) = 4 x^2 + 1
		 *
		 * A(x, y) * (A(x, y) + 1) / 2
		 * = (4 x^2 - x - y + 1) * (4 x^2 - x - y + 2) / 2
		 * = (16 x^4 - 8 x^3 - (8y - 13) x^2 + (2 y - 3) x + (y - 1) (y - 2)) / 2
		 *
		 * A(x, x) * (A(x, x) + 1) / 2
		 * = (4 x^2 - 2 x + 1) * (4 x^2 - 2 x + 2) / 2
		 * = 8 x^4 - 8 x^3 + 8 x^2 - 3 x + 1
		 *
		 * A(-x, x) * (A(-x, x) + 1) / 2
		 * = (4 x^2 + 1) * (4 x^2 + 2) / 2
		 * = 8 x^4 + 6 x^2 + 1
		 *
		 */
		l = max(-x2, max(max(-y2, y1 + 1), 1)), r = min(-x1, -y1 - 1);
		if (l <= r)
			ans = (ans + (sum4_(l, r) * 8
						+ sum3_(l, r) * 8
						+ sum2_(l, r) * 8
						+ sum1_(l, r) * 3
						+ sum0_(l, r))) % MD;
		l = max(l, -y1), r = -x1;
		if (l <= r)
			ans = (ans + (sum4_(l, r) * 16
						+ sum3_(l, r) * 8
						- sum2_(l, r) * (y1 * 8 - 13) % MD
						- sum1_(l, r) * (y1 * 2 - 3) % MD
						+ sum0_(l, r) * (y1 - 1) % MD * (y1 - 2) % MD) % MD * INV2) % MD;
		l = max(-x2, max(max(-y2, y1 + 1), 1)), r = min(-x1, y2);
		if (l <= r)
			ans = (ans - (sum4_(l, r) * 8
						+ sum2_(l, r) * 6
						+ sum0_(l, r))) % MD;
		l = max(l, y2 + 1), r = -x1;
		if (l <= r)
			ans = (ans - (sum4_(l, r) * 16
						+ sum3_(l, r) * 8
						- sum2_(l, r) * ((y2 + 1) * 8 - 13) % MD
						- sum1_(l, r) * ((y2 + 1) * 2 - 3) % MD
						+ sum0_(l, r) * y2 % MD * (y2 - 1) % MD) % MD * INV2) % MD;
		/* y < 0, y < x <= -y
		 * A(x, y) = (2 y + 1)^2 - 6 y + x - y = 4 y^2 - 3 y + x + 1
		 * A(-y, y) = 4 y^2 - 4 y + 1
		 * A(y, y) = 4 y^2 - 2 y + 1
		 *
		 * A(x, y) (A(x, y) + 1) / 2
		 * = (4 y^2 - 3 y + x + 1)(4 y^2 - 3 y + x + 2) / 2
		 * = (16 y^4 - 24 y^3 + (8 x + 21) y^2 - (6 x + 9) y + (x + 1) (x + 2)) / 2
		 *
		 * A(-y, y) (A(-y, y) + 1) / 2
		 * = (4 y^2 - 4 y + 1) (4 y^2 - 4 y + 2) / 2
		 * = 8 y^4 - 16 y^3 + 14 y^2 - 6 y + 1
		 *
		 * A(y, y) (A(y, y) + 1) / 2
		 * = (4 y^2 - 2 y + 1) (4 y^2 - 2 y + 2) / 2
		 * = 8 y^4 - 8 y^3 + 8 y^2 - 3 y + 1
		 */
		l = max(-y2, max(max(x1, -x2 + 1), 1)), r = min(-y1, x2 - 1);
		if (l <= r)
			ans = (ans + (sum4_(l, r) * 8
						+ sum3_(l, r) * 16
						+ sum2_(l, r) * 14
						+ sum1_(l, r) * 6
						+ sum0_(l, r))) % MD;
		l = max(l, x2), r = -y1;
		if (l <= r)
			ans = (ans + (sum4_(l, r) * 16
						+ sum3_(l, r) * 24
						+ sum2_(l, r) * (x2 * 8 + 21) % MD
						+ sum1_(l, r) * (x2 * 6 + 9) % MD
						+ sum0_(l, r) * (x2 + 1) % MD * (x2 + 2) % MD) % MD * INV2) % MD;
		l = max(-y2, max(max(x1, -x2 + 1), 1)), r = min(-y1, -x1);
		if (l <= r)
			ans = (ans - (sum4_(l, r) * 8
						+ sum3_(l, r) * 8
						+ sum2_(l, r) * 8
						+ sum1_(l, r) * 3
						+ sum0_(l, r))) % MD;
		l = max(l, -x1 + 1), r = -y1;
		if (l <= r)
			ans = (ans - (sum4_(l, r) * 16
						+ sum3_(l, r) * 24
						+ sum2_(l, r) * ((x1 - 1) * 8 + 21) % MD
						+ sum1_(l, r) * ((x1 - 1) * 6 + 9) % MD
						+ sum0_(l, r) * x1 % MD * (x1 + 1) % MD) % MD * INV2) % MD;
		if (ans < 0)
			ans += MD;
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message (stderr)

spiral.c: In function 'main':
spiral.c:55:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
spiral.c:59:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |   scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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