QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#488135#1281. Longest Common SubsequenceDEMONKILLERTL 0ms24036kbC++141.4kb2024-07-23 17:00:052024-07-23 17:00:05

Judging History

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

  • [2024-07-23 17:00:05]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:24036kb
  • [2024-07-23 17:00:05]
  • 提交

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
...

result: