QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#469400 | #1281. Longest Common Subsequence | q | TL | 4ms | 25764kb | C++14 | 2.6kb | 2024-07-09 18:42:14 | 2024-07-09 18:42:14 |
Judging History
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+1;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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 25764kb
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 ...