QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#517155 | #1281. Longest Common Subsequence | 123456xwd | TL | 0ms | 18080kb | C++14 | 2.0kb | 2024-08-13 09:29:30 | 2024-08-13 09:29:31 |
Judging History
answer
#include<bits/stdc++.h>
#define p_b push_back
#define m_p make_pair
#define pii pair<int,int>
//#define int long long
#define ls k<<1
#define rs k<<1|1
#define mid ((l+r)>>1)
#define gcd __gcd
#define lowbit(x) (x&(-x))
using namespace std;
int rd(){
int x=0,f=1; char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if (ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
const int N=1e6+5,INF=0x3f3f3f3f;
int n,m,a[N],b[N];
struct BIT{
int c[N<<1];
void clean(){
for(int i=1;i<=max(n,m)*2+1;i++) c[i]=-INF;
}
void add(int x,int y){
x+=max(n,m)+1;
for(;x<=max(n,m)*2+1;x+=lowbit(x)) c[x]=max(c[x],y);
}
int query(int x){
x+=max(n,m)+1;
int res=-INF;
while(x){
res=max(res,c[x]);
x-=lowbit(x);
}
return res;
}
}Ta,Tb;
int suma[N],sumb[N],sufa[N],sufb[N],prea[N],preb[N];
void solve(){
n=rd(),m=rd();
for(int i=1;i<=n;i++) a[i]=rd();
for(int i=1;i<=m;i++) b[i]=rd();
Ta.clean();Tb.clean();int tmp;
prea[0]=preb[0]=0,sufa[0]=n+1,sufb[0]=m+1;
for(int i=1;i<=n+1;i++)prea[i]=n+1,sufa[i]=0;
for(int i=1;i<=m+1;i++)preb[i]=m+1,sufb[i]=0;
for(int i=1;i<=n;i++)suma[i]=suma[i-1]+(a[i]==2);
tmp=0;
for(int i=1;i<=n;i++) if(a[i]==1) prea[++tmp]=i;
tmp=0;
for(int i=n;i>=1;i--) if(a[i]==3) sufa[++tmp]=i;
for(int i=1;i<=m;i++)sumb[i]=sumb[i-1]+(b[i]==2);
tmp=0;
for(int i=1;i<=m;i++) if(b[i]==1) preb[++tmp]=i;
tmp=0;
for(int i=m;i>=1;i--) if(b[i]==3) sufb[++tmp]=i;
int ans=-INF;
for(int i=min(n,m),j=0;i>=0;i--){
while(j<=min(n,m)&&sufa[j]>prea[i]&&sufb[j]>preb[i]){
Ta.add(suma[sufa[j]]-sumb[sufb[j]],j+suma[sufa[j]]);
Tb.add(sumb[sufb[j]]-suma[sufa[j]],j+suma[sufb[j]]);
j++;
}
ans=max(ans,i+max(Ta.query(suma[prea[i]]-sumb[preb[i]])-suma[prea[i]],Tb.query(sumb[preb[i]]-suma[prea[i]])-sumb[preb[i]]));
}
printf("%d\n",ans);
}
void clean(){
}
signed main(){
int T=rd();
while(T--){
solve();
//clean();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 18080kb
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...