QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#518263#1281. Longest Common SubsequencecqzhmWA 77ms20040kbC++141.6kb2024-08-13 18:59:072024-08-13 18:59:08

Judging History

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

  • [2024-08-13 18:59:08]
  • 评测
  • 测评结果:WA
  • 用时:77ms
  • 内存:20040kb
  • [2024-08-13 18:59:07]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int MAXN=1e6+10,N=1e6;
int n,m,a[MAXN],b[MAXN],maxn;
struct BIT{
	int tree[MAXN<<1];
	inline int lowbit(int x){return x&(-x);}
	inline void update(int x,int val){for(;x<=(maxn<<1);x+=lowbit(x)) tree[x]=max(tree[x],val);}
	inline int query(int x){int ans=0; for(;x;x-=lowbit(x)) ans=max(ans,tree[x]); return ans;}
}f1,f2;
int la[MAXN],ra[MAXN],s1[MAXN];
int lb[MAXN],rb[MAXN],s2[MAXN];
int cnta1,cnta3,cntb1,cntb3;
inline void solve(){
	cnta1=cnta3=cntb1=cntb3=0;
	cin>>n>>m; maxn=max(n,m);
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	for(int i=1;i<=n;i++){
		if(a[i]==1) la[++cnta1]=i;
		s1[i]=s1[i-1]+(a[i]==2);
	}
	ra[0]=n+1; for(int i=n;i>=1;i--) if(a[i]==3) ra[++cnta3]=i;
	for(int i=1;i<=m;i++){
		if(b[i]==1) lb[++cntb1]=i;
		s2[i]=s2[i-1]+(b[i]==2);
	}
	rb[0]=m+1; for(int i=m;i>=1;i--) if(b[i]==3) rb[++cntb3]=i;
	for(int i=0;i<=(maxn<<1);i++) f1.tree[i]=f2.tree[i]=-inf;
	int ans=0;
	for(int i=0,j=min(cnta3,cntb3);j>=0;j--){
		while(i<=min(cnta1,cntb1) && ra[j]>la[i] && rb[j]>lb[i]){
			f1.update(-s1[la[i]]+s2[lb[i]]+maxn,i-s1[la[i]]);
			f2.update(s1[la[i]]-s2[lb[i]]+maxn,i-s2[lb[i]]);
			i++;
		}
		int res1=f1.query(-s1[max(ra[j]-1,0ll)]+s2[max(rb[j]-1,0ll)]+maxn)+s1[max(ra[j]-1,0ll)]+j;
		int res2=f2.query(s1[max(ra[j]-1,0ll)]-s2[max(rb[j]-1,0ll)]+maxn)+s2[max(rb[j]-1,0ll)]+j;
		ans=max({ans,res1,res2});
	}
	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: 0ms
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
Wrong Answer
time: 77ms
memory: 18024kb

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:

4
2
1
5
3
2
0
4
2
1
3
1
1
8
2
2
1
3
2
4
5
4
1
3
2
1
3
2
3
4
4
2
3
4
4
5
5
2
3
4
1
1
3
1
1
5
5
4
1
4
2
4
1
4
2
1
4
1
3
4
4
2
3
4
5
2
3
3
2
2
4
4
3
2
2
3
2
4
4
3
2
2
5
2
6
4
1
3
3
4
5
4
1
4
1
6
2
4
1
4
6
4
3
2
1
2
1
5
2
4
3
5
1
5
2
3
2
3
0
4
2
4
1
3
4
5
1
1
1
4
2
2
4
3
2
4
3
5
3
1
5
6
6
2
3
4
3
4
3
3
...

result:

wrong answer 1st words differ - expected: '1', found: '4'