QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#498429 | #1281. Longest Common Subsequence | do_it_tomorrow | AC ✓ | 265ms | 117692kb | C++14 | 1.5kb | 2024-07-30 14:33:43 | 2024-07-30 14:33:43 |
Judging History
answer
#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=3e6+5,inf=7e5;
int n,m,a[N],b[N],la[N],lb[N],sa[N],sb[N],ra[N],rb[N];
int mmax;
struct BIT{
int s[N];
void clear(){for(int i=0;i<=mmax;i++) s[i]=-inf;}
int lowbit(int x){return x&-x;}
void updata(int x,int v){x+=max(n,m);for(int i=x;i<=mmax;i+=lowbit(i)) s[i]=max(s[i],v);}
int ask(int x){x+=max(n,m);int ans=-inf;for(int i=x;i>=1;i-=lowbit(i)) ans=max(ans,s[i]);return ans;}
}tree1,tree2;
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
la[0]=lb[0]=0,ra[0]=n+1,rb[0]=m+1;
for(int i=1;i<=n+1;i++) la[i]=n+1,ra[i]=0;
for(int i=1;i<=m+1;i++) lb[i]=m+1,rb[i]=0;
mmax=max(n,m)*2,tree1.clear(),tree2.clear();
int p1=0,p2=0;
for(int i=1;i<=n;i++) if(a[i]==1) la[++p1]=i;
for(int i=n;i>=1;i--) if(a[i]==3) ra[++p2]=i;
for(int i=1;i<=n;i++) sa[i]=sa[i-1]+(a[i]==2);
p1=0,p2=0;
for(int i=1;i<=m;i++) if(b[i]==1) lb[++p1]=i;
for(int i=m;i>=1;i--) if(b[i]==3) rb[++p2]=i;
for(int i=1;i<=m;i++) sb[i]=sb[i-1]+(b[i]==2);
int ans=0;
for(int i=0,j=min(n,m);j>=0;j--){
while(i<=min(n,m)&&la[i]<ra[j]&&lb[i]<rb[j]){
tree1.updata(sa[la[i]]-sb[lb[i]],i-sb[lb[i]]);
tree2.updata(sb[lb[i]]-sa[la[i]],i-sa[la[i]]);
i++;
}
ans=max(ans,j+max(sb[rb[j]-1]+tree1.ask(sa[ra[j]-1]-sb[rb[j]-1]),sa[ra[j]-1]+tree2.ask(sb[rb[j]-1]-sa[ra[j]-1])));
}
cout<<ans+1-1<<'\n';
}
signed main(){
int T;cin>>T;
while(T--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 17960kb
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: 0
Accepted
time: 265ms
memory: 18028kb
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:
ok 139889 tokens
Test #3:
score: 0
Accepted
time: 218ms
memory: 17904kb
input:
100000 10 10 1 1 1 3 1 2 1 1 1 1 3 1 1 2 1 2 2 2 1 3 10 10 1 1 3 2 3 1 1 2 3 2 3 3 1 3 2 1 1 1 2 1 10 10 2 2 3 3 1 2 3 1 3 2 2 3 2 3 2 1 2 3 3 1 10 10 3 3 1 1 1 3 2 3 2 2 2 2 1 2 2 2 2 2 3 3 10 10 3 3 3 2 1 3 3 1 3 1 1 3 1 1 3 2 1 1 1 3 10 10 1 1 2 1 3 1 1 3 1 3 2 1 1 1 1 3 2 1 2 2 10 10 2 2 3 1 2 2...
output:
4 5 5 4 4 5 4 5 4 7 4 5 5 4 4 5 4 6 6 6 3 4 4 4 5 4 4 4 6 4 5 5 5 3 5 6 5 4 4 4 4 5 5 3 4 4 3 7 3 4 5 4 4 4 3 5 5 5 4 6 5 3 5 5 3 3 3 5 3 4 4 5 4 4 3 4 5 6 5 6 7 5 4 5 4 4 6 5 4 5 6 5 4 3 3 4 3 4 4 4 4 4 5 4 5 5 5 4 2 6 3 5 5 5 5 4 4 4 4 4 5 5 4 4 5 6 5 4 3 4 4 4 3 4 3 3 4 5 5 3 4 6 4 3 4 5 6 5 5 5 ...
result:
ok 100000 tokens
Test #4:
score: 0
Accepted
time: 225ms
memory: 18012kb
input:
59509 16 16 3 3 3 2 3 3 1 3 1 2 1 1 3 1 3 2 3 3 3 1 1 3 1 1 2 2 2 2 3 3 1 1 16 17 2 1 1 1 3 1 1 2 3 3 2 1 2 3 3 3 1 1 3 1 1 1 1 1 1 3 2 3 2 1 3 1 3 19 10 1 1 3 3 2 1 1 2 3 1 2 3 3 1 3 1 2 1 1 3 1 1 3 1 1 1 2 2 1 10 14 3 3 3 1 1 3 3 1 3 1 3 1 3 2 2 3 3 1 1 3 1 3 3 3 12 20 1 1 2 2 1 1 2 1 1 2 3 1 1 1 ...
output:
6 10 7 6 8 4 6 6 7 6 6 7 5 8 8 5 8 5 8 5 5 7 6 5 5 7 6 6 8 7 5 6 6 4 7 7 6 5 7 7 7 9 5 5 8 9 7 7 6 11 8 5 7 9 6 7 8 5 5 6 6 8 8 6 9 8 4 6 7 8 7 5 8 4 5 6 8 8 5 6 6 7 7 8 5 6 7 6 7 5 10 10 6 6 8 6 6 7 5 7 5 6 6 7 3 6 10 5 6 7 7 8 7 4 4 5 7 5 7 7 6 5 6 8 6 8 6 6 7 7 8 4 4 6 7 6 5 5 6 7 8 9 6 8 7 9 8 8...
result:
ok 59509 tokens
Test #5:
score: 0
Accepted
time: 220ms
memory: 17960kb
input:
50000 20 20 1 3 3 2 1 2 1 1 1 2 3 2 1 2 2 2 2 2 1 3 3 2 2 1 3 3 1 2 3 2 1 2 2 3 2 3 1 3 2 1 20 20 1 3 2 3 2 2 1 1 1 3 3 2 2 2 3 3 3 3 3 1 2 3 2 3 1 2 1 2 2 2 1 3 1 3 1 2 3 2 3 1 20 20 1 3 1 1 2 3 1 2 2 3 3 1 2 1 1 1 2 2 1 2 2 1 1 2 2 2 1 1 1 3 1 1 3 1 2 1 2 2 3 1 20 20 3 3 3 2 1 2 2 2 1 2 2 2 2 2 3 ...
output:
8 10 11 8 7 8 9 9 9 8 7 9 9 8 8 10 8 8 10 9 8 8 8 10 9 8 9 9 8 7 5 7 8 7 9 9 9 7 10 11 12 12 8 10 11 10 9 9 10 8 8 8 9 10 8 9 9 10 9 8 8 8 10 8 9 11 9 6 9 6 9 8 8 11 9 10 9 8 8 9 10 9 9 7 9 9 9 8 9 11 6 8 8 8 8 9 9 8 9 7 8 7 6 8 10 9 9 10 8 9 8 9 11 9 8 7 8 8 10 11 6 8 9 9 8 7 9 9 10 9 7 10 8 9 9 8 ...
result:
ok 50000 tokens
Test #6:
score: 0
Accepted
time: 172ms
memory: 18028kb
input:
11967 85 68 1 2 2 2 1 3 3 1 3 3 1 2 2 1 1 2 1 2 1 3 2 2 3 2 3 1 2 3 1 2 3 2 1 1 2 1 3 1 2 3 2 1 2 2 1 2 3 2 2 1 1 1 3 2 2 2 2 3 2 1 3 3 1 3 2 3 1 2 3 2 1 2 1 3 2 3 3 2 2 3 2 2 1 1 2 1 3 3 1 2 1 1 1 2 1 2 3 1 1 3 2 1 3 3 1 1 3 1 1 3 2 2 1 2 1 1 2 3 3 2 1 2 2 3 2 1 2 3 1 3 3 3 1 3 1 3 1 3 3 1 1 3 1 2 ...
output:
32 29 25 37 25 29 22 27 31 31 22 22 31 37 23 29 27 29 22 31 26 30 25 28 26 27 24 26 25 25 28 30 23 33 33 24 21 29 23 35 26 36 26 23 24 33 31 28 25 22 31 35 32 35 26 25 30 35 28 36 27 25 25 28 33 26 30 27 23 35 32 36 30 28 26 30 31 33 28 24 33 36 21 30 33 33 29 29 22 22 29 27 20 38 29 31 30 35 34 39 ...
result:
ok 11967 tokens
Test #7:
score: 0
Accepted
time: 204ms
memory: 17908kb
input:
10000 100 100 2 3 2 2 2 3 2 3 1 1 2 2 2 2 1 2 3 3 3 2 3 3 1 3 3 2 2 3 1 1 3 3 2 3 1 3 3 1 2 2 2 3 1 2 3 1 2 2 3 3 1 1 3 1 3 1 2 2 2 2 2 3 2 1 3 1 2 2 1 2 1 2 1 2 3 2 3 1 3 2 2 1 2 1 2 3 1 3 2 1 3 3 2 2 1 1 3 1 1 2 3 1 1 2 1 1 1 3 3 2 3 3 3 2 1 3 3 2 2 2 1 3 1 3 1 3 1 2 2 1 1 2 3 2 3 3 2 1 3 2 3 3 3 ...
output:
38 40 34 35 39 40 38 40 39 39 36 38 42 41 39 37 42 43 35 37 36 34 39 40 41 40 33 36 38 38 42 38 40 42 44 42 35 41 35 44 39 45 36 37 39 38 40 40 35 37 39 39 40 43 42 37 41 41 39 44 43 35 40 41 37 40 39 39 36 38 40 39 38 39 37 35 40 40 41 38 36 42 41 38 38 38 34 43 37 36 40 39 41 46 38 42 40 37 47 39 ...
result:
ok 10000 tokens
Test #8:
score: 0
Accepted
time: 197ms
memory: 17968kb
input:
1000 1000 1000 3 1 3 3 3 2 3 1 3 2 1 1 3 1 2 2 3 3 1 2 2 3 3 3 3 1 3 3 3 1 1 2 2 1 1 2 1 2 2 2 1 3 1 3 1 1 1 2 3 1 3 1 3 1 1 2 1 1 1 3 1 2 1 1 2 3 2 2 2 1 1 2 2 1 2 2 3 3 2 1 1 2 2 3 1 3 2 1 2 3 3 1 3 2 2 3 2 1 1 3 3 3 1 3 1 2 2 3 1 3 3 3 1 3 2 3 2 3 2 1 2 1 1 1 1 3 1 3 1 2 3 3 1 1 3 3 2 3 3 2 1 1 3...
output:
366 357 362 343 351 343 357 344 343 357 343 348 353 354 358 346 349 357 347 357 344 349 353 356 354 358 350 361 356 342 353 362 350 350 351 353 364 355 355 361 348 349 354 354 347 345 346 361 349 338 360 344 353 339 351 344 343 352 345 354 335 359 355 351 350 355 354 342 347 347 356 358 364 356 351 ...
result:
ok 1000 tokens
Test #9:
score: 0
Accepted
time: 197ms
memory: 20264kb
input:
100 10000 10000 2 2 2 3 2 3 3 2 2 1 1 1 3 3 2 3 2 3 1 2 1 2 2 1 3 2 1 3 1 3 3 2 2 2 2 2 1 3 3 3 2 3 1 3 3 3 2 1 1 2 2 1 2 1 1 3 1 2 3 1 1 3 3 2 1 3 2 2 2 3 3 3 1 2 2 1 3 1 1 3 3 1 3 2 2 2 2 2 1 1 1 2 3 2 2 1 2 2 1 2 3 3 2 3 3 3 1 3 1 3 3 3 2 1 1 2 1 3 1 3 2 2 1 1 2 1 3 3 2 3 3 3 1 2 2 1 3 2 1 3 2 1 ...
output:
3431 3388 3380 3406 3403 3366 3399 3389 3390 3374 3389 3356 3419 3423 3348 3392 3366 3392 3411 3398 3436 3429 3371 3410 3414 3366 3377 3406 3384 3391 3391 3421 3400 3409 3412 3407 3429 3405 3444 3381 3414 3398 3437 3390 3381 3397 3396 3399 3412 3382 3403 3368 3393 3445 3410 3396 3393 3430 3416 3391 ...
result:
ok 100 tokens
Test #10:
score: 0
Accepted
time: 199ms
memory: 28932kb
input:
10 100000 100000 3 1 2 2 1 1 1 3 2 3 1 3 3 1 2 3 1 2 3 3 3 2 3 3 3 3 2 1 1 3 3 1 1 2 3 1 2 3 1 2 2 2 3 3 2 1 1 3 3 1 2 3 3 2 3 3 3 3 1 2 1 3 1 3 3 2 2 2 3 3 3 2 1 1 2 1 3 1 3 2 3 3 3 3 2 3 1 2 2 2 2 3 2 3 1 3 3 1 3 3 1 1 3 2 1 3 1 3 3 3 3 3 2 1 1 2 2 3 1 3 2 3 3 3 2 2 3 1 3 2 1 3 1 2 3 2 2 1 3 3 2 1...
output:
33573 33651 33656 33615 33599 33519 33490 33488 33510 33572
result:
ok 10 tokens
Test #11:
score: 0
Accepted
time: 210ms
memory: 114876kb
input:
1 1000000 1000000 1 3 2 3 1 1 2 2 2 1 2 1 3 1 1 2 2 3 2 1 3 1 1 1 3 2 2 1 1 1 2 1 2 3 3 1 2 1 2 3 3 2 1 1 1 1 1 2 2 3 2 3 2 1 3 3 1 2 2 3 1 3 3 3 2 3 2 1 2 1 2 3 2 2 1 1 1 3 1 3 2 1 1 3 1 1 2 1 1 3 3 2 1 2 3 3 3 2 1 3 3 2 3 1 1 1 1 3 3 2 3 2 1 1 2 1 3 3 3 3 3 3 2 3 1 3 2 1 2 3 1 2 3 2 2 3 3 1 1 1 1 ...
output:
333799
result:
ok "333799"
Test #12:
score: 0
Accepted
time: 199ms
memory: 114196kb
input:
1 1000000 1000000 2 1 2 1 1 3 1 3 2 2 2 2 1 3 2 2 2 3 2 1 3 3 3 2 3 1 1 1 3 2 3 2 1 1 3 1 3 2 2 3 1 1 2 3 1 1 1 2 3 3 2 1 2 2 2 3 1 2 2 3 1 2 2 1 3 2 2 1 1 2 1 1 2 1 2 1 2 2 3 1 3 3 3 2 1 1 1 1 1 1 3 1 3 1 2 1 3 3 2 3 1 1 2 1 1 1 1 1 2 2 1 1 2 3 1 3 2 3 3 3 3 1 3 1 3 1 3 1 3 2 2 2 3 3 3 2 1 3 3 3 3 ...
output:
334219
result:
ok "334219"
Test #13:
score: 0
Accepted
time: 211ms
memory: 116468kb
input:
1 1000000 1000000 1 2 2 2 2 1 3 3 3 2 1 1 3 3 1 2 3 1 2 1 2 3 2 3 1 2 1 2 1 1 2 1 1 3 2 1 1 1 2 3 2 1 1 1 1 3 3 2 3 3 1 3 1 3 3 2 1 2 3 1 2 3 2 3 2 3 2 2 3 1 3 2 2 3 3 1 1 1 3 2 2 1 2 3 1 1 1 1 1 3 1 3 1 3 1 2 2 2 1 1 2 1 1 2 1 2 1 2 1 1 3 1 1 1 3 2 1 1 1 2 3 3 3 3 2 3 2 1 1 3 1 3 2 2 1 1 3 3 1 1 3 ...
output:
333870
result:
ok "333870"
Test #14:
score: 0
Accepted
time: 206ms
memory: 114544kb
input:
1 1000000 1000000 1 1 2 3 3 3 1 1 1 1 1 3 2 3 3 1 2 3 2 1 2 3 1 3 3 1 2 2 1 2 2 2 1 1 3 2 2 3 3 3 2 1 2 2 1 1 2 2 1 3 3 1 3 3 1 1 3 2 3 2 2 2 1 1 3 1 2 2 3 3 3 3 1 3 3 1 2 3 2 1 2 1 3 1 3 2 1 2 1 3 1 1 1 2 3 2 2 1 3 1 3 3 3 2 1 2 1 2 1 2 3 3 3 1 3 1 1 2 2 3 1 1 1 2 1 1 3 2 1 1 3 3 2 2 1 3 1 2 2 2 2 ...
output:
334023
result:
ok "334023"
Test #15:
score: 0
Accepted
time: 211ms
memory: 117692kb
input:
1 1000000 1000000 2 2 3 1 3 2 3 2 2 3 3 2 3 3 1 1 1 3 3 1 2 2 3 1 1 2 1 3 3 3 1 1 1 2 1 2 3 1 1 3 3 3 3 3 1 3 3 1 2 1 1 3 2 1 2 3 3 2 3 2 3 3 1 2 3 3 3 3 2 1 2 1 1 2 1 3 2 2 3 3 3 1 2 2 3 2 3 3 2 2 1 3 3 1 2 1 2 1 1 2 2 1 1 3 2 3 3 2 3 2 1 2 1 2 2 3 3 2 3 2 1 2 1 3 2 3 1 2 2 2 1 1 3 1 2 2 1 1 1 1 1 ...
output:
334141
result:
ok "334141"