QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#469260 | #1281. Longest Common Subsequence | z | TL | 3ms | 20040kb | C++14 | 1.8kb | 2024-07-09 16:51:05 | 2024-07-09 16:51:05 |
Judging History
answer
/* 值域 1-3,求最长公共上升子序列
i + j + min( sumb[rb[j]]-sumb[lb[i]] , suma[ra[j]]-suma[la[i]] )
1^ sumb[rb[j]]-sumb[lb[i]-1] <= suma[ra[j]]-suma[la[i]-1]
=> sumb[rb[j]] - suma[ra[j]] <= sumb[lb[i]]-suma[la[i]]
2^ sumb[rb[j]]-sumb[lb[i]] >= suma[ra[j]]-suma[la[i]]
=> suma[ra[j]] - sumb[rb[j]] <= suma[la[i]]-sumb[lb[i]]
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int T,n,m,LIM;
int a[N],b[N];
int la[N],lb[N],ra[N],rb[N],suma[N],sumb[N];
int k1,k2,k3,k4;
struct BIT{
int S[N*2];
void clear(){
for(int i=1;i<=LIM*2;i++) S[i]=-0x3f3f3f3f;
}
void update(int x,int v){
for(x+=LIM;x<=LIM*2;x+=x&-x)
S[x]=max(S[x],v);
}
int ask(int x){
int ret=-0x3f3f3f3f;
for(x+=LIM;x;x-=x&-x)
ret=max(ret,S[x]);
return ret;
}
}T1,T2;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>T;
while(T--){
k1=k2=k3=k4=0;
int ans=0;
cin>>n>>m;
LIM=max(n,m);
T1.clear();T2.clear();
ra[0]=n+1,rb[0]=m+1;
for(int i=1;i<=n+1;i++) la[i]=n+1,ra[i]=0;
for(int i=1;i<=m+1;i++) lb[i]=m+1,rb[i]=0;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]==1) la[++k1]=i;
suma[i]=suma[i-1]+(a[i]==2);
}
for(int i=1;i<=m;i++){
cin>>b[i];
if(b[i]==1) lb[++k2]=i;
sumb[i]=sumb[i-1]+(b[i]==2);
}
for(int i=n;i>=1;i--) if(a[i]==3) ra[++k3]=i;
for(int i=m;i>=1;i--) if(b[i]==3) rb[++k4]=i;
for(int i=0,j=min(n,m);j>=0;j--){
for(;i<=n&&i<=m&&la[i]<ra[j]&&lb[i]<rb[j];i++){
T1.update(sumb[rb[i]-1]-suma[ra[i]-1],i+sumb[rb[i]-1]);
T2.update(suma[ra[i]-1]-sumb[rb[i]-1],i+suma[ra[i]-1]);
}
ans=max(ans,max(j-sumb[lb[j]]+T1.ask(sumb[lb[j]]-suma[la[j]]),j-suma[la[j]]+T2.ask(suma[la[j]]-sumb[lb[j]])));
}
cout<<ans<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 20040kb
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...