QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#498593 | #1281. Longest Common Subsequence | xinhaowen | WA | 36ms | 13572kb | C++14 | 2.0kb | 2024-07-30 16:28:03 | 2024-07-30 16:28:04 |
Judging History
answer
#include<cstdio>
#include<algorithm>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
template<typename T>void read(T &x){
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;
}
void write(char x){putchar(x);}
template<typename T>void write(T x){
if(x<0)putchar('-'),x=-x;
char stk[24];int cnt=0;
do stk[++cnt]=x%10+48,x/=10;while(x);
for(;cnt;)putchar(stk[cnt--]);
}
template<typename T,typename ...Args>void read(T &x,Args &...args){read(x);read(args...);}
template<typename T,typename ...Args>void write(T x,Args ...args){write(x);write(args...);}
template<typename T>T min(T x,T y){return x<y?x:y;}
template<typename T>T max(T x,T y){return x>y?x:y;}
const int maxn=1e6+4;int T,n,m,a[maxn],b[maxn],la[maxn],lb[maxn],ra[maxn],rb[maxn],suma[maxn],sumb[maxn];
int maxx[maxn<<1],ca1,ca3,cb1,cb3,ans;
void update(int x,int val){for(;x<=n+m-1;x+=(x&(-x)))maxx[x]=max(maxx[x],val);}
int query(int x){int ans=0;for(;x;x-=(x&(-x)))ans=max(ans,maxx[x]);return ans;}
signed main(){
read(T);
for(;T--;){
read(n,m);ca1=ca3=cb1=cb3=ans=0;
for(int i=1;i<=n;++i)read(a[i]),a[i]==1&&(la[++ca1]=i),suma[i]=suma[i-1]+(a[i]==2);
for(int i=1;i<=m;++i)read(b[i]),b[i]==1&&(lb[++cb1]=i),sumb[i]=sumb[i-1]+(b[i]==2);
for(int i=n;i;--i)a[i]==3&&(ra[++ca3]=i);
for(int i=m;i;--i)b[i]==3&&(rb[++cb3]=i);
int i=min(ca1,cb1),j=0;suma[n+1]=suma[n];sumb[m+1]=sumb[m];ra[0]=n+1;rb[0]=m+1;
for(;i>=0;--i){
for(;j<=min(ca3,cb3)&&ra[j]>la[i]&&rb[j]>lb[i];update(m+1+suma[ra[j]]-sumb[rb[j]],j+suma[ra[j]]),++j);
ans=max(ans,i-suma[la[i]]+query(m+1+suma[la[i]]-sumb[lb[i]]));
}
for(int i=1;i<=n+m+1;++i)maxx[i]=0;
i=min(ca1,cb1),j=0;
for(;i>=0;--i){
for(;j<=min(ca3,cb3)&&ra[j]>la[i]&&rb[j]>lb[i];update(n+1+sumb[rb[j]]-suma[ra[j]],j+sumb[rb[j]]),++j);
ans=max(ans,i-sumb[lb[i]]+query(n+1+sumb[lb[i]]-suma[la[i]]));
}
for(int i=1;i<=n+m+1;++i)maxx[i]=0;
write(ans,'\n');
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 13572kb
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
Wrong Answer
time: 36ms
memory: 11548kb
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 0 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 0 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 0 1 3 2 3 2 2 0 0 2 3 1 2 0 4 0 4 1 1 3 1 1 0 1 1 0 1 3 2 2 2 3 3 3 1 2 2 3 2 1 1 3 3 2 3 ...
result:
wrong answer 2nd words differ - expected: '1', found: '0'