제출 #1239413

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239413		kaiboy	Spiral (BOI16_spiral)	C++20	100 / 100	0 ms	328 KiB

spiral

#include <algorithm>
#include <iostream>

using namespace std;

const int MD = 1000000007;

long long sum(int n) { // sum of a for a in [1, n]
	return (long long) n * (n + 1) / 2 % MD;
}

long long sum2(int n) { // sum of a ^ 2 for a in [1, n]
	return (__int128_t) n * (n + 1) * (n * 2 + 1) / 6 % MD;
}

long long sum3(int n) { // sum of a ^ 3 for a in [1, n]
	long long s = sum(n);
	return s * s % MD;
}

int solve0(int x, int y) {
	if (x < 0 || y < 0)
		return 0;
	int z = min(x, y);
	// sum of ((w * 2 - 1) ^ 2 + w) * (w * 2 + 1) + (w * 2 + 1) * (w * 2) / 2 for w in [0, z]
	int ans = (sum3(z) * 8 + z + 1) % MD;
	if (x < y) {
		// sum of ((w * 2) * (w * 2 - 1) + w + 1) * (x + 1) - (x + 1) * x / 2 for w in (x, y]
		ans = (ans + ((sum2(y) - sum2(x)) * 4 - (sum(y) - sum(x)) + y - x) % MD * (x + 1) - sum(x) * (y - x)) % MD;
	} else {
		// sum of ((w * 2 - 1) ^ 2 + w) * (y + 1) + (y + 1) * y / 2 for w in (y, x]
		ans = (ans + ((sum2(x) - sum2(y)) * 4 - (sum(x) - sum(y)) * 3 + x - y) % MD * (y + 1) + sum(y) * (x - y)) % MD;
	}
	if (ans < 0)
		ans += MD;
	return ans;
}

int solve0(int xl, int xr, int yl, int yr) {
	return (((solve0(xr, yr) - solve0(xl - 1, yr) + MD) % MD - solve0(xr, yl - 1) + MD) % MD + solve0(xl - 1, yl - 1)) % MD;
}

int solve1(int x, int y) {
	if (x < 0 || y < 0)
		return 0;
	int z = min(x, y);
	// sum of ((w * 2) * (w * 2 - 1) + w + 1) * (w * 2 + 1) + (w * 2 + 1) * (w * 2) / 2 for w in [0, z]
	int ans = (sum3(z) * 8 + sum2(z) * 4 + sum(z) * 2 + z + 1) % MD;
	if (x < y) {
		// sum of ((w * 2) * (w * 2) + w + 1) * (x + 1) - (x + 1) * x / 2 for w in (x, y]
		ans = (ans + ((sum2(y) - sum2(x)) * 4 + sum(y) - sum(x) + y - x) % MD * (x + 1) - sum(x) * (y - x)) % MD;
	} else {
		// sum of ((w * 2) * (w * 2 - 1) + w + 1) * (y + 1) + (y + 1) * y / 2 for w in (y, x]
		ans = (ans + ((sum2(x) - sum2(y)) * 4 - (sum(x) - sum(y)) + x - y) % MD * (y + 1) + sum(y) * (x - y)) % MD;
	}
	if (ans < 0)
		ans += MD;
	return ans;
}

int solve1(int xl, int xr, int yl, int yr) {
	int xl_ = yl, xr_ = yr, yl_ = -xr, yr_ = -xl;
	xl = xl_, xr = xr_, yl = yl_, yr = yr_;
	return (((solve1(xr, yr) - solve1(xl - 1, yr) + MD) % MD - solve1(xr, yl - 1) + MD) % MD + solve1(xl - 1, yl - 1)) % MD;
}

int solve2(int x, int y) {
	if (x < 0 || y < 0)
		return 0;
	int z = min(x, y);
	// sum of ((w * 2) * (w * 2) + w + 1) * (w * 2 + 1) + (w * 2 + 1) * (w * 2) / 2 for w in [0, z]
	int ans = (sum3(z) * 8 + sum2(z) * 8 + sum(z) * 4 + z + 1) % MD;
	if (x < y) {
		// sum of ((w * 2) * (w * 2 + 1) + w + 1) * (x + 1) - (x + 1) * x / 2 for w in (x, y]
		ans = (ans + ((sum2(y) - sum2(x)) * 4 + (sum(y) - sum(x)) * 3 + y - x) % MD * (x + 1) - sum(x) * (y - x)) % MD;
	} else {
		// sum of ((w * 2) * (w * 2) + w + 1) * (y + 1) + (y + 1) * y / 2 for w in (y, x]
		ans = (ans + ((sum2(x) - sum2(y)) * 4 + sum(x) - sum(y) + x - y) % MD * (y + 1) + sum(y) * (x - y)) % MD;
	}
	if (ans < 0)
		ans += MD;
	return ans;
}

int solve2(int xl, int xr, int yl, int yr) {
	int xl_ = -xr, xr_ = -xl, yl_ = -yr, yr_ = -yl;
	xl = xl_, xr = xr_, yl = yl_, yr = yr_;
	return (((solve2(xr, yr) - solve2(xl - 1, yr) + MD) % MD - solve2(xr, yl - 1) + MD) % MD + solve2(xl - 1, yl - 1)) % MD;
}

int solve3(int x, int y) {
	if (x < 0 || y < 0)
		return 0;
	int z = min(x, y - 1);
	// sum of ((w * 2) * (w * 2 + 1) + w + 1) * ((w + 1) * 2) + ((w + 1) * 2) * ((w + 1) * 2 - 1) / 2 for w in [0, z]
	int ans = (sum3(z) * 8 + sum2(z) * 16 + sum(z) * 11 + (z + 1) * 3LL) % MD;
	if (x < y - 1) {
		// sum of ((w * 2 - 1) * (w * 2 - 1) + w) * (x + 1) - (x + 1) * x / 2 for w in (x + 1, y]
		ans = (ans + ((sum2(y) - sum2(x + 1)) * 4 - (sum(y) - sum(x + 1)) * 3 + y - (x + 1)) % MD * (x + 1) - sum(x) * (y - (x + 1))) % MD;
	} else {
		// sum of ((w * 2) * (w * 2 + 1) + w + 1) * (y + 1) + (y + 1) * y / 2 for w in (y - 1, x]
		ans = (ans + ((sum2(x) - sum2(y - 1)) * 4 + (sum(x) - sum(y - 1)) * 3 + x - (y - 1)) % MD * (y + 1) + sum(y) * (x - (y - 1))) % MD;
	}
	if (ans < 0)
		ans += MD;
	return ans;
}

int solve3(int xl, int xr, int yl, int yr) {
	int xl_ = -yr, xr_ = -yl, yl_ = xl, yr_ = xr;
	xl = xl_, xr = xr_, yl = yl_, yr = yr_;
	return (((solve3(xr, yr) - solve3(xl - 1, yr) + MD) % MD - solve3(xr, yl - 1) + MD) % MD + solve3(xl - 1, yl - 1)) % MD;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, q; cin >> n >> q;
	while (q--) {
		int xl, xr, yl, yr; cin >> xl >> yl >> xr >> yr;
		if (0 <= xl && 0 <= yl) {
			cout << solve0(xl, xr, yl, yr) << '\n';
			continue;
		}
		if (xr <= 0 && 0 <= yl) {
			cout << solve1(xl, xr, yl, yr) << '\n';
			continue;
		}
		if (xr <= 0 && yr <= 0) {
			cout << solve2(xl, xr, yl, yr) << '\n';
			continue;
		}
		if (0 <= xl && yr <= 0) {
			cout << solve3(xl, xr, yl, yr) << '\n';
			continue;
		}
		if (0 <= yl) {
			cout << (solve1(xl, 0, yl, yr) + solve0(1, xr, yl, yr)) % MD << '\n';
			continue;
		}
		if (xr <= 0) {
			cout << (solve2(xl, xr, yl, 0) + solve1(xl, xr, 1, yr)) % MD << '\n';
			continue;
		}
		if (yr <= 0) {
			cout << (solve2(xl, 0, yl, yr) + solve3(1, xr, yl, yr)) % MD << '\n';
			continue;
		}
		if (0 <= xl) {
			cout << (solve3(xl, xr, yl, 0) + solve0(xl, xr, 1, yr)) % MD << '\n';
			continue;
		}
		cout << (((solve0(0, xr, 0, yr) + solve1(xl, -1, 0, yr)) % MD + solve2(xl, -1, yl, -1)) % MD + solve3(0, xr, yl, -1)) % MD << '\n';
	}
	return 0;
}

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