QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#176193#7108. Couleurucup-team1430RE 1ms3452kbC++175.7kb2023-09-11 11:51:242023-09-11 11:51:24

Judging History

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

  • [2023-09-11 11:51:24]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3452kb
  • [2023-09-11 11:51:24]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define ld long double
#define pb push_back
#define sws cin.tie(0)->sync_with_stdio(false);
#define endl '\n'

using namespace std;

const int N = 2e5+10;
const int MOD = 256;
// const ll MOD = 998244353;
// const ll MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;

#define vp vector<point>
#define ld long double
const ld EPS = 1e-6;
const ld PI = acos(-1);

struct ST {    
    int n;
    vector<int> left, right, t;
    int idx = 1;
    int id = 0;

    ST(int n): n(n) {
        left.assign(60 * n, 0);
        right.assign(60 * n, 0);
        t.assign(60 * n, 0);
    }

    int f(int a, int b) {
        return a + b;
    }

    int query(int l, int r, int x, int lx, int rx) {
        if (l > r) return 0;
        if(l <= lx and rx <= r) return t[x];
        if(r < lx or rx < l) return id;

        int mid = (lx+rx)/2;
        auto s1 = query(l, r, left[x], lx, mid);
        auto s2 = query(l, r, right[x], mid+1, rx);
        return f(s1, s2);
    }
    int query(int l, int r, int x) { return query(l, r, x, 0, n-1); }

    int update(int i, int val, int x, int lx, int rx) {
        int y = idx++;
        if(lx == rx) {
            t[y] = val + t[x];
            return y;
        }

        int mid = (lx+rx)/2;
        if(lx <= i and i <= mid) {
            int k = update(i, val, left[x], lx, mid);
            left[y] = k;
            right[y] = right[x];
        }
        else {
            int k = update(i, val, right[x], mid+1, rx);
            left[y] = left[x];
            right[y] = k;
        }

        t[y] = f(t[left[y]], t[right[y]]);
        return y;
    }
    int update(int i, int val, int x) { return update(i, val, x, 0, n-1); }
};

int32_t main()
{
    // #ifndef LOCAL
    // sws;
    // #endif

    int t; cin >> t;
    while (t--) {
        int n; cin >> n;

        ST seg(n+1);
        vector<int> a(n+1), p(n+1);
        for (int i=1;i<=n;i++) {
            cin >> a[i];
        }
        for (int i=1;i<=n;i++) {
            cin >> p[i];
        }

        vector<int> roots(n+10); roots[0] = 0;
        ll inv_total = 0;
        for (int i=1;i<=n;i++) {
            roots[i] = seg.update(a[i], 1, roots[i-1]);
            inv_total += seg.query(a[i] + 1, n + 1, roots[i]);
        }

        auto query_range = [&](int l, int r, int lx, int rx) {
            if (lx > rx) return 0;
            return seg.query(l, r, roots[rx]) - seg.query(l, r, roots[lx-1]);
        };
        auto contribution = [&](int id, int l, int r) {
            int x = a[id];
            return query_range(x+1, n, l, id-1) + query_range(0, x-1, id+1, r);
        };

        set<tuple<ll, ll, ll>> ranges;
        multiset<ll> best_inv;
        auto insert = [&](ll l, ll r, ll inv) {
            best_inv.insert(inv);
            ranges.insert({l, r, inv});
        };
        auto remove = [&](ll l, ll r, ll inv) {
            best_inv.erase(best_inv.find(inv));
            ranges.erase({l, r, inv});
        };
        auto best_ans = [&]() {
            if (best_inv.empty()) return 0LL;
            return *(best_inv.rbegin());
        };
        insert(1, n, inv_total);

        vector<ll> ans; ans.push_back(best_ans());
        set<int> used;
        for (int i=1;i<=n;i++) {
            int pos = p[i] ^ ans.back(); // lucas sala
            if (used.count(pos)) return 0;
            used.insert(pos);
            int x = a[pos];
            auto it = ranges.upper_bound({pos, n+10, 0LL}); it--;
            auto [l, r, inv] = *it;
            remove(l, r, inv);

            // inv = inv_left + inv_right + inv_leftright + inv[p]
            inv -= contribution(pos, l, r);
            if (pos == l) {
                // cout << "ok" << endl;
                if (l+1 <= r) insert(l+1, r, inv);
            }
            else if (pos == r) {
                // cout << "ok2" << endl;
                if (l <= r-1) insert(l, r-1, inv);
            }
            else {
                assert(r - l >= 2);
                ll inv_leftright = 0;
                if (pos - l < r - pos) { // small is the left one
                // cout << "ok3" << endl;
                    ll inv_left = 0;
                    for (int i=l;i<=pos-1;i++) {
                        inv_left += contribution(i, l, pos-1);
                        inv_leftright += query_range(0, a[i]-1, pos+1, r);
                    }
                    assert(inv_left % 2 == 0);
                    inv_left /= 2;
                    // left = inv_left
                    // right = inv - inv_left - inv_leftright
                    insert(l, pos-1, inv_left);
                    insert(pos+1, r, inv - inv_left - inv_leftright);

                } else { // small is the right one
                    ll inv_right = 0;
                    for (int i=pos+1;i<=r;i++) {
                        inv_right += contribution(i, pos+1, r);
                        inv_leftright += query_range(a[i]+1, n, l, pos-1);
                    }
                    assert(inv_right % 2 == 0);
                    inv_right /= 2;
                    // right = inv_right
                    // left = inv - inv_right - inv_leftright
                    insert(l, pos-1, inv - inv_right - inv_leftright);
                    insert(pos+1, r, inv_right);
                }
            }
            ans.push_back(best_ans());
        }

        ans.pop_back();

        for (int i=0;i<ans.size();i++) {
            if (i) cout << " ";
            cout << ans[i];
        }
        cout << endl;


    }

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3452kb

input:

3
5
4 3 1 1 1
5 4 5 3 1
10
9 7 1 4 7 8 5 7 4 8
21 8 15 5 9 2 4 5 10 6
15
4 8 8 1 12 1 10 14 7 14 2 9 13 10 3
37 19 23 15 7 2 10 15 2 13 4 5 8 7 10

output:

7 0 0 0 0
20 11 7 2 0 0 0 0 0 0
42 31 21 14 14 4 1 1 1 0 0 0 0 0 0

result:

ok 3 lines

Test #2:

score: -100
Runtime Error

input:

11116
10
10 5 10 3 6 4 8 5 9 8
31 27 24 11 12 3 0 2 3 1
10
8 2 7 2 8 10 1 10 9 10
6 5 2 13 2 1 0 1 3 1
10
7 10 7 6 1 3 10 6 7 9
21 18 10 1 6 5 4 8 9 10
10
2 10 4 8 8 5 7 2 6 7
20 10 9 1 15 0 4 2 9 7
10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10
6 3 5 2 7 10 9 1 4 8
10
1 10 1 3...

output:

21 18 16 12 10 6 4 1 1 0
12 12 10 10 4 4 4 2 1 0
20 16 9 5 3 3 3 0 0 0
22 14 8 8 5 5 2 1 1 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
19 12 7 4 4 2 2 1 0 0
20 18 8 3 1 1 0 0 0 0
45 21 21 10 3 3 3 0 0 0
17 11 8 2 1 1 1 0 0 0
13 4 1 0 0 0 0 0 0 0
29 27 22 15 9 7 4 3 1 0
26 16 9 2 1 1 1 1 1 0
0 0 0 0 0 ...

result: