제출 #114508

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
114508		atoiz	Spiral (BOI16_spiral)	C++14	27 / 100	1572 ms	384 KiB

spiral

/*input
19999 1
-100 -1000 1000 100
*/

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

using namespace std;

#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) ans = add(ans, sumLR(get(max(x1, -d + 1), -d), get(x2, -d))); 
	if (x1 == -d) ans = add(ans, sumLR(get(-d, min(y2, d - 1)), get(-d, y1)));
	if (y2 == d) ans = add(ans, sumLR(get(min(x2, d - 1), d), get(x1, d)));
	if (x2 == d) 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));
	return ans;	
}

signed main()
{
	int n, q; scanf("%lld %lld", &n, &q);
	while (q--) {
		int x1, x2, y1, y2; scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &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;

		ans = bruteForce(x1, x2, y1, y2);
		printf("%lld\n", ans);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

spiral.cpp: In function 'long long int get(long long int, long long int)':
spiral.cpp:45: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:45: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:46: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:46: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:47: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:47: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:103: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:105: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: 0 / 17
• Subtask 4: 0 / 31
• Subtask 5: 0 / 25