QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#798284#1281. Longest Common SubsequenceSFlyerTL 7ms45456kbC++141.9kb2024-12-04 11:08:222024-12-04 11:08:24

Judging History

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

  • [2024-12-04 11:08:24]
  • 评测
  • 测评结果:TL
  • 用时:7ms
  • 内存:45456kb
  • [2024-12-04 11:08:22]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e6+6;

int n,m,a[N],b[N],sa[N],sb[N],la[N],ra[N],lb[N],rb[N];

struct fenwick {
	int t[N*4];
	int B=N*2;
	void init(){
		for (int i=0; i<N*4; i++) t[i]=-1e9;
	}
	void M(int p,int v){
		p+=B;
		while (p<N*4){
			t[p]=max(t[p],v),p+=p&-p;
		}
	}
	int Q(int p){
		int ans=-1e9;
		p+=B;
		while (p){
			ans=max(ans,t[p]),p-=p&-p;
		}
		return ans;
	}
} t[2];

void solve(){
	cin>>n>>m;
	for (int i=1; i<=n; i++){
		cin>>a[i];
		sa[i]=sa[i-1]+(a[i]==2);
		la[i]=n+1,ra[i]=0;
	}
	for (int i=1; i<=m; i++){
		cin>>b[i];
		sb[i]=sb[i-1]+(b[i]==2);
		lb[i]=m+1,rb[i]=0;
	}
	int c=0;
	for (int i=1; i<=n; i++){
		if (a[i]==1) la[++c]=i;
	} 
	c=0;
	for (int i=1; i<=m; i++){
		if (b[i]==1) lb[++c]=i;
	} 
	ra[0]=n+1,c=0;
	for (int i=n; i; i--){
		if (a[i]==3) ra[++c]=i;
	}
	rb[0]=m+1,c=0;
	for (int i=m; i; i--){
		if (b[i]==3) rb[++c]=i;
	} 
	t[0].init(),t[1].init();
	int ans=0;
	for (int j=min(n,m),i=0; j>=0; j--){
		while (i<=min(n,m) && la[i]<ra[j] && lb[i]<rb[j]){
			t[0].M(sa[la[i]]-sb[lb[i]],-sb[lb[i]]+i);
			t[1].M(sb[lb[i]]-sa[la[i]],-sa[la[i]]+i);
			i++;
		}
		ans=max(ans,t[0].Q(sa[ra[j]-1]-sb[rb[j]-1])+sb[rb[j]-1]+j);
		ans=max(ans,t[1].Q(sb[rb[j]-1]-sa[ra[j]-1])+sa[ra[j]-1]+j);
	}
	cout<<ans<<"\n";
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	cin>>t;
	while (t--){
		solve();
	}
	return 0;
}

// TRY! TRY! TRY!

/*
Think twice before coding. Have you overkilled?
Think twice before submitting.
Check on the samples and constraints carefully.
*/

/*
Be brave to guess.
Is your former/first approach correct?
Follow your intuition.
Use a notebook to note down your ideas and check whether they are correct.
*/

/*
A simple brute force may work? There is some limit on the answer?
Try to find patterns.
*/

详细

Test #1:

score: 100
Accepted
time: 7ms
memory: 45456kb

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...

output:


result: