QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#498768#1281. Longest Common SubsequenceqLRE 2ms16048kbC++142.1kb2024-07-30 19:35:062024-07-30 19:35:14

Judging History

你现在查看的是最新测评结果

  • [2024-07-30 19:35:14]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:16048kb
  • [2024-07-30 19:35:06]
  • 提交

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...

output:


result: