Submission #78788

#	Time	Username	Problem	Language	Result	Execution time	Memory
78788		scanhex	Spiral (BOI16_spiral)	C++17	100 / 100	2 ms	616 KiB

spiral

#include <bits/stdc++.h>

using namespace std;
using nagai = long long;
using ll = long long;

const nagai mod = 1e9 + 7;

nagai sumx(nagai x)
{
	return x * (x + 1) / 2 % mod;
}

nagai calc11(nagai x, nagai y, nagai i)
{
	nagai j = 4 * i * i % mod;
	return sumx(j + i - x) - sumx((j - i - y) - 1);
}

nagai md(nagai x)
{
	x %= mod;
	if (x < 0)
		x += mod;
	return x;
}

nagai mult(nagai a, nagai b)
{
	return (a * b) % mod;
}

nagai pw(nagai a, nagai b)
{
	nagai c = 1;
	while (b)
	{
		if (b & 1)
			c = mult(c, a);
		a = mult(a, a);
		b >>= 1;
	}
	return c;
}

nagai inv(nagai x)
{
	 return pw(x, mod - 2);
}

nagai add(nagai a, nagai b)
{
	a += b;
	return a >= mod ? a - mod : a;
}


nagai integrate(nagai n, nagai c0 = 0, nagai c1 = 0, nagai c2 = 0, nagai c3 = 0)
{
	static nagai inv30 = inv(30);
	static nagai inv6 = inv(6);
	static nagai inv2 = (mod + 1) / 2;
	static nagai inv4 = mult(inv2, inv2);
	nagai ans = mult(c3, mult(inv4, mult(n, mult(n, mult(n + 1, n + 1)))));
	ans = add(ans, mult(c2, mult(inv6, mult(n, mult(n + 1, 2 * n + 1)))));
	ans = add(ans, mult(c1, mult(inv2, mult(n, n + 1))));
	ans = add(ans, mult(c0, n));
	return ans;
}

nagai sum11(nagai x, nagai y, nagai i)
{
	nagai c3 = 16;
	nagai c2 = (8 * x + 8 * y + 8) % mod;
	nagai c1 = md(2 * x - 2 * y);
	nagai c0 = md(x * x + x - y * y - y);
	return integrate(i, c0, c1, c2, c3);
}

nagai sum11(nagai x, nagai y, nagai from, nagai to)
{
	nagai ans = sum11(x, y, to) - (from == 0 ? 0 : sum11(x, y, from - 1));
	if (ans < 0)
		ans += mod;
	return ans;
}

nagai sum21(nagai x, nagai i)
{
	nagai c0 = 0, c1 = md(-2 - 4 * x), c2 = md(16 * x), c3 = 32;
	return integrate(i, c0, c1, c2, c3);
}

nagai sum12(nagai y, nagai i)
{
	nagai c0 = 0, c1 = md(4 * y + 2), c2 = md(16 * y + 4 + 4 + 9 - 1), c3 = 32;
	return integrate(i, c0, c1, c2, c3);
}


nagai sum21(nagai x, nagai from, nagai to)
{
	return md(sum21(x, to) - sum21(x, from - 1));
}

nagai sum12(nagai y, nagai from, nagai to)
{
	return md(sum12(y, to) - sum12(y, from - 1));
}

nagai sum22(nagai i)
{
	nagai c0 = 0, c1 = 8, c2 = 0, c3 = 64;
	return integrate(i, c0, c1, c2, c3);
}

nagai sum22(nagai from, nagai to)
{
	return md(sum22(to) - sum22(from - 1));
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	auto get = [&](int x, int y)
	{
		if (x < -n || y < -n)
			return 0LL;
		nagai ans = mult(2, mult(x + n + 1, y + n + 1));
		// -i <= x < i, -i <= y < i
		int from = 0;
		int to = n;
		if (x < 0)
			from = max(from, -x);
		if (y < 0)
			from = max(from, -y);
		if (x >= 0)
			from = max(from, x + 1);
		if (y >= 0)
			from = max(from, y + 1);
		if (from <= to)
			ans = add(ans, sum11(x, y, from, to));
		to = n; // to = from - 1
		from = 0;
		if (x <= y)
		{
			// y >= i
			// x < i
			// -i <= x
			from = max(0, x + 1);
			to = y;
			from = max(from, -x);
			if (from <= to)
				ans = add(ans, sum21(x, from, to));
		}
		else
		{
			from = max(0, y + 1);
			to = x;
			from = max(from, -y);
			if (from <= to)
				ans = add(ans, sum12(y, from, to));
		}
		// y >= i
		// x >= i
		from = 0;
		to = min(x, y);
		if (from <= to)
			ans = add(ans, sum22(from, to));
		return ans;
	};
	auto transform = [&](int& x, int& y)
	{
		y = -y;
		swap(x, y);
	};
	while (q--)
	{
		 int x1, y1, x2, y2;
		 cin >> x1 >> y1 >> x2 >> y2;
		 transform(x1, y1);
		 transform(x2, y2);
		 if (x1 > x2)
			 swap(x1, x2);
		 if (y1 > y2)
			 swap(y1, y2);
		 --x1, --y1;
		 //cerr << get(x2, y2) << ' ' << get(x2, y1) << ' ' << get(x1, y2) << ' ' << get(x1, y1) << '\n';
		 nagai ans = get(x2, y2) - get(x2, y1) - get(x1, y2) + get(x1, y1);
		 ans = md(ans);
		 ans = mult(ans, (mod + 1) / 2);
		 cout << ans << '\n';
	}
	/*
	int n; 
	cin >> n;
	int x = n, y = n;
	vector<int> dx = {0, -1, 0, 1};
	vector<int> dy = {1, 0, -1, 0};
	int curd = 0;
	vector<vector<int>> board(2 * n + 1, vector<int>(2 * n + 1));
	int cur = 0;
	for (int i = 0; i < 4 * n + 1; ++i)
	{
		int len = i / 2 + 1;
		for (int j = 0; j < len; ++j)
		{
			board[x][y] = cur++;
			x += dx[curd];
			y += dy[curd];
		}
		++curd;
		curd %= 4;
	}
	cerr << sum11(0, 0, 1, 1) << '\n';
	cerr << sum11(0, 0, 2, 2) << '\n';
	cerr << sum11(0, 1, 2, 2) << '\n';
//	cerr << sum21(0, 2, 2) << '\n';
//	cerr << sum12(0, 1, 1) << '\n';
//	cerr << sum22(0, 2) << '\n';
	*/

	return 0;
}

Compilation message (stderr)

spiral.cpp: In function 'nagai integrate(nagai, nagai, nagai, nagai, nagai)':
spiral.cpp:60:15: warning: unused variable 'inv30' [-Wunused-variable]
  static nagai inv30 = inv(30);
               ^~~~~

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