QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#471560 | #1281. Longest Common Subsequence | _log_ | WA | 79ms | 7832kb | C++14 | 3.3kb | 2024-07-10 22:08:28 | 2024-07-10 22:08:29 |
Judging History
answer
# include <bits/stdc++.h>
# define rep(i, j, k) for(int i = j; i <= k; ++i)
# define per(i, j, k) for(int i = j; i >= k; --i)
# define go(u) for(int i = head[u], v; v = to[i], w = W[i], i; i = nxt[i])
# define maxn 100100
using namespace std;
int T, n, m, ans;
int a[maxn], b[maxn], la[maxn], ra[maxn], lb[maxn], rb[maxn], suma[maxn], sumb[maxn], cnt[2][4];
int pos[maxn];
namespace BIT {
# define f(x) (x + maxn)
# define lowbit(x) (x & -x)
int Max[2][maxn << 1];
vector<pair<bool, int> > Furina;
inline void update(int pos, int x, int t) {
// if(!T) cerr << pos << ' ' << x << '\n';
while(pos <= f(min(n, m))) {
Max[t][pos] = max(Max[t][pos], x);
if(Max[t][pos] > -0x3f3f3f3f) Furina.push_back({t, pos});
pos += lowbit(pos);
}
}
inline int query(int pos, int t) {
int Max1 = -2e9;
while(pos) Max1 = max(Max1, Max[t][pos]), pos -= lowbit(pos); return Max1;
}
inline void init() {
rep(i, 0, (int)Furina.size() - 1) {
int t = Furina[i].first, pos = Furina[i].second;
Max[t][pos] = -0x3f3f3f3f;
}
}
} using namespace BIT;
void solve() {
init(); memset(cnt, 0, sizeof(cnt));
Furina.clear();
cin >> n >> m; rep(i, 1, n) cin >> a[i]; rep(i, 1, m) cin >> b[i]; ans = 0;
ra[0] = n + 1, rb[0] = m + 1;
rep(i, 1, n) {
suma[i] = suma[i - 1] + (a[i] == 2);
if(a[i] == 1) la[++cnt[0][1]] = i;
}
per(i, n, 1) if(a[i] == 3) ra[++cnt[0][3]] = i;
rep(i, 1, m) {
sumb[i] = sumb[i - 1] + (b[i] == 2);
if(b[i] == 1) lb[++cnt[1][1]] = i;
}
per(i, m, 1) if(b[i] == 3) rb[++cnt[1][3]] = i;
for(int i = min(cnt[0][1], cnt[1][1]), j = 0; j <= min(cnt[0][3], cnt[1][3]); ++j) {
while(la[i] >= ra[j] || lb[i] >= rb[j]) --i; pos[j] = i;
}
// memset(Max, -0x3f, sizeof(Max));
update(f(sumb[lb[0]] - suma[la[0]]), sumb[lb[0]], 0);
update(f(suma[la[0]] - sumb[lb[0]]), suma[la[0]], 1);
// cout << sumb[lb[0]] - suma[la[0]] << ' ' << suma[la[0]] - sumb[lb[0]] << '\n';
pos[min(cnt[0][3], cnt[1][3]) + 1] = 0;
per(j, min(cnt[0][3], cnt[1][3]), 0) {
// if(!T) cerr << pos[j + 1] << ' ' << pos[j] << '\n';
rep(i, pos[j + 1] + 1, pos[j]) {
// if(!T) cerr << "insert" << i << ' ' << j << '\n';
update(f(sumb[lb[i]] - suma[la[i]]), i - sumb[lb[i]], 0);
update(f(suma[la[i]] - sumb[lb[i]]), i - suma[la[i]], 1);
}
// if(!T)cout << rb[j] << ' ' << sumb[rb[j] - 1] << ' ' << f(suma[ra[j] - 1] - sumb[rb[j] - 1]) << ' ' << query(f(suma[ra[j] - 1] - sumb[rb[j] - 1]), 0) + j << '\n';
// if(!T)cout << ra[j] << ' ' << suma[ra[j] - 1] << ' ' << f(sumb[rb[j] - 1] - suma[ra[j] - 1]) << ' ' << query(f(sumb[rb[j] - 1] - suma[ra[j] - 1]), 1) + j << '\n';
ans = max(ans, sumb[rb[j] - 1] + query(f(suma[ra[j] - 1] - sumb[rb[j] - 1]), 0) + j);
ans = max(ans, suma[ra[j] - 1] + query(f(sumb[rb[j] - 1] - suma[ra[j] - 1]), 1) + j);
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> T; memset(Max, -0x3f, sizeof(Max));
while(T--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 6824kb
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: 79ms
memory: 7832kb
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 7 1 0 1 2 2 3 4 4 1 1 1 0 2 3 4 6 5 1 1 3 2 0 2 1 3 1 1 1 3 1 1 2 3 2 1 3 1 4 2 2 2 1 4 1 1 2 3 1 4 4 5 2 2 1 1 1 2 4 3 2 1 1 2 3 1 3 2 1 5 2 4 2 1 3 4 3 6 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 2 3 0 6 1 4 1 1 3 1 1 0 1 2 1 1 3 3 2 2 3 3 3 1 2 3 4 2 1 1 3 3 2 3 ...
result:
wrong answer 14th words differ - expected: '6', found: '7'