QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#469429#4216. Funny SalesmanqTL 0ms0kbC++142.7kb2024-07-09 19:07:592024-07-09 19:07:59

Judging History

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

  • [2024-07-09 19:07:59]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [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

output:


result: