QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#226251#7108. Couleurreal_sigma_team#Compile Error//C++203.6kb2023-10-25 19:07:252023-10-25 19:07:26

Judging History

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

  • [2023-10-25 19:07:26]
  • 评测
  • [2023-10-25 19:07:25]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

using ll = long long;

const int N = 5e6;

int sz = 0;

struct node {
    int sm = 0;
    int L = -1, R = -1;

    node() = default;
} tr[N];

int n;

void build(int t, int l = 0, int r = n - 1) {
    if (l == r) return;
    tr[t].L = sz++;
    tr[t].R = sz++;
    int m = (l + r) / 2;
    build(tr[t].L, l, m);
    build(tr[t].R, m + 1, r);
}

int update(int t, int k, int l = 0, int r = n - 1) {
    int u = sz++;
    tr[u] = tr[t];
    tr[u].sm++;
    if (l != r) {
        int m = (l + r) / 2;
        if (k <= m) tr[u].L = update(tr[u].L, k, l, m);
        else tr[u].R = update(tr[u].R, k, m + 1, r);
    }
    return u;
}

int get(int t, int ql, int qr, int l = 0, int r = n - 1) {
    if (ql <= l && r <= qr) return tr[t].sm;
    if (r < ql || qr < l) return 0;
    int m = (l + r) / 2;
    return get(tr[t].L, ql, qr, l, m) + get(tr[t].R, ql, qr, m + 1, r);
}

void solve() {
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i], --a[i];
    }
    vector<int> pref(n + 1);
    pref[0] = 0;
    sz = 1;
    build(0);
    for (int i = 0; i < n; ++i) {
        pref[i + 1] = update(pref[i], a[i]);
    }
    set<int> st;
    st.insert(0);
    vector<ll> ans(n);
    vector<int> right(n);
    right[0] = n - 1;
    for (int i = 0; i < n; ++i) {
        ans[0] += get(pref[i], a[i] + 1, n - 1);
    }
    multiset<ll> vals(all(ans));
    auto upd = [&](int k, ll x) -> void {
        vals.extract(ans[k]);
        vals.insert(ans[k] = x);
    };
    int z = *prev(vals.end());
    for (int _ = 0; _ < n; ++_) {
        cout << z << ' ';
        int k; cin >> k; k ^= z; --k;
        int l = *prev(st.upper_bound(k));
        int r = right[l];
        ll cur = ans[l];
        upd(k, 0);
        st.erase(l);
        if (k - l < r - k) {
            if (k != l) {
                ll cc = 0;
                for (int i = l; i < k; ++i) {
                    cc += get(pref[i], a[i] + 1, n - 1) - get(pref[l], a[i] + 1, n - 1);
                }
                upd(l, cc);
                right[l] = k - 1;
                st.insert(l);
            }
            if (k != r) {
                ll cc = cur;
                for (int i = l; i <= k; ++i) {
                    cc -= get(pref[r + 1], 0, a[i] - 1) - get(pref[i + 1], 0, a[i] - 1);
                }
                upd(k + 1, cc);
                right[k + 1] = r;
                st.insert(k + 1);
            }
        } else {
            if (k != r) {
                ll cc = 0;
                for (int i = k + 1; i <= r; ++i) {
                    cc += get(pref[i], a[i] + 1, n - 1) - get(pref[k + 1], a[i] + 1, n - 1);
                }
                upd(k + 1, cc);
                st.insert(k + 1);
                right[k + 1] = r;
            }
            if (k != l) {
                ll cc = cur;
                for (int i = r; i >= k; --i) {
                    cc -= get(pref[i], a[i] + 1, n - 1) - get(pref[l], a[i] + 1, n - 1);
                }
                upd(l, cc);
                st.insert(l);
                right[l] = k - 1;
            }
        }
        z = *prev(vals.end());
    }
    cout << '\n';
    for (int i = 0; i < sz; ++i) tr[i] = node();
}

int main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#else
    freopen("input.txt", "r", stdin);
#endif
    int t;
    cin >> t;
    while (t--)
    solve();
    return 0;
}

详细

answer.code:143:1: fatal error: error writing to /tmp/ccb9yrIz.s: File too large
  143 | }
      | ^
compilation terminated.