QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#517166#1281. Longest Common Subsequence123456xwdWA 58ms18228kbC++141.9kb2024-08-13 09:39:592024-08-13 09:39:59

Judging History

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

  • [2024-08-13 09:39:59]
  • 评测
  • 测评结果:WA
  • 用时:58ms
  • 内存:18228kb
  • [2024-08-13 09:39:59]
  • 提交

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,sufb[0]=m;
	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);
}
signed main(){
	int T=rd();
	while(T--)solve();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 18228kb

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: 58ms
memory: 18228kb

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
0
1
4
2
2
1
1
2
1
2
3
0
6
0
0
1
3
2
3
4
4
1
3
4
2
2
2
3
4
4
0
1
3
2
1
2
2
4
4
1
3
3
1
1
4
4
2
0
4
1
3
4
3
2
2
3
1
2
4
3
3
3
4
5
4
3
1
0
4
2
5
3
2
1
2
2
4
1
2
1
2
6
2
4
2
1
2
3
2
5
4
1
4
1
3
1
2
1
2
2
5
3
2
0
1
1
4
3
2
3
2
0
0
1
3
3
3
0
4
1
4
1
1
3
1
1
0
1
3
0
1
3
3
2
1
3
6
5
5
3
2
3
2
1
1
4
4
3
3
...

result:

wrong answer 2nd words differ - expected: '1', found: '0'