QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#176193 | #7108. Couleur | ucup-team1430 | RE | 1ms | 3452kb | C++17 | 5.7kb | 2023-09-11 11:51:24 | 2023-09-11 11:51:24 |
Judging History
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 ...