QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#517440 | #1281. Longest Common Subsequence | wy2025 | TL | 3ms | 19948kb | C++14 | 1.4kb | 2024-08-13 11:29:38 | 2024-08-13 11:29:38 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
int n,m,a[2][N],L[2][N],R[2][N],s[2][N],cl[2],cr[2];//0a,1b
struct T_A{
int c[N*4];
void init(){for(int i=1;i<=2*(n+m);i++) c[i]=0;}
int lowbit(int x){return x&-x;}
void update(int x,int v){x+=n+m+1;for(int i=x;i<=2*(n+m);i+=lowbit(i)) c[i]=max(c[i],v);}
int ask(int x){
x+=n+m+1;
int ans=0;
for(int i=x;i;i-=lowbit(i)) ans=max(ans,c[i]);
return ans;
}
}t[2];
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[0][i];
for(int i=1;i<=m;i++) cin>>a[1][i];
n=min(n,m);
for(int j=0;j<2;j++){
cl[j]=cr[j]=0;
R[j][0]=n+1;
t[j].init();
for(int i=1;i<=n;i++){
if(a[j][i]==1) L[j][++cl[j]]=i;
s[j][i]=s[j][i-1]+(a[j][i]==2);
}
for(int i=n;i;i--)
if(a[j][i]==3) R[j][++cr[j]]=i;
}
int ans=max(s[0][n],s[1][n]);
for(int i=0,j=min(cr[0],cr[1]);~j;j--){
while(i<min(cl[0],cl[1])&&L[0][i+1]<R[0][j]&&L[1][i+1]<R[1][j])
i++,
t[0].update(s[0][R[0][i]-1]-s[1][R[1][i]-1],i-s[0][L[0][i]]),
t[1].update(s[0][L[0][i]]-s[1][L[1][i]],i-s[1][L[1][i]]);
ans=max(ans,j+max(s[0][R[0][j]-1]+t[0].ask(s[0][L[0][j]]-s[1][L[1][j]]),
s[1][R[1][j]-1]+t[1].ask(s[0][R[0][j]-1]-s[1][R[1][j]-1])));
}
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: 3ms
memory: 19948kb
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...