QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#471485#1281. Longest Common Subsequence_log_WA 0ms7292kbC++142.5kb2024-07-10 21:32:242024-07-10 21:32:25

Judging History

你现在查看的是最新测评结果

  • [2024-07-10 21:32:25]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:7292kb
  • [2024-07-10 21:32:24]
  • 提交

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];
    inline void update(int pos, int x, int t) {while(pos <= f(min(n, m))) Max[t][pos] = max(Max[t][pos], x), pos += lowbit(pos);}
    inline int query(int pos, int t) {int Max1 = -1; while(pos) Max1 = max(Max1, Max[t][pos]), pos -= lowbit(pos); return Max1;}
} using namespace BIT;

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m; rep(i, 1, n) cin >> a[i]; rep(i, 1, m) cin >> b[i]; ans = -2e9;
    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;
    // rep(i, 1, cnt[0][1]) cout << la[i] << ' ';
    // cout << '\n';
    // rep(i, 1, cnt[0][3]) cout << ra[i] << ' ';
    // cout << '\n';
    // rep(i, 1, n) cout << suma[i] << ' ';
    // cout << '\n';
    // rep(i, 1, cnt[1][1]) cout << lb[i] << ' ';
    // cout << '\n';
    // rep(i, 1, cnt[1][3]) cout << rb[i] << ' ';
    // cout << '\n';
    // rep(i, 1, m) cout << sumb[i] << ' ';
    // cout << "\n\n\n\n";
    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) {
        // cout << i << '\n';
        while(la[i] >= ra[j] || lb[i] >= rb[j]) --i; pos[j] = i;// cout << pos[j] << ' ' << i << '\n';
    }
    // cout << '\n';
    memset(Max, -0x3f, sizeof(Max));
    per(j, min(cnt[0][3], cnt[1][3]), 0) {
        rep(i, pos[j + 1] + 1, pos[j]) {
            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);
        }
        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';
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 7292kb

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:

2

result:

wrong answer 1st words differ - expected: '3', found: '2'