QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#591331 | #7108. Couleur | feng | RE | 3ms | 52104kb | C++20 | 3.2kb | 2024-09-26 15:26:24 | 2024-09-26 15:26:25 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define endl '\n'
#define PII pair<int,int>
using namespace std;
const int maxn = 1e5;
const int mod = 998244353;
vector<int> A(maxn + 5), p(maxn + 5);
set<int> pos;
int idx = 0;
struct node {
int ch[2] = { 0,0 };
int s = 0;
};
vector<node> tree(maxn * 20 + 5);
vector<int> root(maxn + 5);
map<PII, ll> mp;
multiset<ll> s;
void insert(int x, int& y, int num, int l, int r) {
y = ++idx;
tree[y] = tree[x];
tree[y].s++;
if (l == r) return;
int mid = l + r >> 1;
if (num <= mid) insert(tree[x].ch[0], tree[y].ch[0], num, l, mid);
else insert(tree[x].ch[1], tree[y].ch[1], num, mid + 1, r);
}
ll query(int x, int y, int l, int r, int u, int v) {
if (x == y) return 0;
if (u <= l && v >= r)
return tree[y].s - tree[x].s;
int mid = l + r >> 1;
ll sum = 0;
if (u <= mid) sum += query(tree[x].ch[0], tree[y].ch[0], l, mid, u, v);
if (v > mid) sum += query(tree[x].ch[1], tree[y].ch[1], mid + 1, r, u, v);
return sum;
}
void solve() {
s.clear();
pos.clear();
mp.clear();
int n; cin >> n;
for (int i = 1; i <= n; ++i) cin >> A[i];
for (int i = 1; i <= n; ++i) cin >> p[i];
int idx = 0;
for (int i = 1; i <= n; ++i)
insert(root[i - 1], root[i], A[i], 1, n);
ll now = 0;
int l = 1, r = n;
for (int i = 1; i < n; ++i) {
if (A[i] == 1) continue;
now += query(root[i], root[n], 1, n, 1, A[i] - 1);
}
s.insert(now);
s.insert(0);
mp[{1, n}] = now;
pos.insert(0);
pos.insert(n + 1);
cout << now;
for (int i = 1; i < n; ++i) {
int x = now ^ p[i];
auto it = pos.lower_bound(x);
r = *it;
l = *prev(it);
l++; r--;
ll sum = 0;
if (A[x] != n) sum += query(root[l - 1], root[x - 1], 1, n, A[x] + 1, n);
if (A[x] != 1) sum += query(root[x], root[r], 1, n, 1, A[x] - 1);
if (x - l > r - x) {
//枚举右边
int a = 0;
for (int j = x + 1; j < r; ++j) {
if (A[j] == 1) continue;
a += query(root[j], root[r], 1, n, 1, A[j] - 1);
}
for (int j = x + 1; j <= r; ++j) {
if (A[j] == n) continue;
sum += query(root[l - 1], root[x - 1], 1, n, A[j] + 1, n);
}
if (x + 1 <= r) mp[{x + 1, r}] = a;
else mp[{x + 1, r}] = 0;
if (l <= x - 1) mp[{l, x - 1}] = mp[{l, r}] - mp[{x + 1, r}] - sum;
else mp[{l, x - 1}] = 0;
s.erase(s.find(mp[{l, r}]));
s.insert(mp[{l, x - 1}]);
s.insert(mp[{x + 1, r}]);
}
else {
int a = 0;
for (int j = l; j < x - 1; ++j) {
if (A[j] == 1) continue;
a += query(root[j], root[x - 1], 1, n, 1, A[j] - 1);
}
for (int j = l; j <= x - 1; ++j) {
if (A[j] == 1) continue;
sum += query(root[x], root[r], 1, n, 1, A[j] - 1);
}
if (l <= x - 1) mp[{l, x - 1}] = a;
else mp[{l, x - 1}] = 0;
if (x + 1 <= r) mp[{x + 1, r}] = mp[{l, r}] - mp[{l, x - 1}] - sum;
else mp[{x + 1, r}] = 0;
s.erase(s.find(mp[{l, r}]));
s.insert(mp[{l, x - 1}]);
s.insert(mp[{x + 1, r}]);
}
pos.insert(x);
now = *prev(s.end());
cout << " " << now;
}
cout << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
//cout << fixed << setprecision(2);
int T; cin >> T;
while (T--) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 52104kb
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 ...