제출 #114508

#제출 시각아이디문제언어결과실행 시간메모리
114508atoizSpiral (BOI16_spiral)C++14
27 / 100
1572 ms384 KiB
/*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);
                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...