QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#498779#1281. Longest Common SubsequenceqLWA 105ms16052kbC++141.9kb2024-07-30 19:43:512024-07-30 19:43:53

Judging History

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

  • [2024-07-30 19:43:53]
  • 评测
  • 测评结果:WA
  • 用时:105ms
  • 内存:16052kb
  • [2024-07-30 19:43:51]
  • 提交

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 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]);
		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, 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, j - sumb[pb[j]]);
			ans = std::max(ans, i + suma[sa[i] - 1] + qry(sumb[sb[i] - 1] - suma[sa[i] - 1] + n + 1));
		}
		printf("%d\n", ans);
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 16052kb

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
Wrong Answer
time: 105ms
memory: 14200kb

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:

1
1
2
4
2
2
0
1
2
1
1
1
1
6
1
0
1
2
2
3
4
5
2
1
1
0
2
3
5
5
5
1
1
3
2
1
2
1
3
4
2
1
3
1
1
2
3
2
1
4
1
4
2
2
2
1
3
1
1
5
3
1
2
4
5
2
2
1
1
1
1
4
3
2
1
1
2
3
1
2
1
1
5
2
3
2
1
4
3
2
5
2
1
3
2
3
3
2
1
2
2
4
2
2
0
1
1
3
2
3
2
2
0
0
2
3
2
2
0
5
1
4
1
1
3
1
1
0
1
1
1
1
3
3
2
2
3
3
3
1
2
2
3
2
1
1
3
3
2
3
...

result:

wrong answer 3rd words differ - expected: '1', found: '2'