QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#226273 | #7108. Couleur | real_sigma_team# | WA | 507ms | 9648kb | C++20 | 3.5kb | 2023-10-25 19:16:24 | 2023-10-25 19:16:25 |
Judging History
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'