QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#470819 | #1281. Longest Common Subsequence | zhouyuxuan3501 | WA | 40ms | 15864kb | C++14 | 1.7kb | 2024-07-10 16:35:19 | 2024-07-10 16:35:20 |
Judging History
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=0;i<=n+m+1;i++)T1.t[i]=T2.t[i]=0;
for(i=h;i>=0;i--)
{
while(j<=w&&c1[0][i]<c3[0][j]&&c1[1][i]<c3[1][j])
{
T1.Z(c2[0][c3[0][j]]-c2[1][c3[1][j]]+m+1,j+c2[0][c3[0][j]]);//m+1避免下标为负数
y=max(y,T1.C(m+1+c2[0][c1[0][i]]-c2[1][c1[1][i]])+i-c2[0][c1[0][i]]);
j++;
}
}
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]]);
y=max(y,T2.C(n+1+c2[1][c1[1][i]]-c2[0][c1[0][i]])+i-c2[1][c1[1][i]]);
j++;
}
}
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: 15864kb
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: 40ms
memory: 13776kb
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 1 3 4 3 1 1 3 2 1 2 1 3 1 1 1 3 1 1 2 3 1 1 3 0 2 1 2 2 1 3 1 1 2 3 1 2 4 4 2 2 0 1 1 2 4 2 1 1 1 2 3 1 2 1 1 5 2 4 0 1 2 3 2 2 2 1 3 1 3 1 2 1 2 1 4 2 2 0 1 1 3 2 3 2 2 0 0 2 3 1 2 0 4 0 4 1 1 3 1 1 0 1 1 1 1 3 2 2 2 3 3 3 1 1 2 3 2 0 0 3 3 2 3 ...
result:
wrong answer 28th words differ - expected: '2', found: '1'