| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 544727 |
2022-04-02T16:12:25 Z |
rainboy |
Spiral (BOI16_spiral) |
C |
|
1 ms |
288 KB |
#include <stdio.h>
#define MD 1000000007
#define INV2 500000004
#define INV4 250000002
#define INV6 166666668
#define INV30 233333335
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
long long sum0(long long n) {
return n;
}
long long sum1(long long n) {
return n * (n + 1) % MD * INV2 % MD;
}
long long sum2(long long n) {
return n * (n + 1) % MD * (n * 2 + 1) % MD * INV6 % MD;
}
long long sum3(long long n) {
return n * (n + 1) % MD * n % MD * (n + 1) % MD * INV4 % MD;
}
long long sum4(long long n) {
return n * (n + 1) % MD * (n * 2 + 1) % MD * ((n * n * 3 + n * 3 - 1) % MD) % MD * INV30 % MD;
}
long long sum0_(long long l, long long r) {
return (sum0(r) - sum0(l - 1)) % MD;
}
long long sum1_(long long l, long long r) {
return (sum1(r) - sum1(l - 1)) % MD;
}
long long sum2_(long long l, long long r) {
return (sum2(r) - sum2(l - 1)) % MD;
}
long long sum3_(long long l, long long r) {
return (sum3(r) - sum3(l - 1)) % MD;
}
long long sum4_(long long l, long long r) {
return (sum4(r) - sum4(l - 1)) % MD;
}
int main() {
int n, q;
scanf("%d%d", &n, &q);
while (q--) {
long long x1, x2, y1, y2, l, r, ans;
scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
ans = x1 <= 0 && 0 <= x2 && y1 <= 0 && 0 <= y2;
/* x > 0, -x < y <= x
* A(x, y) = (2 x - 1)^2 + y + x = 4 x^2 - 3 x + y + 1
* A(x, x) = 4 x^2 - 2 x + 1
* A(x, -x) = 4 x^2 - 4 x + 1
*
* A(x, y) (A(x, y) + 1) / 2
* = (4 x^2 - 3 x + y + 1)(4 x^2 - 3 x + y + 2) / 2
* = (16 x^4 - 24 x^3 + (8 y + 21) x^2 - (6 y + 9) x + (y + 1) (y + 2)) / 2
*
* A(x, x) (A(x, x) + 1) / 2
* = (4 x^2 - 2 x + 1) (4 x^2 - 2 x + 2) / 2
* = 8 x^4 - 8 x^3 + 8 x^2 - 3 x + 1
*
* A(x, -x) (A(x, -x) + 1) / 2
* = (4 x^2 - 4 x + 1) (4 x^2 - 4 x + 2) / 2
* = 8 x^4 - 16 x^3 + 14 x^2 - 6 x + 1
*/
l = max(x1, max(max(y1, -y2 + 1), 1)), r = min(x2, y2 - 1);
if (l <= r)
ans = (ans + (sum4_(l, r) * 8
- sum3_(l, r) * 8
+ sum2_(l, r) * 8
- sum1_(l, r) * 3
+ sum0_(l, r))) % MD;
l = max(l, y2), r = x2;
if (l <= r)
ans = (ans + (sum4_(l, r) * 16
- sum3_(l, r) * 24
+ sum2_(l, r) * (y2 * 8 + 21) % MD
- sum1_(l, r) * (y2 * 6 + 9) % MD
+ sum0_(l, r) * (y2 + 1) % MD * (y2 + 2) % MD) % MD * INV2) % MD;
l = max(x1, max(max(y1, -y2 + 1), 1)), r = min(x2, -y1);
if (l <= r)
ans = (ans - (sum4_(l, r) * 8
- sum3_(l, r) * 16
+ sum2_(l, r) * 14
- sum1_(l, r) * 6
+ sum0_(l, r))) % MD;
l = max(l, -y1 + 1), r = x2;
if (l <= r)
ans = (ans - (sum4_(l, r) * 16
- sum3_(l, r) * 24
+ sum2_(l, r) * ((y1 - 1) * 8 + 21) % MD
- sum1_(l, r) * ((y1 - 1) * 6 + 9) % MD
+ sum0_(l, r) * y1 % MD * (y1 + 1) % MD) % MD * INV2) % MD;
/* y > 0, y > x >= -y
* A(x, y) = (2 y - 1)^2 + 2 y + y - x = 4 y^2 - y - x + 1
* A(-y, y) = 4 y^2 + 1
* A(y, y) = 4 y^2 - 2 y + 1
*
* A(x, y) * (A(x, y) + 1) / 2
* = (4 y^2 - y - x + 1) * (4 y^2 - y - x + 2) / 2
* = (16 y^4 - 8 y^3 - (8x - 13) y^2 + (2 x - 3) y + (x - 1) (x - 2)) / 2
*
* A(-y, y) * (A(-y, y) + 1) / 2
* = (4 y^2 + 1) * (4 y^2 + 2) / 2
* = 8 y^4 + 6 y^2 + 1
*
* A(y, y) * (A(y, y) + 1) / 2
* = (4 y^2 - 2 y + 1) * (4 y^2 - 2 y + 2) / 2
* = 8 y^4 - 8 y^3 + 8 y^2 - 3 y + 1
*/
l = max(y1, max(max(-x2, x1 + 1), 1)), r = min(y2, -x1 - 1);
if (l <= r)
ans = (ans + (sum4_(l, r) * 8
+ sum2_(l, r) * 6
+ sum0_(l, r))) % MD;
l = max(l, -x1), r = y2;
if (l <= r)
ans = (ans + (sum4_(l, r) * 16
- sum3_(l, r) * 8
- sum2_(l, r) * (x1 * 8 - 13) % MD
+ sum1_(l, r) * (x1 * 2 - 3) % MD
+ sum0_(l, r) * (x1 - 1) % MD * (x1 - 2) % MD) % MD * INV2) % MD;
l = max(y1, max(max(-x2, x1 + 1), 1)), r = min(y2, x2);
if (l <= r)
ans = (ans - (sum4_(l, r) * 8
- sum3_(l, r) * 8
+ sum2_(l, r) * 8
- sum1_(l, r) * 3
+ sum0_(l, r))) % MD;
l = max(l, x2 + 1), r = y2;
if (l <= r)
ans = (ans - (sum4_(l, r) * 16
- sum3_(l, r) * 8
- sum2_(l, r) * ((x2 + 1) * 8 - 13) % MD
+ sum1_(l, r) * ((x2 + 1) * 2 - 3) % MD
+ sum0_(l, r) * x2 % MD * (x2 - 1) % MD) % MD * INV2) % MD;
/* x < 0, -x > y >= x
* A(x, y) = (2 x + 1)^2 - 4 x - x - y = 4 x^2 - x - y + 1
* A(x, x) = 4 x^2 - 2 x + 1
* A(x, -x) = 4 x^2 + 1
*
* A(x, y) * (A(x, y) + 1) / 2
* = (4 x^2 - x - y + 1) * (4 x^2 - x - y + 2) / 2
* = (16 x^4 - 8 x^3 - (8y - 13) x^2 + (2 y - 3) x + (y - 1) (y - 2)) / 2
*
* A(x, x) * (A(x, x) + 1) / 2
* = (4 x^2 - 2 x + 1) * (4 x^2 - 2 x + 2) / 2
* = 8 x^4 - 8 x^3 + 8 x^2 - 3 x + 1
*
* A(-x, x) * (A(-x, x) + 1) / 2
* = (4 x^2 + 1) * (4 x^2 + 2) / 2
* = 8 x^4 + 6 x^2 + 1
*
*/
l = max(-x2, max(max(-y2, y1 + 1), 1)), r = min(-x1, -y1 - 1);
if (l <= r)
ans = (ans + (sum4_(l, r) * 8
+ sum3_(l, r) * 8
+ sum2_(l, r) * 8
+ sum1_(l, r) * 3
+ sum0_(l, r))) % MD;
l = max(l, -y1), r = -x1;
if (l <= r)
ans = (ans + (sum4_(l, r) * 16
+ sum3_(l, r) * 8
- sum2_(l, r) * (y1 * 8 - 13) % MD
- sum1_(l, r) * (y1 * 2 - 3) % MD
+ sum0_(l, r) * (y1 - 1) % MD * (y1 - 2) % MD) % MD * INV2) % MD;
l = max(-x2, max(max(-y2, y1 + 1), 1)), r = min(-x1, y2);
if (l <= r)
ans = (ans - (sum4_(l, r) * 8
+ sum2_(l, r) * 6
+ sum0_(l, r))) % MD;
l = max(l, y2 + 1), r = -x1;
if (l <= r)
ans = (ans - (sum4_(l, r) * 16
+ sum3_(l, r) * 8
- sum2_(l, r) * ((y2 + 1) * 8 - 13) % MD
- sum1_(l, r) * ((y2 + 1) * 2 - 3) % MD
+ sum0_(l, r) * y2 % MD * (y2 - 1) % MD) % MD * INV2) % MD;
/* y < 0, y < x <= -y
* A(x, y) = (2 y + 1)^2 - 6 y + x - y = 4 y^2 - 3 y + x + 1
* A(-y, y) = 4 y^2 - 4 y + 1
* A(y, y) = 4 y^2 - 2 y + 1
*
* A(x, y) (A(x, y) + 1) / 2
* = (4 y^2 - 3 y + x + 1)(4 y^2 - 3 y + x + 2) / 2
* = (16 y^4 - 24 y^3 + (8 x + 21) y^2 - (6 x + 9) y + (x + 1) (x + 2)) / 2
*
* A(-y, y) (A(-y, y) + 1) / 2
* = (4 y^2 - 4 y + 1) (4 y^2 - 4 y + 2) / 2
* = 8 y^4 - 16 y^3 + 14 y^2 - 6 y + 1
*
* A(y, y) (A(y, y) + 1) / 2
* = (4 y^2 - 2 y + 1) (4 y^2 - 2 y + 2) / 2
* = 8 y^4 - 8 y^3 + 8 y^2 - 3 y + 1
*/
l = max(-y2, max(max(x1, -x2 + 1), 1)), r = min(-y1, x2 - 1);
if (l <= r)
ans = (ans + (sum4_(l, r) * 8
+ sum3_(l, r) * 16
+ sum2_(l, r) * 14
+ sum1_(l, r) * 6
+ sum0_(l, r))) % MD;
l = max(l, x2), r = -y1;
if (l <= r)
ans = (ans + (sum4_(l, r) * 16
+ sum3_(l, r) * 24
+ sum2_(l, r) * (x2 * 8 + 21) % MD
+ sum1_(l, r) * (x2 * 6 + 9) % MD
+ sum0_(l, r) * (x2 + 1) % MD * (x2 + 2) % MD) % MD * INV2) % MD;
l = max(-y2, max(max(x1, -x2 + 1), 1)), r = min(-y1, -x1);
if (l <= r)
ans = (ans - (sum4_(l, r) * 8
+ sum3_(l, r) * 8
+ sum2_(l, r) * 8
+ sum1_(l, r) * 3
+ sum0_(l, r))) % MD;
l = max(l, -x1 + 1), r = -y1;
if (l <= r)
ans = (ans - (sum4_(l, r) * 16
+ sum3_(l, r) * 24
+ sum2_(l, r) * ((x1 - 1) * 8 + 21) % MD
+ sum1_(l, r) * ((x1 - 1) * 6 + 9) % MD
+ sum0_(l, r) * x1 % MD * (x1 + 1) % MD) % MD * INV2) % MD;
if (ans < 0)
ans += MD;
printf("%lld\n", ans);
}
return 0;
}
Compilation message
spiral.c: In function 'main':
spiral.c:55:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | scanf("%d%d", &n, &q);
| ^~~~~~~~~~~~~~~~~~~~~
spiral.c:59:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
288 KB |
Output is correct |
