QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#469691#1281. Longest Common SubsequencediduWA 161ms16260kbC++142.7kb2024-07-09 22:00:132024-07-09 22:00:13

Judging History

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

  • [2024-07-09 22:00:13]
  • 评测
  • 测评结果:WA
  • 用时:161ms
  • 内存:16260kb
  • [2024-07-09 22:00:13]
  • 提交

answer

#include<iostream>
#include<algorithm>
#include<cstdio>

#define ll long long
#define ls lc[p]
#define rs rc[p]
using namespace std;

const int INF = 1e6+10;
const int MAXN = 1e6+10;

int Tc;

ll a[MAXN],b[MAXN];

int cntla = 0,cntra = 0,cntlb = 0,cntrb = 0;
int la[MAXN],lb[MAXN];//表示第i个1的pos在哪里(从头部开始算)
int ra[MAXN],rb[MAXN];//表示第i个3的pos在哪里(从末尾开始算) 
int suma[MAXN],sumb[MAXN];//2的前缀和数组 

int lc[MAXN<<4],rc[MAXN<<4];
ll sgt[MAXN<<4][2+5];
int n,m;

ll ans = 0;
ll cnt = 0;//这个是动态开点的节点数 
int rt = 0;//表示最大的区间的线段树标号 

void pushup(int p){
	sgt[p][0] = max(sgt[ls][0],sgt[rs][0]);
	sgt[p][1] = max(sgt[ls][1],sgt[rs][1]);
	return ;
}

void update(int &p,int l,int r,int pos,ll vala,ll valb){
	if(!p)p = ++cnt;
	if(l == r){
		sgt[p][0] = max(sgt[p][0],vala); 
		sgt[p][1] = max(sgt[p][1],valb);
		return ;
	} 
	
	int mid = (l + r) >> 1;
	if(pos <= mid)update(ls,l,mid,pos,vala,valb);
	if(pos > mid)update(rs,mid+1,r,pos,vala,valb);
	pushup(p);
}

ll query(int p,int l,int r,int L,int R,int fl){
	if(!p || !sgt[p][fl] || L > R)return 0;
	if(L <= l && r <= R)return sgt[p][fl];
	int mid = (l + r) >> 1;
	
	ll Smx = -INF;
	if(L <= mid)Smx = max(Smx,query(ls,l,mid,L,R,fl));
	if(R > mid)Smx = max(Smx,query(rs,mid+1,r,L,R,fl));
	return Smx;
}

void init(){
	cntla = 0,cntlb = 0,cntra = 0,cntrb = 0;
	for(int i = 1;i <= cnt;i++)sgt[i][0] = sgt[i][1] = lc[i] = rc[i] = 0;
	rt = cnt = 0;
	return ;
}

int main(){
	
	scanf("%d",&Tc);
	while(Tc--){
		init();
		scanf("%d%d",&n,&m);
		for(int i = 1;i <= n;i++) scanf("%lld",&a[i]);
		for(int i = 1;i <= m;i++) scanf("%lld",&b[i]);
		for(int i = 1;i <= n;i++) suma[i] = suma[i-1] + (a[i] == 2);
		for(int i = 1;i <= m;i++) sumb[i] = sumb[i-1] + (b[i] == 2);
		for(int i = 1;i <= n;i++) if(a[i] == 1)la[++cntla] = i;
		for(int i = 1;i <= m;i++) if(b[i] == 1)lb[++cntlb] = i;
		for(int i = n;i >= 1;i--) if(a[i] == 3)ra[++cntra] = i;
		for(int i = m;i >= 1;i--) if(b[i] == 3)rb[++cntrb] = i;
		
		ra[0] = n+1;
		rb[0] = m+1;
		ans = 0;
		
		//枚举在答案的最长公共子序列中 有i个1的使用(左侧),有j个3的使用(右侧) 
		for(ll i = min(cntla,cntlb),j = 0;~i;i--){
			while(ra[j] > la[i] && rb[j] > lb[j] && j <= min(cntrb,cntra)){
				update(rt,-INF,INF,suma[ra[j]-1] - sumb[rb[j]-1], j + suma[ra[j]-1],j + sumb[rb[j]-1] ); j++;
			}
			ans = max({ans , i - suma[la[i]] + query(rt,-INF,INF,-INF,suma[la[i]] - sumb[lb[i]],0) ,
							 i - sumb[lb[i]] + query(rt,-INF,INF,suma[la[i]] - sumb[lb[i]],INF,1)});
		}
		
		printf("%lld\n",ans);
	}
	
	return 0;
}

//cf741c
//cf1556g
//cf1844e
//cf1693f

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 16260kb

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: 161ms
memory: 14076kb

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

result:

wrong answer 4th words differ - expected: '4', found: '3'