/*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);
}
}
Compilation message
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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1122 ms |
356 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
256 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1122 ms |
356 KB |
Output is correct |
| 2 |
Execution timed out |
1571 ms |
384 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1572 ms |
256 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1122 ms |
356 KB |
Output is correct |
| 2 |
Correct |
3 ms |
256 KB |
Output is correct |
| 3 |
Execution timed out |
1571 ms |
384 KB |
Time limit exceeded |
