QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#518280 | #1281. Longest Common Subsequence | cqzhm | WA | 80ms | 20092kb | C++20 | 1.6kb | 2024-08-13 19:06:47 | 2024-08-13 19:06:47 |
Judging History
answer
#include<bits/stdc++.h>
#define inf 1e9
using namespace std;
const int MAXN=1e6+10;
int n,m,a[MAXN],b[MAXN],maxn;
struct BIT{
int tree[MAXN<<1];
inline int lowbit(int x){return x&(-x);}
inline void update(int x,int val){for(;x<=maxn*2;x+=lowbit(x)) tree[x]=max(tree[x],val);}
inline int query(int x){int ans=0; for(;x;x-=lowbit(x)) ans=max(ans,tree[x]); return ans;}
}f1,f2;
int la[MAXN],ra[MAXN],s1[MAXN];
int lb[MAXN],rb[MAXN],s2[MAXN];
int cnta1,cnta3,cntb1,cntb3;
inline void solve(){
cnta1=cnta3=cntb1=cntb3=0;
cin>>n>>m; maxn=max(n,m);
for(int i=1;i<=n;i++) cin>>a[i],la[i]=0;
for(int i=1;i<=m;i++) cin>>b[i],lb[i]=0;
for(int i=1;i<=n;i++){
if(a[i]==1) la[++cnta1]=i;
s1[i]=s1[i-1]+(a[i]==2);
}
ra[0]=n+1; for(int i=n;i>=1;i--) if(a[i]==3) ra[++cnta3]=i;
for(int i=1;i<=m;i++){
if(b[i]==1) lb[++cntb1]=i;
s2[i]=s2[i-1]+(b[i]==2);
}
rb[0]=m+1; for(int i=m;i>=1;i--) if(b[i]==3) rb[++cntb3]=i;
for(int i=0;i<=maxn*2;i++) f1.tree[i]=f2.tree[i]=-inf;
int ans=0;
for(int i=0,j=min(cnta3,cntb3);j>=0;j--){
while(i<=min(cnta1,cntb1) && ra[j]>la[i] && rb[j]>lb[i]){
f1.update(-s1[la[i]]+s2[lb[i]]+maxn,i-s1[la[i]]);
f2.update(s1[la[i]]-s2[lb[i]]+maxn,i-s2[lb[i]]);
i++;
}
int res1=f1.query(-s1[max(ra[j]-1,0)]+s2[max(rb[j]-1,0)]+maxn)+s1[max(ra[j]-1,0)]+j;
int res2=f2.query(s1[max(ra[j]-1,0)]-s2[max(rb[j]-1,0)]+maxn)+s2[max(rb[j]-1,0)]+j;
ans=max({ans,res1,res2});
}
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T; cin>>T;
while(T--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 20092kb
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: 80ms
memory: 20004kb
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:
4 2 1 5 3 2 0 4 2 1 3 1 1 8 2 2 1 3 2 4 5 4 1 3 2 1 3 2 3 4 4 2 3 4 4 5 5 2 3 4 1 1 3 1 1 5 5 4 1 4 2 4 1 4 2 1 4 1 3 4 4 2 3 4 5 2 3 3 2 2 4 4 3 2 2 3 2 4 4 3 2 2 5 2 6 4 1 3 3 4 5 4 1 4 1 6 2 4 1 4 6 4 3 2 1 2 1 5 2 4 3 5 1 5 2 3 2 3 0 4 2 4 1 3 4 5 1 1 1 4 2 2 4 3 2 4 3 5 3 1 5 6 6 2 3 4 3 4 3 3 ...
result:
wrong answer 1st words differ - expected: '1', found: '4'