QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#498515 | #8776. Not Another Constructive! | c20150005 | TL | 0ms | 0kb | C++14 | 1.5kb | 2024-07-30 15:45:54 | 2024-07-30 15:45:55 |
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???????????