QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#498515#8776. Not Another Constructive!c20150005TL 0ms0kbC++141.5kb2024-07-30 15:45:542024-07-30 15:45:55

Judging History

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

  • [2024-07-30 15:45:55]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-07-30 15:45:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;using ll=long long;
int rd(int x=0,char c=getchar()){int f=1;while(!isdigit(c))f=(c^'-'?1:-1),c=getchar();while(isdigit(c))x=x*10+(c^48),c=getchar();return x*f;}
const int N=1e6+6;
int n,m;
int a[N],b[N];
int suma[N],sumb[N];
int la[N],lb[N];
int ra[N],rb[N];
int c[N<<1];
void upd(int x,int y){for(;x<=n+m;x+=(x&-x))c[x]=max(c[x],y);}
int ask(int x,int r=0){for(;x;x-=(x&-x))r=max(r,c[x]);return r;}
void solve(){
	n=rd(),m=rd();
	int tx1=0,ty1=0,tx2=0,ty2=0;
	for(int i=1;i<=n;i++){
		a[i]=rd();
		if(a[i]==1)la[++tx1]=i;
		suma[i]=suma[i-1];
		if(a[i]==2)suma[i]++;
	}suma[n+1]=suma[n];
	for(int i=n;i;i--)if(a[i]==3)ra[++ty1]=i;
	for(int i=1;i<=m;i++){
		b[i]=rd();
		if(b[i]==1)lb[++tx2]=i;
		sumb[i]=sumb[i-1];
		if(b[i]==2)sumb[i]++;
	}sumb[m+1]=sumb[m];
	for(int i=m;i;i--)if(b[i]==3)rb[++ty2]=i;
	ra[0]=n+1,rb[0]=m+1;
	int i=min(tx1,tx2),j=0;
	int ans=0;
	for(;i>=0;i--){
		while(j<=min(ty1,ty2)&&ra[j]>la[i]&&rb[j]>lb[i])
		upd(suma[ra[j]]-sumb[rb[j]]+m+1,j+suma[ra[j]]),j++;
		ans=max(ans,ask(suma[la[i]]-sumb[lb[i]]+m+1)+i-suma[la[i]]);
	}for(int i=1;i<=n+m+1;i++)c[i]=0;i=min(tx1,tx2),j=0;
	for(;i>=0;i--){
		while(j<=min(ty1,ty2)&&ra[j]>la[i]&&rb[j]>lb[i])
		upd(n+1-suma[ra[j]]+sumb[rb[j]],j+sumb[rb[j]]),j++;
		ans=max(ans,ask(n+1-suma[la[i]]+sumb[lb[i]])+i-sumb[lb[i]]);
	}printf("%d\n",ans);
	for(int i=1;i<=m*10&&i<N;i++)c[i]=0; 
}
int main(){
	int t=rd();while(t--)solve();
	return 0;
}

详细

Test #1:

score: 0
Time Limit Exceeded

input:

22 2
N??A??????C???????????

output:


result: