QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#468617#1281. Longest Common SubsequenceqTL 0ms23808kbC++232.6kb2024-07-08 21:51:182024-07-08 21:51:18

Judging History

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

  • [2024-07-08 21:51:18]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:23808kb
  • [2024-07-08 21:51:18]
  • 提交

answer

#include<bits/stdc++.h>
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+5;
int n,m,a[N],b[N];
int la[N],lb[N],ra[N],rb[N],sa[N],sb[N];
int c[N*2];
void modify(int pos,int val){ for(int i=pos;i<=n+m+5;i+=i&-i) c[i]=std::max(c[i],val); }
int query(int pos){ int res=0; for(int i=pos;i;i-=i&-i) res=std::max(res,c[i]); return res; }
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]);
        if(a[i]==1) la[++len_la]=i;
        sa[i]=sa[i-1]+(a[i]==2);
    }
    sa[n+1]=sa[n];
    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]);
        if(b[i]==1) lb[++len_lb]=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;
    ra[0]=n+1,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]]);
    }
    memset(c,0,sizeof c);
    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]]+n+1,j+sb[rb[j]]),j++;
        ans=std::max(ans,query(-sa[la[i]]+sb[lb[i]]+n+1)+i-sb[lb[i]]);
    }
    IO::write(ans,"\n");
}
int main(){
    int T; IO::read(T);
    while(T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 23808kb

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
Time Limit Exceeded

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

result: