QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#488135 | #1281. Longest Common Subsequence | DEMONKILLER | TL | 0ms | 24036kb | C++14 | 1.4kb | 2024-07-23 17:00:05 | 2024-07-23 17:00:05 |
Judging History
answer
#include<bits/stdc++.h>
#define N 1000010
#define lb(i) i&(-i)
using namespace std;
int T,n,m,cnta,cntb,ccnta,ccntb,ans,a[N],b[N],La[N],Lb[N],Ra[N],Rb[N],suma[N],sumb[N],t[2][N];
void add(int p,int c,int opt){
for(int i=p;i<=(opt?m:n);i+=lb(i))
t[opt][i]=max(t[opt][i],c);
}
int query(int p,int opt){
if(p==0)return 0;
int ans=-0x3f3f3f3f;
for(int i=p;i;i-=lb(i))
ans=max(ans,t[opt][i]);
return ans;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
cnta=cntb=ccnta=ccntb=0,ans=-0x3f3f3f3f;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]==1)La[++cnta]=i;
suma[i]=suma[i-1]+(a[i]==2);
}
for(int i=1;i<=m;i++){
scanf("%d",&b[i]);
if(b[i]==1)Lb[++cntb]=i;
sumb[i]=sumb[i-1]+(b[i]==2);
}
for(int i=n;i>=1;i--)if(a[i]==3)Ra[++ccnta]=i;
for(int i=m;i>=1;i--)if(b[i]==3)Rb[++ccntb]=i;
Ra[0]=n+1,Rb[0]=m+1;
memset(t,-0x3f3f3f3f,sizeof(t));
for(int i=1;i<=cnta;i++)add(i,i-suma[La[i]],0);
for(int i=1;i<=cntb;i++)add(i,i-sumb[Lb[i]],1);
for(int i=min(cnta,cntb),j=0;j<=min(ccnta,ccntb);j++){
while(i&&(La[i]>=Ra[j]||Lb[i]>=Rb[j]))i--;
int ma=suma[Ra[j]-1]+query(i,0),mb=sumb[Rb[j]-1]+query(i,1);
ans=max(ans,j+min(ma,mb));
}
printf("%d\n",ans);
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 24036kb
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
Time Limit Exceeded
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 4 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 4 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 ...