QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#472246 | #1281. Longest Common Subsequence | lichenyu_ac | WA | 122ms | 18224kb | C++14 | 1.6kb | 2024-07-11 15:14:57 | 2024-07-11 15:14:57 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int n,m,a[N],b[N],top;
int lA[N],rA[N],sumA[N];
int lB[N],rB[N],sumB[N];
int t1[N],t2[N];
void add1(int x,int k){
for(int i=x+n+m+1;i<=(n+m)*3+1;i+=i&-i){
t1[i]=max(t1[i],k);
}
}
void add2(int x,int k){
for(int i=x+n+m+1;i;i-=i&-i){
t2[i]=max(t2[i],k);
}
}
int ask1(int x){
int ret=-1e9;
for(int i=x+n+m+1;i>=1;i-=i&-i){
ret=max(ret,t1[i]);
}
return ret;
}
int ask2(int x){
int ret=-1e9;
for(int i=x+n+m+1;i<=(n+m)*3+1;i+=i&-i){
ret=max(ret,t2[i]);
}
return ret;
}
void solve(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=m;i++)scanf("%d",&b[i]);
for(int i=-n-m;i<=(n+m)*2;i++)
t1[i+n+m+1]=t2[i+n+m+1]=-1e9;
rA[0]=n+1,rB[0]=m+1;
for(int i=1;i<=n;i++)lA[i]=n+1,rA[i]=0;
for(int i=1;i<=m;i++)lB[i]=m+1,rB[i]=0;
top=0;
for(int i=1;i<=n;i++)
if(a[i]==1)lA[++top]=i;
top=0;
for(int i=n;i>=1;i--)
if(a[i]==3)rA[++top]=i;
for(int i=1;i<=n;i++)
sumA[i]=sumA[i-1]+(a[i]==2);
top=0;
for(int i=1;i<=m;i++)
if(b[i]==1)lB[++top]=i;
top=0;
for(int i=m;i>=1;i--)
if(b[i]==3)rB[++top]=i;
for(int i=1;i<=m;i++)
sumB[i]=sumB[i-1]+(b[i]==2);
int ans=0;
for(int i=min(n,m),j=0;i>=0;i--){
while(j<=min(n,m)&&lA[i]<rA[j]&&lB[i]<rB[j]){
add1(sumA[rA[j]-1]-sumB[rB[j]-1],j+sumA[rA[j]-1]);
add2(sumA[rA[j]-1]-sumB[rB[j]-1],j+sumB[rB[j]-1]);
j++;
}
ans=max({ans,ask1(sumA[rA[i]]-sumB[rB[i]])+i-sumA[lA[i]],ask2(sumA[lA[i]]-sumB[lB[i]])+i-sumB[lB[i]]});
}
printf("%d\n",ans);
}
int main(){
int T;scanf("%d",&T);
while(T--)solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 18224kb
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: 122ms
memory: 18208kb
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 4 3 1 1 1 1 7 1 0 1 2 2 1 4 4 1 1 1 1 2 2 4 4 3 3 3 3 4 1 2 1 3 1 1 1 3 1 1 5 4 4 1 4 1 5 1 4 2 1 3 1 1 2 4 1 4 4 4 3 2 1 2 2 2 4 3 2 2 1 2 4 1 3 2 2 6 2 4 2 1 3 4 2 5 2 1 5 1 3 1 2 1 2 2 4 3 2 0 2 1 5 2 3 3 2 0 0 3 3 1 2 0 6 0 4 1 1 4 2 1 0 1 1 2 1 3 2 2 2 3 3 3 1 2 3 3 2 1 1 3 4 2 3 ...
result:
wrong answer 8th words differ - expected: '1', found: '4'