Submission #114511

#	Time	Username	Problem	Language	Result	Execution time	Memory
114511		atoiz	Spiral (BOI16_spiral)	C++14	100 / 100	7 ms	384 KiB

spiral

/*input
19999 1
-7 -5 8 -5
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cassert>
#include <cmath>
#include <random>
#include <chrono>

using namespace std;

uniform_int_distribution<int> rnd(0, 1e9 + 7);
mt19937 rng(chrono::system_clock().now().time_since_epoch().count());
int rd(int l, int r) { return l + rnd(rng) % (r - l + 1); }

#define int long long
#define abs abss
#define div divv
#define min minn
#define max maxx

const int MOD = 1000000007;

int add(int a, int b) { a = (a + b) % MOD; if (a < 0) a += MOD; return a; }
int sub(int a, int b) { a = (a - b) % MOD; if (a < 0) a += MOD; return a; }
int mul(int a, int b) { a = ((a % MOD) * (b % MOD)) % MOD; if (a < 0) a += MOD; return a; }
int sqr(int a) { return mul(a, a); }
int bpow(int a, int p) { int ans = 1; while (p) { if (p & 1) ans = mul(ans, a); p >>= 1; a = sqr(a); } return ans; }
int div(int a, int b) { return mul(a, bpow(b, MOD - 2)); }
int abs(int a) { return (a > 0 ? a : -a); }
int min(int a, int b) { return (a < b ? a : b); }
int max(int a, int b) { return (a > b ? a : b); }

#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORB(i, a, b) for (int i = a; i >= b; --i)

const int MAGIC = 6;

int sumLR(int l, int r) { return mul(mul(add(l, r), add(sub(r, l), 1)), (MOD + 1) / 2); }

int get(int x, int y)
{
	if (x == 0 && y == 0) return 1;
	int d = max(abs(x), abs(y)), ans = add(sqr(d * 2 - 1), d);

	if (x == d && y > -d && y <= d) return add(ans, y); ans = add(ans, d); ans = add(ans, d);
	if (y == d && x >= -d && x < d) return sub(ans, x); ans = add(ans, d); ans = add(ans, d);
	if (x == -d && y >= -d && y < d) return sub(ans, y); ans = add(ans, d); ans = add(ans, d);
	return add(ans, x);
}

int interpolate(vector<int> vec, int x)
{
	int ans = 0;
	FOR(i, 0, MAGIC - 1) {
		int cur = vec[i];
		FOR(j, 0, MAGIC - 1) if (j != i) {
			cur = mul(cur, div(sub(x, j), sub(i, j)));
		}
		ans = add(ans, cur);
	}

	return ans;
}

int get1(int x1, int x2, int y1, int y2, int d)
{
	if (x1 > d || x2 < -d || y1 > d || y2 < -d) return 0;
	if (d == 0) return 1;

	x1 = max(x1, -d); x2 = min(x2, d); y1 = max(y1, -d); y2 = min(y2, d); 

	int ans = 0;
	if (y1 == -d && max(x1, -d + 1) <= x2) ans = add(ans, sumLR(get(max(x1, -d + 1), -d), get(x2, -d))); 
	if (x1 == -d && min(y2, d - 1) >= y1) ans = add(ans, sumLR(get(-d, min(y2, d - 1)), get(-d, y1)));
	if (y2 == d && min(x2, d - 1) >= x1) ans = add(ans, sumLR(get(min(x2, d - 1), d), get(x1, d)));
	if (x2 == d && max(y1, -d + 1) <= y2) ans = add(ans, sumLR(get(d, max(y1, -d + 1)), get(d, y2)));
	return ans;
}

int getRect(int x1, int x2, int y1, int y2, int d1, int d2) // [d1, d2]
{
	int ans = 0;
	if (d2 - d1 <= MAGIC) {
		FOR(d, d1, d2) ans = add(ans, get1(x1, x2, y1, y2, d));
		return ans;
	}

	vector<int> vec(MAGIC);
	vec[0] = get1(x1, x2, y1, y2, d1);
	FOR(d, d1 + 1, d1 + MAGIC - 1) vec[d - d1] = add(vec[d - d1 - 1], get1(x1, x2, y1, y2, d));
	return interpolate(vec, d2 - d1);
}

int bruteForce(int x1, int x2, int y1, int y2)
{
	int ans = 0;
	FOR(x, x1, x2) FOR(y, y1, y2) ans = add(ans, get(x, y));
	// FOR(x, x1, x2) FOR(y, y1, y2) cout << get(x, y) << ' '; cout << endl;
	return ans;	
}

int solve(int x1, int x2, int y1, int y2)
{
	int ans = 0;
	vector<int> vec = {abs(x1), abs(x2), abs(y1), abs(y2)};
	sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end());
	for (int i : vec) ans = add(ans, get1(x1, x2, y1, y2, i));

	int prv = -1;
	for (int i : vec) ans = add(ans, getRect(x1, x2, y1, y2, prv + 1, i - 1)), prv = i;
	return ans;
}

signed main()
{
	// while (true) {
	// 	int x1 = rd(-10, 10), x2 = rd(-10, 10), y1 = rd(-10, 10), y2 = rd(-10, 10);
	// 	if (x1 > x2) swap(x1, x2);
	// 	if (y1 > y2) swap(y1, y2);
	// 	if (bruteForce(x1, x2, y1, y2) != solve(x1, x2, y1, y2)) {
	// 		cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
	// 		return 0;
	// 	}
	// }

	int n, q; scanf("%lld %lld", &n, &q);
	while (q--) {
		int x1, x2, y1, y2; scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
		// cout << get1(x1, x2, y1, y2, 5) << endl;
		// cout << bruteForce(x1, x2, y1, y2) << endl;
		printf("%lld\n", solve(x1, x2, y1, y2));
	}
}

Compilation message (stderr)

spiral.cpp: In function 'long long int get(long long int, long long int)':
spiral.cpp:51:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (x == d && y > -d && y <= d) return add(ans, y); ans = add(ans, d); ans = add(ans, d);
  ^~
spiral.cpp:51:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (x == d && y > -d && y <= d) return add(ans, y); ans = add(ans, d); ans = add(ans, d);
                                                      ^~~
spiral.cpp:52:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (y == d && x >= -d && x < d) return sub(ans, x); ans = add(ans, d); ans = add(ans, d);
  ^~
spiral.cpp:52:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (y == d && x >= -d && x < d) return sub(ans, x); ans = add(ans, d); ans = add(ans, d);
                                                      ^~~
spiral.cpp:53:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (x == -d && y >= -d && y < d) return sub(ans, y); ans = add(ans, d); ans = add(ans, d);
  ^~
spiral.cpp:53:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (x == -d && y >= -d && y < d) return sub(ans, y); ans = add(ans, d); ans = add(ans, d);
                                                       ^~~
spiral.cpp: In function 'int main()':
spiral.cpp:132:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, q; scanf("%lld %lld", &n, &q);
            ~~~~~^~~~~~~~~~~~~~~~~~~~~
spiral.cpp:134:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x1, x2, y1, y2; 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