QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#470898#1281. Longest Common Subsequencezhouyuxuan3501WA 39ms15872kbC++141.7kb2024-07-10 16:51:302024-07-10 16:51:30

Judging History

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

  • [2024-07-10 16:51:30]
  • 评测
  • 测评结果:WA
  • 用时:39ms
  • 内存:15872kb
  • [2024-07-10 16:51:30]
  • 提交

answer

#include<cstdio>
#include<algorithm>
using namespace std;
const int n_max=1e6+11;
struct BIT
{
	int t[n_max<<1],N;
	void Z(int x,int c)
	{
		for(;x<=N;x+=(-x&x))
			t[x]=max(t[x],c);
	}
	int C(int x)
	{
		int c=0;
		for(;x;x-=(-x&x))
			c=max(c,t[x]);
		return c;
	}
}T1,T2;
int Du()
{
	int k=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')
	{
		k=k*10+c-'0';
		c=getchar();
	}
	return k;
}
int n,m,A[n_max],B[n_max],c1[2][n_max],c2[2][n_max],c3[2][n_max],k1[2],k3[2],i,j,h,w,y,t;
void CN()
{
	n=Du();   m=Du();
	T1.N=T2.N=n+m+1;
	for(i=1;i<=n;i++)
	{
		A[i]=Du();
		if(A[i]==1)c1[0][++k1[0]]=i;
		c2[0][i]=c2[0][i-1]+(A[i]==2);
	}
	for(i=n;i>=1;i--)if(A[i]==3)c3[0][++k3[0]]=i;
	c2[0][n+1]=c2[0][n];   c3[0][0]=n+1;
	for(i=1;i<=m;i++)
	{
		B[i]=Du();
		if(B[i]==1)c1[1][++k1[1]]=i;
		c2[1][i]=c2[1][i-1]+(B[i]==2);
	}
	for(i=m;i>=1;i--)if(B[i]==3)c3[1][++k3[1]]=i;
	c2[1][m+1]=c2[1][m];   c3[1][0]=m+1;
	h=min(k1[0],k1[1]);   w=min(k3[0],k3[1]);
	for(i=1;i<=n+m+1;i++)T1.t[i]=T2.t[i]=0;
	j=0;
	for(i=h;i>=0;i--)
	{
		while(j<=w&&c1[0][i]<c3[0][j]&&c1[1][i]<c3[1][j])
		{//+m+1避免负数 
			T1.Z(c2[0][c3[0][j]]-c2[1][c3[1][j]]+m+1,j+c2[0][c3[0][j]]);
			j++;
			y=max(y,T1.C(c2[0][c1[0][i]]-c2[1][c1[1][i]]+m+1)+i-c2[0][c1[0][i]]);
		}
	}
	j=0;
	for(i=h;i>=0;i--)
	{
		while(j<=w&&c1[0][i]<c3[0][j]&&c1[1][i]<c3[1][j])
		{
			T2.Z(c2[1][c3[1][j]]-c2[0][c3[0][j]]+n+1,j+c2[1][c3[1][j]]);
			j++;
			y=max(y,T2.C(c2[1][c1[1][i]]-c2[0][c1[0][i]]+n+1)+i-c2[1][c1[1][i]]);
		}
	}
	printf("%d\n",y);
}
int main()
{
	t=Du();
	while(t--)
	{
		k1[0]=k1[1]=k3[0]=k3[1]=0;
		y=0;
		CN();
	}
	return 0;
}

詳細信息

Test #1:

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

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: 39ms
memory: 13788kb

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
1
4
2
2
0
1
2
1
1
1
1
6
1
0
1
2
2
3
4
4
1
1
1
0
2
2
3
4
4
1
1
3
2
1
2
1
3
1
1
1
3
1
1
2
3
1
1
3
1
2
1
2
2
1
3
1
1
2
3
1
2
4
4
2
2
1
1
1
2
4
2
2
1
1
2
3
1
2
2
1
5
2
4
2
1
2
3
2
5
2
1
3
1
3
1
2
1
2
2
4
3
2
0
1
1
3
2
3
2
2
0
0
2
3
1
2
0
4
1
4
1
1
3
1
1
0
1
1
1
1
3
2
2
2
3
3
3
1
2
2
3
2
1
1
3
3
2
3
...

result:

wrong answer 48th words differ - expected: '2', found: '1'