QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#590930#7108. CouleurfengRE 6ms52104kbC++202.9kb2024-09-26 13:08:422024-09-26 13:08:42

Judging History

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

  • [2024-09-26 13:08:42]
  • 评测
  • 测评结果:RE
  • 用时:6ms
  • 内存:52104kb
  • [2024-09-26 13:08:42]
  • 提交

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;
vector<int> A(maxn + 5), p(maxn + 5);
set<int> pos;
int idx = 0;
struct node {
	int ch[2];
	int s;
};
vector<node> tree(maxn * 20 + 5);
vector<int> root(maxn + 5);
//vector<int> test(maxn);
map<int, 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 (u > v) 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);
	mp[1] = now;
	mp[n] = 0;
	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;
		ll old = mp[l];
		s.erase(s.find(old));
		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) {
			//枚举右边
			ll a = 0;
			for (int i = x + 1; i < r; ++i) {
				if (A[i] == 1) continue;
				a += query(root[i], root[r], 1, n, 1, A[i] - 1);
			}
			for (int i = x + 1; i <= r; ++i) {
				if (A[i] == n) continue;
				sum += query(root[l - 1], root[x - 1], 1, n, A[i] + 1, n);
			}
			mp[x + 1] = a;
			mp[l] = mp[l] - a - sum;
			s.insert(mp[l]);
			s.insert(mp[x + 1]);
		}
		else {
			ll a = 0;
			for (int i = l; i < x - 1; ++i) {
				if (A[i] == 1) continue;
				a += query(root[i], root[x - 1], 1, n, 1, A[i] - 1);
			}
			for (int i = l; i <= x - 1; ++i) {
				if (A[i] == 1) continue;
				sum += query(root[x], root[r], 1, n, 1, A[i] - 1);
			}
			mp[l] = a;
			mp[x + 1] = old - a - sum;
			s.insert(mp[l]);
			s.insert(mp[x + 1]);
		}
		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: 6ms
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 ...

result: