QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#91297 | #5818. Macaron | skittles1412 | 100 ✓ | 61ms | 9732kb | C++17 | 3.9kb | 2023-03-28 11:36:25 | 2023-03-28 11:36:28 |
Judging History
answer
#include "bits/extc++.h"
using namespace std;
template <typename T>
void dbgh(const T& t) {
cerr << t << endl;
}
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t << " | ";
dbgh(u...);
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
<< ": "; \
dbgh(__VA_ARGS__)
#else
#define cerr \
if (false) \
cerr
#define dbg(...)
#endif
using ld = long double;
#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))
constexpr int DIRS[4][2] {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
long sq(long x) {
return x * x;
}
struct DS1 {
vector<int> v;
DS1(int n) : v(n + 1) {}
void update(int l, int r, int x) {
v[l] += x;
v[r + 1] -= x;
}
vector<int> query() const {
vector<int> ans(sz(v));
partial_sum(begin(v), end(v), ans.begin());
ans.pop_back();
return ans;
}
};
template <typename T>
T reversed(T t) {
reverse(begin(t), end(t));
return t;
}
vector<vector<bool>> solve(const vector<vector<bool>>& arr, int r) {
int n = sz(arr), m = sz(arr[0]), cols[m];
memset(cols, -1, sizeof(cols));
vector<vector<bool>> ans(n, vector<bool>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j]) {
cols[j] = i;
}
}
DS1 ds(m);
for (int j = 0; j < m; j++) {
int y = cols[j];
if (y == -1) {
continue;
}
long s = r - sq(y - i);
if (s < 0) {
continue;
}
ld ql = j - sqrtl(s), qr = j + sqrtl(s);
int cl = int(floor(ql) + 1), cr = int(ceil(qr) - 1);
cl = max(0, cl);
cr = min(m - 1, cr);
if (cl <= cr) {
ds.update(cl, cr, 1);
}
}
auto cans = ds.query();
for (int j = 0; j < m; j++) {
ans[i][j] = !!cans[j];
}
}
return ans;
}
void solve() {
int n, m, r, sx, sy, kv;
cin >> n >> m >> r >> sx >> sy >> kv;
auto ibs = [&](int x, int y) -> bool {
return 0 <= x && x <= n + 1 && 0 <= y && y <= m + 1;
};
vector<vector<bool>> iarr(n + 2, vector<bool>(m + 2));
for (int i = 0; i < kv; i++) {
int x, y;
cin >> x >> y;
iarr[x][y] = true;
}
auto arr1 = solve(iarr, r), arr2 = reversed(solve(reversed(iarr), r));
vector<vector<bool>> arr(n + 2, vector<bool>(m + 2, true));
for (int i = 0; i <= n + 1; i++) {
for (int j = 0; j <= m + 1; j++) {
bool cans = true;
cans &= !arr1[i][j];
cans &= !arr2[i][j];
cans &= sq(i) >= r && sq(n + 1 - i) >= r && sq(j) >= r && sq(m + 1 - j) >= r;
arr[i][j] = cans;
}
}
if (!arr[sx][sy]) {
cout << 0 << endl;
return;
}
vector<vector<bool>> vis(n + 2, vector<bool>(m + 2));
vector<pair<int, int>> q;
auto push = [&](int x, int y) -> void {
if (vis[x][y]) {
return;
}
vis[x][y] = true;
q.emplace_back(x, y);
};
push(sx, sy);
while (sz(q)) {
auto [x, y] = q.back();
q.pop_back();
for (auto& [dx, dy] : DIRS) {
int cx = x + dx, cy = y + dy;
if (ibs(cx, cy) && arr[cx][cy]) {
push(cx, cy);
}
}
}
int ans = 0;
for (auto& a : vis) {
for (auto&& b : a) {
ans += b;
}
}
cout << ans << endl;
}
int main() {
cin.tie(nullptr);
cin.exceptions(ios::failbit);
ios_base::sync_with_stdio(false);
solve();
}
詳細信息
Test #1:
score: 10
Accepted
time: 2ms
memory: 3484kb
input:
11 11 5 9 7 4 1 10 1 11 8 3 8 4
output:
37
result:
ok single line: '37'
Test #2:
score: 10
Accepted
time: 17ms
memory: 6032kb
input:
999 999 3000 340 211 25 230 432 513 610 514 610 360 56 360 55 474 319 474 318 687 476 687 477 204 142 205 142 206 142 207 142 244 511 243 511 242 511 241 511 32 652 32 653 32 654 32 655 197 976 539 579 540 579 540 578
output:
724629
result:
ok single line: '724629'
Test #3:
score: 10
Accepted
time: 21ms
memory: 9184kb
input:
1000 1000 5000 748 173 24 944 654 943 654 944 653 942 654 941 654 941 655 942 655 940 655 939 655 938 655 939 656 938 656 635 128 636 128 634 128 635 127 637 128 633 128 632 128 633 127 631 128 630 128 629 128 628 128
output:
716645
result:
ok single line: '716645'
Test #4:
score: 10
Accepted
time: 14ms
memory: 4436kb
input:
1000 1000 10000 668 126 30 9 589 39 505 165 527 185 25 211 383 231 699 235 849 291 839 317 955 319 627 355 79 355 117 365 521 447 253 473 721 515 161 517 157 587 465 627 849 641 515 729 893 775 81 783 583 813 1 839 699 869 215 931 365 937 975 941 47 965 249
output:
192418
result:
ok single line: '192418'
Test #5:
score: 10
Accepted
time: 2ms
memory: 3524kb
input:
50 50 30 36 40 11 50 41 29 16 31 23 48 9 27 22 8 33 9 33 1 40 3 39 27 21 29 30
output:
1200
result:
ok single line: '1200'
Test #6:
score: 10
Accepted
time: 2ms
memory: 3496kb
input:
100 100 300 69 24 17 32 34 33 34 31 34 40 55 32 10 98 77 97 77 96 77 81 71 19 69 87 66 88 66 88 67 100 38 100 37 19 89 13 48
output:
1730
result:
ok single line: '1730'
Test #7:
score: 10
Accepted
time: 20ms
memory: 6004kb
input:
1000 1000 5000 845 228 41 13 132 12 132 13 133 13 131 11 132 12 133 14 131 11 131 908 888 907 888 401 736 350 495 350 494 349 494 348 494 349 493 348 495 350 493 347 495 348 496 351 493 349 496 348 497 351 492 351 491 859 937 295 732 295 733 151 720 152 720 151 721 152 721 151 722 37 291 675 123 676...
output:
646861
result:
ok single line: '646861'
Test #8:
score: 10
Accepted
time: 24ms
memory: 9732kb
input:
1000 1000 10000 845 168 7949 901 901 901 902 901 903 901 904 901 905 901 906 901 909 901 911 901 912 901 913 901 914 901 915 901 916 901 917 901 918 901 919 901 920 901 921 901 923 901 924 901 925 901 926 901 927 901 928 901 930 901 935 901 936 901 938 901 939 901 940 901 942 901 943 901 945 901 946...
output:
635255
result:
ok single line: '635255'
Test #9:
score: 10
Accepted
time: 61ms
memory: 6104kb
input:
1000 1000 1 19 587 249999 1 1 1 3 1 5 1 7 1 9 1 11 1 13 1 15 1 17 1 19 1 21 1 23 1 25 1 27 1 29 1 31 1 33 1 35 1 37 1 39 1 41 1 43 1 45 1 47 1 49 1 51 1 53 1 55 1 57 1 59 1 61 1 63 1 65 1 67 1 69 1 71 1 73 1 75 1 77 1 79 1 81 1 83 1 85 1 87 1 89 1 91 1 93 1 95 1 97 1 99 1 101 1 103 1 105 1 107 1 109...
output:
750001
result:
ok single line: '750001'
Test #10:
score: 10
Accepted
time: 12ms
memory: 4568kb
input:
1000 1000 111012 587 619 0
output:
111556
result:
ok single line: '111556'
Extra Test:
score: 0
Extra Test Passed