QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#469691 | #1281. Longest Common Subsequence | didu | WA | 161ms | 16260kb | C++14 | 2.7kb | 2024-07-09 22:00:13 | 2024-07-09 22:00:13 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include<cstdio>
#define ll long long
#define ls lc[p]
#define rs rc[p]
using namespace std;
const int INF = 1e6+10;
const int MAXN = 1e6+10;
int Tc;
ll a[MAXN],b[MAXN];
int cntla = 0,cntra = 0,cntlb = 0,cntrb = 0;
int la[MAXN],lb[MAXN];//表示第i个1的pos在哪里(从头部开始算)
int ra[MAXN],rb[MAXN];//表示第i个3的pos在哪里(从末尾开始算)
int suma[MAXN],sumb[MAXN];//2的前缀和数组
int lc[MAXN<<4],rc[MAXN<<4];
ll sgt[MAXN<<4][2+5];
int n,m;
ll ans = 0;
ll cnt = 0;//这个是动态开点的节点数
int rt = 0;//表示最大的区间的线段树标号
void pushup(int p){
sgt[p][0] = max(sgt[ls][0],sgt[rs][0]);
sgt[p][1] = max(sgt[ls][1],sgt[rs][1]);
return ;
}
void update(int &p,int l,int r,int pos,ll vala,ll valb){
if(!p)p = ++cnt;
if(l == r){
sgt[p][0] = max(sgt[p][0],vala);
sgt[p][1] = max(sgt[p][1],valb);
return ;
}
int mid = (l + r) >> 1;
if(pos <= mid)update(ls,l,mid,pos,vala,valb);
if(pos > mid)update(rs,mid+1,r,pos,vala,valb);
pushup(p);
}
ll query(int p,int l,int r,int L,int R,int fl){
if(!p || !sgt[p][fl] || L > R)return 0;
if(L <= l && r <= R)return sgt[p][fl];
int mid = (l + r) >> 1;
ll Smx = -INF;
if(L <= mid)Smx = max(Smx,query(ls,l,mid,L,R,fl));
if(R > mid)Smx = max(Smx,query(rs,mid+1,r,L,R,fl));
return Smx;
}
void init(){
cntla = 0,cntlb = 0,cntra = 0,cntrb = 0;
for(int i = 1;i <= cnt;i++)sgt[i][0] = sgt[i][1] = lc[i] = rc[i] = 0;
rt = cnt = 0;
return ;
}
int main(){
scanf("%d",&Tc);
while(Tc--){
init();
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++) scanf("%lld",&a[i]);
for(int i = 1;i <= m;i++) scanf("%lld",&b[i]);
for(int i = 1;i <= n;i++) suma[i] = suma[i-1] + (a[i] == 2);
for(int i = 1;i <= m;i++) sumb[i] = sumb[i-1] + (b[i] == 2);
for(int i = 1;i <= n;i++) if(a[i] == 1)la[++cntla] = i;
for(int i = 1;i <= m;i++) if(b[i] == 1)lb[++cntlb] = i;
for(int i = n;i >= 1;i--) if(a[i] == 3)ra[++cntra] = i;
for(int i = m;i >= 1;i--) if(b[i] == 3)rb[++cntrb] = i;
ra[0] = n+1;
rb[0] = m+1;
ans = 0;
//枚举在答案的最长公共子序列中 有i个1的使用(左侧),有j个3的使用(右侧)
for(ll i = min(cntla,cntlb),j = 0;~i;i--){
while(ra[j] > la[i] && rb[j] > lb[j] && j <= min(cntrb,cntra)){
update(rt,-INF,INF,suma[ra[j]-1] - sumb[rb[j]-1], j + suma[ra[j]-1],j + sumb[rb[j]-1] ); j++;
}
ans = max({ans , i - suma[la[i]] + query(rt,-INF,INF,-INF,suma[la[i]] - sumb[lb[i]],0) ,
i - sumb[lb[i]] + query(rt,-INF,INF,suma[la[i]] - sumb[lb[i]],INF,1)});
}
printf("%lld\n",ans);
}
return 0;
}
//cf741c
//cf1556g
//cf1844e
//cf1693f
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 16260kb
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: 161ms
memory: 14076kb
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 3 2 2 0 1 2 1 1 1 1 6 1 0 1 1 2 3 1 4 1 1 1 0 2 2 3 4 4 1 0 3 2 1 1 1 3 1 1 0 1 1 0 2 2 2 1 2 1 4 1 1 2 1 3 1 1 2 2 1 2 4 4 2 2 1 1 1 2 4 3 2 1 1 2 3 0 2 2 1 5 2 4 2 1 3 3 2 5 2 1 3 1 3 1 1 1 3 2 4 3 2 0 0 1 2 2 3 2 2 0 0 2 3 1 2 0 4 1 4 0 0 2 1 1 0 1 1 1 1 3 2 1 2 1 3 3 1 2 2 3 2 1 1 2 2 2 3 ...
result:
wrong answer 4th words differ - expected: '4', found: '3'