QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#390859 | #7108. Couleur | KKT89 | RE | 0ms | 0kb | C++17 | 3.9kb | 2024-04-15 23:55:06 | 2024-04-15 23:55:07 |
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) { return (ull)rng() % B; }
// 0-indexed
template <typename T> struct BIT {
int n;
vector<T> bit, ary;
BIT(int n = 0) : n(n), bit(n + 1), ary(n) {}
T operator[](int k) { return ary[k]; }
// [0, i)
T sum(int i) {
T res = 0;
for (; i > 0; i -= (i & -i)) {
res += bit[i];
}
return res;
}
// [l, r)
T sum(int l, int r) { return sum(r) - sum(l); }
void add(int i, T a) {
ary[i] += a;
i++;
for (; i <= n; i += (i & -i)) {
bit[i] += a;
}
}
};
void slv() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<BIT<int>> bit_memo(n);
// [l, r) の転倒数と左端を始点としたBITを返す
auto calc = [&](int l, int r) -> pair<ll, BIT<int>> {
// 座圧
vector<int> z(r - l);
for (int i = l; i < r; ++i) {
z[i - l] = a[i];
}
sort(z.begin(), z.end());
z.erase(unique(z.begin(), z.end()), z.end());
for (int i = l; i < r; ++i) {
a[i] = lower_bound(z.begin(), z.end(), a[i]) - z.begin();
}
ll inv = 0;
BIT<int> bit(z.size());
for (int i = l; i < r; ++i) {
inv += (i - l - bit.sum(a[i] + 1));
bit.add(a[i], 1);
}
return {inv, bit};
};
// setで区間を管理 [l, r)
set<pair<int, int>> st;
st.insert({0, n});
// 転倒数の値を管理
multiset<ll> mst;
// 初期化
auto init = calc(0, n);
mst.insert(init.first);
bit_memo[0] = init.second;
for (int i = 0; i < n; ++i) {
ll val = *mst.rbegin();
mst.erase(mst.find(val));
cout << val << " ";
ll mid;
cin >> mid;
mid = (mid ^ val) - 1;
auto it = st.lower_bound({mid, 1e9});
auto [l, r] = *(--it);
st.erase(it);
// 左端を消す場合
if (l == mid) {
if (mid + 1 != r) {
val -= bit_memo[l].sum(a[l]);
bit_memo[l].add(a[l], -1);
swap(bit_memo[l], bit_memo[l + 1]);
st.insert({l + 1, r});
mst.insert(val);
}
continue;
}
// 右端を消す場合
if (mid + 1 == r) {
val -= (r - l) - bit_memo[l].sum(a[r - 1] + 1);
bit_memo[l].add(a[r - 1], -1);
st.insert({l, r - 1});
mst.insert(val);
continue;
}
// 区間が2つに分かれる場合
if (mid - l <= r - mid) {
for (int j = l; j <= mid; ++j) {
val -= bit_memo[l].sum(a[j]);
bit_memo[l].add(a[j], -1);
}
swap(bit_memo[l], bit_memo[mid + 1]);
st.insert({mid + 1, r});
mst.insert(val);
auto nxt = calc(l, mid);
bit_memo[l] = nxt.second;
st.insert({l, mid});
mst.insert(nxt.first);
} else {
for (int j = r - 1; j >= mid; --j) {
val -= (j + 1 - l) - bit_memo[l].sum(a[j] + 1);
bit_memo[l].add(a[j], -1);
}
st.insert({l, mid});
mst.insert(val);
auto nxt = calc(mid + 1, r);
bit_memo[mid + 1] = nxt.second;
st.insert({mid + 1, r});
mst.insert(nxt.first);
}
}
cout << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
slv();
}
}
詳細信息
Test #1:
score: 0
Runtime Error
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