QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#469429 | #4216. Funny Salesman | q | TL | 0ms | 0kb | C++14 | 2.7kb | 2024-07-09 19:07:59 | 2024-07-09 19:07:59 |
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;}
namespace IO{
#define ISIZE (1<<20)
char in[ISIZE],*p1=in,*p2=in;
std::streambuf *inbuf=std::cin.rdbuf();
#define getchar() (p1==p2&&(p2=(p1=in)+inbuf->sgetn(in,ISIZE),p1==p2)?EOF:*p1++)
std::streambuf *outbuf=std::cout.rdbuf();
#define putchar(ch) (outbuf->sputc(ch))
template<class Tp> void read(Tp &x)noexcept{
x=0; bool f=0; char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
if(f) x=-x;
}
template<class Tp,class ...Args> void read(Tp &x,Args &...args)noexcept{ read(x),read(args...); }
void write(const char *x)noexcept{ while(*x) putchar(*x++); }
template<class Tp> void write(Tp x)noexcept{
static char stk[50],*top=stk;
if(x<0) putchar('-'),x=-x;
do *++top=x%10,x/=10; while(x);
do putchar(*top--^48); while(top!=stk);
}
template<class Tp,class ...Args> void write(Tp x,Args ...args)noexcept{ write(x),write(args...); }
#undef getchar
#undef putchar
#undef ISIZE
}
const int N=1e6+6;
int n,m;
int a[N],b[N];
int sa[N],sb[N];
int la[N],lb[N];
int ra[N],rb[N];
int c[N<<1];
void modify(int x,int y){for(;x<=n+m+1;x+=(x&-x))c[x]=max(c[x],y);}
int query(int x,int r=0){for(;x;x-=(x&-x))r=max(r,c[x]);return r;}
void solve(){
IO::read(n,m);
int len_la=0,len_ra=0,len_lb=0,len_rb=0;
for(int i=1;i<=n;i++) IO::read(a[i]);
for(int i=1;i<=n;i++) if(a[i]==1) la[++len_la]=i;
for(int i=1;i<=n;i++) sa[i]=sa[i-1]+(a[i]==2); sa[n+1]=sa[n];
ra[0]=n+1; for(int i=n;i>=1;i--) if(a[i]==3) ra[++len_ra]=i;
for(int i=1;i<=m;i++) IO::read(b[i]);
for(int i=1;i<=m;i++) if(b[i]==1) lb[++len_lb]=i;
for(int i=1;i<=m;i++) sb[i]=sb[i-1]+(b[i]==2); sb[m+1]=sb[m];
for(int i=m;i>=1;i--) if(b[i]==3) rb[++len_rb]=i; rb[0]=m+1;
memset(c,0,sizeof c);
int ans=0,i=std::min(len_la,len_lb),j=0;
for(;i>=0;i--){
while(j<=std::min(len_ra,len_rb)&&ra[j]>la[i]&&rb[j]>lb[i]) modify(sa[ra[j]]-sb[rb[j]]+m+1,j+sa[ra[j]]),j++;
ans=std::max(ans,query(sa[la[i]]-sb[lb[i]]+m+1)+i-sa[la[i]]);
}for(int i=1;i<=n+m+1;i++)c[i]=0;i=min(len_la,len_lb),j=0;
for(;i>=0;i--){
while(j<=min(len_ra,len_rb)&&ra[j]>la[i]&&rb[j]>lb[i])
modify(n+1-sa[ra[j]]+sb[rb[j]],j+sb[rb[j]]),j++;
ans=max(ans,query(n+1-sa[la[i]]+sb[lb[i]])+i-sb[lb[i]]);
}printf("%d\n",ans);
}
int main(){
int t=rd();while(t--)solve();
return 0;
}
詳細信息
Test #1:
score: 0
Time Limit Exceeded
input:
5 1 2 0 2 3 0 3 4 0 4 5 1