| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 114511 |
2019-06-01T14:11:12 Z |
atoiz |
Spiral (BOI16_spiral) |
C++14 |
|
7 ms |
384 KB |
/*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
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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
384 KB |
Output is correct |
| 2 |
Correct |
6 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
256 KB |
Output is correct |
| 3 |
Correct |
6 ms |
256 KB |
Output is correct |
| 4 |
Correct |
3 ms |
256 KB |
Output is correct |
| 5 |
Correct |
6 ms |
384 KB |
Output is correct |
