QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#498768 | #1281. Longest Common Subsequence | qL | RE | 2ms | 16048kb | C++14 | 2.1kb | 2024-07-30 19:35:06 | 2024-07-30 19:35:14 |
Judging History
answer
#include <algorithm>
#include <cstdio>
using i32 = int;
constexpr i32 N = 1E6;
constexpr i32 inf32 = 0x3f3f3f3f;
i32 n, m, a[N + 1], b[N + 1];
i32 pa[N + 1], sa[N + 1], pb[N + 1], sb[N + 1], suma[N + 1], sumb[N + 1], ct[N * 2 + 1];
void upd(i32 x, i32 n, i32 v) noexcept {
for (; x <= n + m + 1; x += x & -x) ct[x] = std::max(ct[x], v);
}
i32 qry(i32 x) noexcept {
i32 r = -inf32;
for (; x; x ^= x & -x) r = std::max(r, ct[x]);
return r;
}
signed main() noexcept {
i32 Test;
for (scanf("%d", &Test); Test; --Test) {
scanf("%d%d", &n, &m);
for (i32 i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (i32 i = 1; i <= m; ++i) scanf("%d", &b[i]);
__builtin_memset(pa + 1, 0, sizeof(i32) * n);
__builtin_memset(sa + 1, 0, sizeof(i32) * n);
__builtin_memset(pb + 1, 0, sizeof(i32) * m);
__builtin_memset(sb + 1, 0, sizeof(i32) * m);
i32 tpa = 0, tpb = 0, tsa = 0, tsb = 0;
for (i32 i = 1; i <= n; ++i)
if (a[i] == 1) pa[++tpa] = i;
for (i32 i = 1; i <= m; ++i)
if (b[i] == 1) pb[++tpb] = i;
sa[0] = n + 1, sb[0] = m + 1;
for (i32 i = n; i; --i)
if (a[i] == 3) sa[++tsa] = i;
for (i32 i = m; i; --i)
if (b[i] == 3) sb[++tsb] = i;
for (i32 i = 1; i <= n; ++i) suma[i] = suma[i - 1] + (a[i] == 2);
for (i32 i = 1; i <= m; ++i) sumb[i] = sumb[i - 1] + (b[i] == 2);
i32 ans = -inf32;
__builtin_memset(ct + 1, 0xcf, sizeof(i32) * (n + m + 1));
for (i32 i = std::min(tsa, tsb), j = 0; ~i; --i) {
for (; j <= std::min(tpa, tpb) && pa[j] < sa[i] && pb[j] < sb[i]; ++j)
upd(suma[pa[j]] - sumb[pb[j]] + m + 1, tpb, j - sumb[pb[j]]);
ans = std::max(ans, i + sumb[sb[i] - 1] + qry(suma[sa[i] - 1] - sumb[sb[i] - 1] + m + 1));
}
__builtin_memset(ct + 1, 0xcf, sizeof(i32) * (n + m + 1));
for (i32 i = std::min(tsa, tsb), j = 0; ~i; --i) {
for (; j <= std::min(tpa, tpb) && pa[j] < sa[i] && pb[j] < sb[i]; ++j)
upd(sumb[pb[j]] - suma[pa[j]] + n + 1, tpb, j - sumb[pb[j]]);
ans = std::max(ans, i + suma[sa[i] - 1] + qry(sumb[sb[i] - 1] - suma[sa[i] - 1] + m + 1));
}
printf("%d\n", ans);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 16048kb
input:
3 3 3 1 2 3 1 2 3 3 3 1 1 1 1 1 2 3 3 1 3 2 1 2 3
output:
3 2 2
result:
ok 3 tokens
Test #2:
score: -100
Runtime Error
input:
139889 1 10 2 2 1 2 2 3 1 1 2 3 3 7 1 3 2 3 3 1 1 2 2 6 1 2 1 3 1 1 1 1 8 7 3 1 3 3 2 2 3 1 3 2 2 1 3 3 3 10 3 3 2 1 1 2 2 1 1 1 1 3 1 1 5 2 1 2 1 3 1 1 2 1 4 1 3 3 3 3 7 2 3 1 2 1 2 2 3 3 2 6 2 3 1 1 2 1 3 1 3 1 4 1 3 1 1 3 4 2 2 3 2 3 1 3 1 8 1 1 1 3 1 3 3 3 1 4 1 1 3 3 3 1 10 10 3 1 2 1 2 2 2 2 1...