QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#292415 | #7120. Soccer | nhuang685 | 0 | 455ms | 274784kb | C++20 | 6.4kb | 2023-12-28 04:27:55 | 2024-04-28 08:03:27 |
Judging History
answer
/**
* @file soccer.cpp
* @author n685
* @brief
* @date 2023-12-27
*
*
*/
#include "soccer.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgR(...) 4242
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
#endif
template <class Node> struct Seg {
using T = typename Node::T;
using RT = typename Node::RT;
int sz = 0;
std::vector<Node> val;
Seg() {}
Seg(int _sz) {
// sz = _sz;
if (_sz == 1) {
sz = 1;
} else {
sz = (1 << (std::__lg(_sz - 1) + 1));
}
val.resize(2 * sz);
}
Seg(const std::vector<T> &v) : Seg(static_cast<int>(v.size())) {
for (int i = 0; i < static_cast<int>(v.size()); ++i) {
val[i + sz] = v[i];
}
build(0, sz - 1);
}
void build(int l, int r) {
l += sz, r += sz;
l /= 2, r /= 2;
for (int k = 2; l >= 1; l /= 2, r /= 2, k *= 2) {
for (int i = l; i <= r; ++i) {
val[i].pull(val[2 * i], val[2 * i + 1]);
}
}
}
void upd(int ind, const std::function<void(Node &)> &f) {
f(val[ind += sz]);
for (ind /= 2; ind >= 1; ind /= 2) {
val[ind].pull(val[2 * ind], val[2 * ind + 1]);
}
}
void set(int ind, const T &v) {
upd(ind, [&v](Node &n) { n.set(v); });
}
void add(int ind, const T &v) {
upd(ind, [&v](Node &n) { n.add(v); });
}
RT query(int l, int r) {
RT ll = Node::ID, rr = Node::ID;
for (l += sz, r += sz; l <= r; l /= 2, r /= 2) {
if (l % 2 == 1) {
ll = Node::comb(val[l++], ll);
}
if (r % 2 == 0) {
rr = Node::comb(rr, val[r--]);
}
}
return Node::comb(ll, rr);
}
};
struct NodeMin {
using T = std::pair<int, int>;
using RT = T;
static constexpr RT ID = std::pair{(int)1e9, (int)1e9};
T val = ID;
NodeMin() {}
NodeMin(T v) : val(v) {}
operator RT() { return val; }
static RT comb(RT a, RT b) { return std::min(a, b); }
void set(T v) { val = v; }
void pull(NodeMin &ll, NodeMin &rr) { val = std::min(ll.val, rr.val); }
};
struct NodeMax {
using T = std::pair<int, int>;
using RT = T;
static constexpr RT ID = std::pair{-(int)1e9, -(int)1e9};
T val = ID;
NodeMax() {}
NodeMax(T v) : val(v) {}
operator RT() { return val; }
static RT comb(RT a, RT b) {
if (a.first >= b.first) {
return a;
} else {
return b;
}
}
void set(T v) { val = v; }
void pull(NodeMax &ll, NodeMax &rr) {
if (ll.val.first >= rr.val.first) {
val = ll.val;
} else {
val = rr.val;
}
}
};
struct Rect {
int tr;
int d;
int l, r;
int ii;
};
int biggest_stadium(int N, std::vector<std::vector<int>> F) {
auto n = N + 2;
std::vector<std::pair<int, int>> tr;
std::vector f(n, std::vector<int>(n, -1));
auto insT = [&](int i, int j) {
tr.emplace_back(i, j);
f[i][j] = (int)tr.size() - 1;
};
for (int i = 0; i <= N + 1; ++i) {
if (f[i][0] == -1) {
insT(i, 0);
}
if (f[i][N + 1] == -1) {
insT(i, N + 1);
}
}
for (int j = 0; j <= N + 1; ++j) {
if (f[0][j] == -1) {
insT(0, j);
}
if (f[N + 1][j] == -1) {
insT(N + 1, j);
}
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (F[i][j]) {
insT(i + 1, j + 1);
}
}
}
int m = (int)tr.size();
std::vector<Seg<NodeMin>> mr(n), md(n);
for (int i = n - 1; i >= 0; --i) {
if (i == n - 1) {
mr[i] = Seg<NodeMin>(n);
md[i] = Seg<NodeMin>(n);
} else {
mr[i] = mr[i + 1];
md[i] = md[i + 1];
}
for (int j = 0; j < n; ++j) {
if (f[j][i] >= 0) {
mr[i].set(j, std::pair{i, f[j][i]});
}
if (f[i][j] >= 0) {
md[i].set(j, std::pair{i, f[i][j]});
}
}
}
std::vector<Seg<NodeMax>> mu(n);
for (int i = 0; i < n; ++i) {
if (i == 0) {
mu[i] = Seg<NodeMax>(n);
} else {
mu[i] = mu[i - 1];
}
for (int j = 0; j < n; ++j) {
if (f[i][j] >= 0) {
mu[i].set(j, std::pair{i, f[i][j]});
}
}
}
std::vector<Rect> rt;
std::vector<std::vector<int>> id(m);
for (int t = 0; t < m; ++t) {
auto [a, b] = tr[t];
if (a == n - 1) {
continue;
}
int l = 0, r = n - 1;
while (l <= r && l <= b && b <= r) {
auto [$, ind] = md[a + 1].query(l, r);
if (ind == (int)1e9) {
break;
}
auto [i, j] = tr[ind];
if (i > a + 1) {
rt.push_back(Rect{t, i - 1, l, r, -1});
}
if (j <= b) {
l = j + 1;
} else {
r = j - 1;
}
}
}
std::sort(rt.begin(), rt.end(), [&](const auto &a, const auto &b) {
return a.r - a.l > b.r - b.l;
});
int k = (int)rt.size();
for (int i = 0; i < k; ++i) {
id[rt[i].tr].push_back(i);
rt[i].ii = (int)id[rt[i].tr].size() - 1;
}
auto added = [&](const Rect &orig, const Rect &nxt) {
auto [i1, d1, l1, r1, ii1] = orig;
auto [i2, d2, l2, r2, ii2] = nxt;
int u1 = tr[i1].first + 1;
int u2 = tr[i2].first + 1;
return (r2 - l2 + 1) * ((d2 - u2) - (d1 - u1));
};
std::vector<int> dp(k);
for (int i = 0; i < k; ++i) {
auto [ind, d, l, r, ii] = rt[i];
int u = tr[ind].first + 1;
dp[i] = (d - u + 1) * (r - l + 1);
}
int ans = 0;
for (int i = 0; i < k; ++i) {
ans = std::max(ans, dp[i]);
auto [ind, d, $, r, ii] = rt[i];
int u = tr[ind].first + 1;
int l = tr[ind].second + 1;
if (ii < (int)id[ind].size() - 1) {
Rect &r2 = rt[id[ind][ii + 1]];
dp[id[ind][ii + 1]] =
std::max(dp[id[ind][ii + 1]], dp[i] + added(rt[i], r2));
}
while (l <= r) {
auto [$$, i3] = mu[u].query(l, r + 1);
if (i3 < 0) {
break;
}
int rr = tr[i3].second - 1;
if (l > rr || rr > r) {
break;
}
auto [$$$, i2] = mu[u].query(l, rr);
l = rr + 2;
int i4 = (int)std::distance(
id[i2].begin(), std::lower_bound(id[i2].begin(), id[i2].end(), d,
[&](const int &a, const int &v) {
return rt[a].d < v;
}));
i4 = id[i2][i4];
dp[i4] = std::max(dp[i4], dp[i] + added(rt[i], rt[i4]));
}
}
return ans;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 6
Accepted
time: 1ms
memory: 3776kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 1 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 1
result:
ok ok
Test #2:
score: 6
Accepted
time: 0ms
memory: 4100kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 0 1 0 0 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 5
result:
ok ok
Test #3:
score: 1.5
Acceptable Answer
time: 2ms
memory: 4760kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 100 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 9847
result:
points 0.250 partial
Test #4:
score: 6
Accepted
time: 26ms
memory: 21168kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 500 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 236536
result:
ok ok
Test #5:
score: 6
Accepted
time: 455ms
memory: 274784kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 2000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 3786181
result:
ok ok
Test #6:
score: 6
Accepted
time: 1ms
memory: 3892kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 9 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 80
result:
ok ok
Test #7:
score: 0
Wrong Answer
time: 0ms
memory: 3768kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 10 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 90
result:
wrong answer wrong
Subtask #2:
score: 0
Wrong Answer
Test #10:
score: 8
Accepted
time: 0ms
memory: 3784kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 0 1 0 0 1 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 5
result:
ok ok
Test #11:
score: 8
Accepted
time: 0ms
memory: 4112kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 0 0 1 1 0 0 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 5
result:
ok ok
Test #12:
score: 2
Acceptable Answer
time: 0ms
memory: 3756kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 1 0 0 0 1 1 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 4
result:
points 0.250 partial
Test #13:
score: 8
Accepted
time: 0ms
memory: 3804kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 1 0 0 1 0 1 0 0 1
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 4
result:
ok ok
Test #14:
score: 2
Acceptable Answer
time: 0ms
memory: 3812kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 1 0 0 0 1 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 5
result:
points 0.250 partial
Test #15:
score: 0
Wrong Answer
time: 0ms
memory: 3840kb
input:
R0R7sb2atQWJ6SAWOjw4ZG7Gwgo5zl9L 3 0 0 1 0 0 1 0 0 0
output:
xlqtkQVzqzbOJxjzxlqsyVrlM2kqlbK0 OK 6
result:
wrong answer wrong
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%