QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#798288#1281. Longest Common SubsequenceSFlyerAC ✓104ms66188kbC++141.9kb2024-12-04 11:11:222024-12-04 11:11:23

Judging History

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

  • [2024-12-04 11:11:23]
  • 评测
  • 测评结果:AC
  • 用时:104ms
  • 内存:66188kb
  • [2024-12-04 11:11: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;
	void init(int mx){
		n=mx*2,B=mx;
		for (int i=0; i<=n; i++) t[i]=-1e9;
	}
	void M(int p,int v){
		p+=B;
		while (p<=n){
			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(n+m),t[1].init(n+m);
	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: 0ms
memory: 17956kb

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: 0
Accepted
time: 91ms
memory: 18052kb

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

result:

ok 139889 tokens

Test #3:

score: 0
Accepted
time: 101ms
memory: 18088kb

input:

100000
10 10
1 1 1 3 1 2 1 1 1 1
3 1 1 2 1 2 2 2 1 3
10 10
1 1 3 2 3 1 1 2 3 2
3 3 1 3 2 1 1 1 2 1
10 10
2 2 3 3 1 2 3 1 3 2
2 3 2 3 2 1 2 3 3 1
10 10
3 3 1 1 1 3 2 3 2 2
2 2 1 2 2 2 2 2 3 3
10 10
3 3 3 2 1 3 3 1 3 1
1 3 1 1 3 2 1 1 1 3
10 10
1 1 2 1 3 1 1 3 1 3
2 1 1 1 1 3 2 1 2 2
10 10
2 2 3 1 2 2...

output:

4
5
5
4
4
5
4
5
4
7
4
5
5
4
4
5
4
6
6
6
3
4
4
4
5
4
4
4
6
4
5
5
5
3
5
6
5
4
4
4
4
5
5
3
4
4
3
7
3
4
5
4
4
4
3
5
5
5
4
6
5
3
5
5
3
3
3
5
3
4
4
5
4
4
3
4
5
6
5
6
7
5
4
5
4
4
6
5
4
5
6
5
4
3
3
4
3
4
4
4
4
4
5
4
5
5
5
4
2
6
3
5
5
5
5
4
4
4
4
4
5
5
4
4
5
6
5
4
3
4
4
4
3
4
3
3
4
5
5
3
4
6
4
3
4
5
6
5
5
5
...

result:

ok 100000 tokens

Test #4:

score: 0
Accepted
time: 80ms
memory: 18096kb

input:

59509
16 16
3 3 3 2 3 3 1 3 1 2 1 1 3 1 3 2
3 3 3 1 1 3 1 1 2 2 2 2 3 3 1 1
16 17
2 1 1 1 3 1 1 2 3 3 2 1 2 3 3 3
1 1 3 1 1 1 1 1 1 3 2 3 2 1 3 1 3
19 10
1 1 3 3 2 1 1 2 3 1 2 3 3 1 3 1 2 1 1
3 1 1 3 1 1 1 2 2 1
10 14
3 3 3 1 1 3 3 1 3 1
3 1 3 2 2 3 3 1 1 3 1 3 3 3
12 20
1 1 2 2 1 1 2 1 1 2 3 1
1 1 ...

output:

6
10
7
6
8
4
6
6
7
6
6
7
5
8
8
5
8
5
8
5
5
7
6
5
5
7
6
6
8
7
5
6
6
4
7
7
6
5
7
7
7
9
5
5
8
9
7
7
6
11
8
5
7
9
6
7
8
5
5
6
6
8
8
6
9
8
4
6
7
8
7
5
8
4
5
6
8
8
5
6
6
7
7
8
5
6
7
6
7
5
10
10
6
6
8
6
6
7
5
7
5
6
6
7
3
6
10
5
6
7
7
8
7
4
4
5
7
5
7
7
6
5
6
8
6
8
6
6
7
7
8
4
4
6
7
6
5
5
6
7
8
9
6
8
7
9
8
8...

result:

ok 59509 tokens

Test #5:

score: 0
Accepted
time: 95ms
memory: 17964kb

input:

50000
20 20
1 3 3 2 1 2 1 1 1 2 3 2 1 2 2 2 2 2 1 3
3 2 2 1 3 3 1 2 3 2 1 2 2 3 2 3 1 3 2 1
20 20
1 3 2 3 2 2 1 1 1 3 3 2 2 2 3 3 3 3 3 1
2 3 2 3 1 2 1 2 2 2 1 3 1 3 1 2 3 2 3 1
20 20
1 3 1 1 2 3 1 2 2 3 3 1 2 1 1 1 2 2 1 2
2 1 1 2 2 2 1 1 1 3 1 1 3 1 2 1 2 2 3 1
20 20
3 3 3 2 1 2 2 2 1 2 2 2 2 2 3 ...

output:

8
10
11
8
7
8
9
9
9
8
7
9
9
8
8
10
8
8
10
9
8
8
8
10
9
8
9
9
8
7
5
7
8
7
9
9
9
7
10
11
12
12
8
10
11
10
9
9
10
8
8
8
9
10
8
9
9
10
9
8
8
8
10
8
9
11
9
6
9
6
9
8
8
11
9
10
9
8
8
9
10
9
9
7
9
9
9
8
9
11
6
8
8
8
8
9
9
8
9
7
8
7
6
8
10
9
9
10
8
9
8
9
11
9
8
7
8
8
10
11
6
8
9
9
8
7
9
9
10
9
7
10
8
9
9
8
...

result:

ok 50000 tokens

Test #6:

score: 0
Accepted
time: 81ms
memory: 17976kb

input:

11967
85 68
1 2 2 2 1 3 3 1 3 3 1 2 2 1 1 2 1 2 1 3 2 2 3 2 3 1 2 3 1 2 3 2 1 1 2 1 3 1 2 3 2 1 2 2 1 2 3 2 2 1 1 1 3 2 2 2 2 3 2 1 3 3 1 3 2 3 1 2 3 2 1 2 1 3 2 3 3 2 2 3 2 2 1 1 2
1 3 3 1 2 1 1 1 2 1 2 3 1 1 3 2 1 3 3 1 1 3 1 1 3 2 2 1 2 1 1 2 3 3 2 1 2 2 3 2 1 2 3 1 3 3 3 1 3 1 3 1 3 3 1 1 3 1 2 ...

output:

32
29
25
37
25
29
22
27
31
31
22
22
31
37
23
29
27
29
22
31
26
30
25
28
26
27
24
26
25
25
28
30
23
33
33
24
21
29
23
35
26
36
26
23
24
33
31
28
25
22
31
35
32
35
26
25
30
35
28
36
27
25
25
28
33
26
30
27
23
35
32
36
30
28
26
30
31
33
28
24
33
36
21
30
33
33
29
29
22
22
29
27
20
38
29
31
30
35
34
39
...

result:

ok 11967 tokens

Test #7:

score: 0
Accepted
time: 92ms
memory: 17964kb

input:

10000
100 100
2 3 2 2 2 3 2 3 1 1 2 2 2 2 1 2 3 3 3 2 3 3 1 3 3 2 2 3 1 1 3 3 2 3 1 3 3 1 2 2 2 3 1 2 3 1 2 2 3 3 1 1 3 1 3 1 2 2 2 2 2 3 2 1 3 1 2 2 1 2 1 2 1 2 3 2 3 1 3 2 2 1 2 1 2 3 1 3 2 1 3 3 2 2 1 1 3 1 1 2
3 1 1 2 1 1 1 3 3 2 3 3 3 2 1 3 3 2 2 2 1 3 1 3 1 3 1 2 2 1 1 2 3 2 3 3 2 1 3 2 3 3 3 ...

output:

38
40
34
35
39
40
38
40
39
39
36
38
42
41
39
37
42
43
35
37
36
34
39
40
41
40
33
36
38
38
42
38
40
42
44
42
35
41
35
44
39
45
36
37
39
38
40
40
35
37
39
39
40
43
42
37
41
41
39
44
43
35
40
41
37
40
39
39
36
38
40
39
38
39
37
35
40
40
41
38
36
42
41
38
38
38
34
43
37
36
40
39
41
46
38
42
40
37
47
39
...

result:

ok 10000 tokens

Test #8:

score: 0
Accepted
time: 91ms
memory: 18112kb

input:

1000
1000 1000
3 1 3 3 3 2 3 1 3 2 1 1 3 1 2 2 3 3 1 2 2 3 3 3 3 1 3 3 3 1 1 2 2 1 1 2 1 2 2 2 1 3 1 3 1 1 1 2 3 1 3 1 3 1 1 2 1 1 1 3 1 2 1 1 2 3 2 2 2 1 1 2 2 1 2 2 3 3 2 1 1 2 2 3 1 3 2 1 2 3 3 1 3 2 2 3 2 1 1 3 3 3 1 3 1 2 2 3 1 3 3 3 1 3 2 3 2 3 2 1 2 1 1 1 1 3 1 3 1 2 3 3 1 1 3 3 2 3 3 2 1 1 3...

output:

366
357
362
343
351
343
357
344
343
357
343
348
353
354
358
346
349
357
347
357
344
349
353
356
354
358
350
361
356
342
353
362
350
350
351
353
364
355
355
361
348
349
354
354
347
345
346
361
349
338
360
344
353
339
351
344
343
352
345
354
335
359
355
351
350
355
354
342
347
347
356
358
364
356
351
...

result:

ok 1000 tokens

Test #9:

score: 0
Accepted
time: 92ms
memory: 18256kb

input:

100
10000 10000
2 2 2 3 2 3 3 2 2 1 1 1 3 3 2 3 2 3 1 2 1 2 2 1 3 2 1 3 1 3 3 2 2 2 2 2 1 3 3 3 2 3 1 3 3 3 2 1 1 2 2 1 2 1 1 3 1 2 3 1 1 3 3 2 1 3 2 2 2 3 3 3 1 2 2 1 3 1 1 3 3 1 3 2 2 2 2 2 1 1 1 2 3 2 2 1 2 2 1 2 3 3 2 3 3 3 1 3 1 3 3 3 2 1 1 2 1 3 1 3 2 2 1 1 2 1 3 3 2 3 3 3 1 2 2 1 3 2 1 3 2 1 ...

output:

3431
3388
3380
3406
3403
3366
3399
3389
3390
3374
3389
3356
3419
3423
3348
3392
3366
3392
3411
3398
3436
3429
3371
3410
3414
3366
3377
3406
3384
3391
3391
3421
3400
3409
3412
3407
3429
3405
3444
3381
3414
3398
3437
3390
3381
3397
3396
3399
3412
3382
3403
3368
3393
3445
3410
3396
3393
3430
3416
3391
...

result:

ok 100 tokens

Test #10:

score: 0
Accepted
time: 97ms
memory: 21956kb

input:

10
100000 100000
3 1 2 2 1 1 1 3 2 3 1 3 3 1 2 3 1 2 3 3 3 2 3 3 3 3 2 1 1 3 3 1 1 2 3 1 2 3 1 2 2 2 3 3 2 1 1 3 3 1 2 3 3 2 3 3 3 3 1 2 1 3 1 3 3 2 2 2 3 3 3 2 1 1 2 1 3 1 3 2 3 3 3 3 2 3 1 2 2 2 2 3 2 3 1 3 3 1 3 3 1 1 3 2 1 3 1 3 3 3 3 3 2 1 1 2 2 3 1 3 2 3 3 3 2 2 3 1 3 2 1 3 1 2 3 2 2 1 3 3 2 1...

output:

33573
33651
33656
33615
33599
33519
33490
33488
33510
33572

result:

ok 10 tokens

Test #11:

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

input:

1
1000000 1000000
1 3 2 3 1 1 2 2 2 1 2 1 3 1 1 2 2 3 2 1 3 1 1 1 3 2 2 1 1 1 2 1 2 3 3 1 2 1 2 3 3 2 1 1 1 1 1 2 2 3 2 3 2 1 3 3 1 2 2 3 1 3 3 3 2 3 2 1 2 1 2 3 2 2 1 1 1 3 1 3 2 1 1 3 1 1 2 1 1 3 3 2 1 2 3 3 3 2 1 3 3 2 3 1 1 1 1 3 3 2 3 2 1 1 2 1 3 3 3 3 3 3 2 3 1 3 2 1 2 3 1 2 3 2 2 3 3 1 1 1 1 ...

output:

333799

result:

ok "333799"

Test #12:

score: 0
Accepted
time: 104ms
memory: 66112kb

input:

1
1000000 1000000
2 1 2 1 1 3 1 3 2 2 2 2 1 3 2 2 2 3 2 1 3 3 3 2 3 1 1 1 3 2 3 2 1 1 3 1 3 2 2 3 1 1 2 3 1 1 1 2 3 3 2 1 2 2 2 3 1 2 2 3 1 2 2 1 3 2 2 1 1 2 1 1 2 1 2 1 2 2 3 1 3 3 3 2 1 1 1 1 1 1 3 1 3 1 2 1 3 3 2 3 1 1 2 1 1 1 1 1 2 2 1 1 2 3 1 3 2 3 3 3 3 1 3 1 3 1 3 1 3 2 2 2 3 3 3 2 1 3 3 3 3 ...

output:

334219

result:

ok "334219"

Test #13:

score: 0
Accepted
time: 96ms
memory: 66116kb

input:

1
1000000 1000000
1 2 2 2 2 1 3 3 3 2 1 1 3 3 1 2 3 1 2 1 2 3 2 3 1 2 1 2 1 1 2 1 1 3 2 1 1 1 2 3 2 1 1 1 1 3 3 2 3 3 1 3 1 3 3 2 1 2 3 1 2 3 2 3 2 3 2 2 3 1 3 2 2 3 3 1 1 1 3 2 2 1 2 3 1 1 1 1 1 3 1 3 1 3 1 2 2 2 1 1 2 1 1 2 1 2 1 2 1 1 3 1 1 1 3 2 1 1 1 2 3 3 3 3 2 3 2 1 1 3 1 3 2 2 1 1 3 3 1 1 3 ...

output:

333870

result:

ok "333870"

Test #14:

score: 0
Accepted
time: 92ms
memory: 66176kb

input:

1
1000000 1000000
1 1 2 3 3 3 1 1 1 1 1 3 2 3 3 1 2 3 2 1 2 3 1 3 3 1 2 2 1 2 2 2 1 1 3 2 2 3 3 3 2 1 2 2 1 1 2 2 1 3 3 1 3 3 1 1 3 2 3 2 2 2 1 1 3 1 2 2 3 3 3 3 1 3 3 1 2 3 2 1 2 1 3 1 3 2 1 2 1 3 1 1 1 2 3 2 2 1 3 1 3 3 3 2 1 2 1 2 1 2 3 3 3 1 3 1 1 2 2 3 1 1 1 2 1 1 3 2 1 1 3 3 2 2 1 3 1 2 2 2 2 ...

output:

334023

result:

ok "334023"

Test #15:

score: 0
Accepted
time: 96ms
memory: 66088kb

input:

1
1000000 1000000
2 2 3 1 3 2 3 2 2 3 3 2 3 3 1 1 1 3 3 1 2 2 3 1 1 2 1 3 3 3 1 1 1 2 1 2 3 1 1 3 3 3 3 3 1 3 3 1 2 1 1 3 2 1 2 3 3 2 3 2 3 3 1 2 3 3 3 3 2 1 2 1 1 2 1 3 2 2 3 3 3 1 2 2 3 2 3 3 2 2 1 3 3 1 2 1 2 1 1 2 2 1 1 3 2 3 3 2 3 2 1 2 1 2 2 3 3 2 3 2 1 2 1 3 2 3 1 2 2 2 1 1 3 1 2 2 1 1 1 1 1 ...

output:

334141

result:

ok "334141"