QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#471879#1281. Longest Common Subsequence_log_WA 100ms12668kbC++143.5kb2024-07-11 10:45:082024-07-11 10:45:08

Judging History

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

  • [2024-07-11 10:45:08]
  • 评测
  • 测评结果:WA
  • 用时:100ms
  • 内存:12668kb
  • [2024-07-11 10:45:08]
  • 提交

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, c1, c3;
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 << 3];
    set<pair<bool, int> > Furina;
    inline void update(int pos, int x, int t) {
        Furina.insert({t, pos}); bool flag = t == 1;
        while(pos <= f(min(n, m))) {
            Max[t][pos] = max(Max[t][pos], x);
            // cerr << "updateing " << t << ' ' << pos << ' ' << Max[t][pos] << '\n';
            pos += lowbit(pos);
        }
    }
    inline void clear(int pos, int t) {while(pos <= f(min(n, m))) Max[t][pos] = -0x3f3f3f3f, pos += lowbit(pos);}
    inline int query(int pos, int t) {
        int Max1 = -2e9; bool flag = pos - maxn == 1 && t == 1;
        while(pos) Max1 = max(Max1, Max[t][pos]), pos -= lowbit(pos);
        return Max1;
    }
    inline void init() {for(auto i = Furina.begin(); i != Furina.end(); ++i) clear(i -> second, i -> first); Furina.clear();}
} using namespace BIT;

signed main(){
    // freopen("sequence.in", "r", stdin);
    // freopen("sequence.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> T; memset(Max, -0x3f, sizeof(Max));
    while(T--) {
        cin >> n >> m; init(); ans = 0; memset(cnt, 0, sizeof(cnt));
        rep(i, 1, n) {
            cin >> a[i]; suma[i] = suma[i - 1] + (a[i] == 2);
            if(a[i] == 1) la[++cnt[0][1]] = i;
        }
        rep(i, 1, m) {
            cin >> b[i]; sumb[i] = sumb[i - 1] + (b[i] == 2);
            if(b[i] == 1) lb[++cnt[1][1]] = i;
        }
        per(i, n, 1) if(a[i] == 3) ra[++cnt[0][3]] = i;
        per(i, m, 1) if(b[i] == 3) rb[++cnt[1][3]] = i;
        c1 = min(cnt[0][1], cnt[1][1]), c3 = min(cnt[0][3], cnt[1][3]); ra[0] = n + 1, rb[0] = m + 1;
        // cout << c1 << ' ' << c3 << '\n';
        // rep(i, 1, c1) cout << la[i] << ' ' << lb[i] << '\n'; cout << '\n';
        // rep(i, 1, c3) cout << ra[i] << ' ' << rb[i] << '\n'; cout << '\n';
        // rep(i, 1, n) cout << suma[i] << ' '; cout << '\n';
        // rep(i, 1, m) cout << sumb[i] << ' '; cout << '\n';
        for(int i = c1, j = 0; j <= c3; ++j) {while(la[i] >= ra[j] || lb[i] >= rb[j]) i--; pos[j] = i;} pos[c3 + 1] = -1;
        per(j, c3, 0) {
            rep(i, pos[j + 1] + 1, pos[j]) {
                update(f(suma[la[i]] - sumb[lb[i]]), i - sumb[lb[i]], 0);
                update(f(sumb[lb[i]] - suma[la[i]]), i - suma[la[i]], 1);
                // cout << "update" << i << ' ' << -(sumb[lb[i]] - suma[la[i]]) << ' ' << i - sumb[lb[i]] << '\n';
                // cout << "update" << i << ' ' << -(suma[la[i]] - sumb[lb[i]]) << ' ' << i - suma[la[i]] << '\n';
            }
            ans = max(ans, query(f(suma[ra[j] - 1] - sumb[rb[j] - 1]), 0) + j + sumb[rb[j] - 1]);
            ans = max(ans, query(f(sumb[rb[j] - 1] - suma[ra[j] - 1]), 1) + j + suma[ra[j] - 1]);
            // cout << "query" << j << ' ' << suma[ra[j] - 1] - sumb[rb[j] - 1] << ' ' << query(f(suma[ra[j] - 1] - sumb[rb[j] - 1]), 0) << '\n';
            // cout << "query" << j << ' ' << suma[ra[j] - 1] - sumb[rb[j] - 1] << ' ' << query(f(sumb[rb[j] - 1] - suma[ra[j] - 1]), 1) << '\n';
        }
        cout << ans << '\n';
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 12668kb

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: 100ms
memory: 12040kb

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
2
3
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
0
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
2
2
3
1
2
0
4
1
4
1
2
3
0
1
0
1
3
1
1
3
2
2
2
3
3
3
1
4
4
5
2
3
3
3
3
3
3
...

result:

wrong answer 32nd words differ - expected: '1', found: '2'