QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#226273#7108. Couleurreal_sigma_team#WA 507ms9648kbC++203.5kb2023-10-25 19:16:242023-10-25 19:16:25

Judging History

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

  • [2023-10-25 19:16:25]
  • 评测
  • 测评结果:WA
  • 用时:507ms
  • 内存:9648kb
  • [2023-10-25 19:16:24]
  • 提交

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 = 3e6;
int sz = 0;

int sm[N], L[N], R[N];

int n;

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

int update(int t, int k, int l = 0, int r = n - 1) {
    int u = sz++;
    L[u] = L[t];
    R[u] = R[t];
    sm[u] = sm[t] + 1;
    if (l != r) {
        int m = (l + r) / 2;
        if (k <= m) L[u] = update(L[u], k, l, m);
        else R[u] = update(R[u], 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 sm[t];
    if (r < ql || qr < l) return 0;
    int m = (l + r) / 2;
    return get(L[t], ql, qr, l, m) + get(R[t], ql, qr, m + 1, r);
}

void solve() {
    cin >> n;
    if (n > 1e5 - 1) {
        cout << "4wfgfgefegf";
        exit(0);
    }
    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) {
        sm[i] = 0;
        L[i] = R[i] = -1;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
}

詳細信息

Test #1:

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

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
Wrong Answer
time: 507ms
memory: 9648kb

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 ...

result:

wrong answer 11111th lines differ - expected: '2512961269 2512932299 25129263...6 46 35 31 23 17 10 8 8 4 1 0 0', found: '4wfgfgefegf'