Submission #257003

#	Time	Username	Problem	Language	Result	Execution time	Memory
257003		Berted	Spiral (BOI16_spiral)	C++14	100 / 100	1 ms	384 KiB

spiral

#include <iostream>
#include <assert.h>
#define ll long long
#define int ll
using namespace std;

const ll MD = 1e9 + 7;

ll pw(ll b, ll e)
{
	e = (e + MD - 1) % (MD - 1);
	ll t = 1;
	while (e)
	{
		if (e & 1) {t = (t * b) % MD;}
		b = (b * b) % MD; e >>= 1;
	}
	return t;
}

ll trs[5][4] = 
{
	{0, 0, 0, 0},
	{1, pw(2, -1), pw(6, -1), 0},
	{0, pw(2, -1), pw(2, -1), pw(4, -1)},
	{0, 0, pw(3, -1), pw(2, -1)},
	{0, 0, 0, pw(4, -1)}
};

struct poly
{
	ll c[5] = {};
	poly() {}
	poly(int x) {c[0] = (MD + x) % MD;}
	poly(int x, int y, int z) {c[2] = (MD + x) % MD; c[1] = (MD + y) % MD; c[0] = (MD + z) % MD;}
};

poly operator+(const poly &a, const poly &b)
{
	poly ret;
	for (int i = 0; i < 5; i++)
	{
		ret.c[i] = (a.c[i] + b.c[i]) % MD;
	}
	return ret;
}

poly operator-(const poly &a, const poly &b)
{
	poly ret;
	for (int i = 0; i < 5; i++)
	{
		ret.c[i] = (a.c[i] + MD - b.c[i]) % MD;
	}
	return ret;
}

poly operator*(const poly &a, const poly &b)
{
	poly ret;
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			if (i + j < 5) {ret.c[i + j] = (ret.c[i + j] + a.c[i] * b.c[j] % MD) % MD;}
		}
	}
	return ret;
}

poly raisePoly(const poly &a)
{
	poly ret;
	for (int i = 1; i < 5; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			ret.c[i] = (ret.c[i] + trs[i][j] * a.c[j] % MD) % MD;
		}
	}
	return ret;
}

ll evalPoly(const poly &p, ll x)
{
	ll ret = 0, k = 1;
	for (int i = 0; i < 5; i++)
	{
		ret = (ret + p.c[i] * k % MD) % MD;
		k = (k * x) % MD;
	}
	return ret;
}

inline ll UR(int x, int y)
{
	poly a = poly(4, -9, 6) * poly(4, -9, 7) * poly(pw(2, -1));
	poly b = poly(4, -11, 7) * poly(4, -11, 8) * poly(pw(2, -1));
	poly r = raisePoly(a - b);
	ll ret = evalPoly(r, min(x, y) + 1);
	if (x < y)
	{
		b = poly(4, -9, 6 - x) * poly(4, -9, 5 - x) * poly(pw(2, -1));
		r = raisePoly(a - b);
		ret += evalPoly(r, y + 1) - evalPoly(r, x + 1);
	}
	else
	{
		a = poly(4, -11, 8 + y) * poly(4, -11, 9 + y) * poly(pw(2, -1));
		r = raisePoly(a - b);
		ret += evalPoly(r, x + 1) - evalPoly(r, y + 1);
	}
	ret = (ret % MD + MD) % MD;
	return ret;
}

inline ll UL(int x, int y)
{
	x = -x;
	poly a = poly(4, -7, 4) * poly(4, -7, 5) * poly(pw(2, -1));
	poly b = poly(4, -9, 5) * poly(4, -9, 6) * poly(pw(2, -1));
	poly r = raisePoly(a - b);
	ll ret = evalPoly(r, min(x, y) + 1);
	if (x < y)
	{
		a = poly(4, -9, x + 6) * poly(4, -9, x + 7) * poly(pw(2, -1));
		r = raisePoly(a - b);
		ret += evalPoly(r, y + 1) - evalPoly(r, x + 1);
	}
	else
	{
		b = poly(4, -7, 4 - y) * poly(4, -7, 3 - y) * poly(pw(2, -1));
		r = raisePoly(a - b);
		ret += evalPoly(r, x + 1) - evalPoly(r, y + 1);
	}
	a = raisePoly(poly(4, -9, 6));
	ret -= evalPoly(a, y + 1);
	ret = (ret % MD + MD) % MD;
	return ret;
}

inline ll DL(int x, int y)
{
	x = -x; y = -y;
	poly a = poly(4, -5, 2) * poly(4, -5, 3) * poly(pw(2, -1));
	poly b = poly(4, -7, 4) * poly(4, -7, 3) * poly(pw(2, -1));
	poly r = raisePoly(a - b);
	ll ret = evalPoly(r, min(x, y) + 1);
	if (x < y)
	{
		b = poly(4, -5, 2 - x) * poly(4, -5, 1 - x) * poly(pw(2, -1));
		r = raisePoly(a - b);
		ret += evalPoly(r, y + 1) - evalPoly(r, x + 1);
	}
	else
	{
		a = poly(4, -7, 4 + y) * poly(4, -7, 5 + y) * poly(pw(2, -1));
		r = raisePoly(a - b);
		ret += evalPoly(r, x + 1) - evalPoly(r, y + 1);
	}
	a = raisePoly(poly(4, -7, 4));
	ret -= evalPoly(a, x + 1);
	ret = (ret % MD + MD) % MD;
	return ret;
}

inline ll DR(int x, int y)
{
	y = -y;
	ll ret = 0;
	poly a = raisePoly(poly(4, 3, 2)), b, r;
	ret = evalPoly(a, y); x--;
	if (x)
	{
		a = poly(4, 5, 1) * poly(4, 5, 2) * poly(pw(2, -1));
		b = poly(4, 3, 3) * poly(4, 3, 2) * poly(pw(2, -1));
		r = raisePoly(a - b);
		ret += evalPoly(r, min(x, y));
		if (x < y)
		{
			a = poly(4, 3, 3 + x) * poly(4, 3, 2 + x) * poly(pw(2, -1));
			r = raisePoly(a - b);
			ret += evalPoly(r, y) - evalPoly(r, x);
		}
		else
		{
			b = poly(4, 5, 2 - y) * poly(4, 5, 1 - y) * poly(pw(2, -1));
			r = raisePoly(a - b);
			ret += evalPoly(r, x) - evalPoly(r, y);
		}
	}
	ret = (ret % MD + MD) % MD;
	return ret;
}

int32_t main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, q; cin >> n >> q;
	for (int i = 0; i < q; i++)
	{
		int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
		ll res = 0;
		int px1 = max(x1, 0LL), px2 = x2;
		int py1 = max(y1, 0LL), py2 = y2;
		
		if (px1 <= px2 && py1 <= py2)
		{
			//cout << "UR " << px1 << " " << py1 << " " << px2 << " " << py2 << "\n";
			res += UR(px2, py2);
			if (px1) {res -= UR(px1 - 1, py2);}
			if (py1) {res -= UR(px2, py1 - 1);}
			if (px1 && py1) {res += UR(px1 - 1, py1 - 1);}
			//cout << res << "\n";
		}

		px1 = x1; px2 = min(-1LL, x2);
		py1 = max(0LL, y1); py2 = y2;
		if (px1 <= px2 && py1 <= py2)
		{
			//cout << "UL " << px1 << " " << py1 << " " << px2 << " " << py2 << "\n";
			res += UL(px1, py2);
			if (py1) {res -= UL(px1, py1 - 1);}
			if (px2 < -1) {res -= UL(px2 + 1, py2);}
			if (py1 && px2 < -1) {res += UL(px2 + 1, py1 - 1);}
			//cout << res << "\n";
		}

		px1 = x1; px2 = min(0LL, x2);
		py1 = y1; py2 = min(-1LL, y2);
		if (px1 <= px2 && py1 <= py2)
		{
			//cout << "DL " << px1 << " " << py1 << " " << px2 << " " << py2 << "\n";
			res += DL(px1, py1);
			if (py2 < -1) {res -= DL(px1, py2 + 1);}
			if (px2 < 0) {res -= DL(px2 + 1, py1);}
			if (py2 < -1 && px2 < 0) {res += DL(px2 + 1, py2 + 1);}
			//cout << res << "\n";
		}

		px1 = max(1LL, x1); px2 = x2;
		py1 = y1; py2 = min(-1LL, y2);
		if (px1 <= px2 && py1 <= py2)
		{
			//cout << "DR " << px1 << " " << py1 << " " << px2 << " " << py2 << "\n";
			res += DR(px2, py1);
			if (py2 < -1) {res -= DR(px2, py2 + 1);}
			if (px1 > 1) {res -= DR(px1 - 1, py1);}
			if (py2 < -1 && px1 > 1) {res += DR(px1 - 1, py2 + 1);}
			//cout << res << "\n";
		}

		cout << (res % MD + MD) % MD << "\n";
	}
	return 0;
}

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