QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#187813#7108. CouleurUrgantTeam#AC ✓2263ms22228kbC++234.7kb2023-09-24 23:58:002023-09-24 23:58:01

Judging History

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

  • [2023-09-24 23:58:01]
  • 评测
  • 测评结果：AC
  • 用时：2263ms
  • 内存：22228kb
查看
  • [2023-09-24 23:58:00]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;
using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef tree <pair <int, int>, null_type, less <pair <int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int mas[100005];
set <pair <int, int> > left_bounds;
set <pair <ll, int> > inv;
int quant = 0;
pair <int, int> segments[100005];
ll inversions[100005];
ordered_set sort_ord[100005];

ll get_answer(int n)
{
 	return (*inv.rbegin()).x;
}

void update(int pos, int n)
{
	int num = (*prev(left_bounds.upper_bound(mp(pos, n + 1)))).y;
	//cout << "num: " << num << '\n';
	left_bounds.erase(mp(segments[num].x, num));
	inv.erase(mp(inversions[num], num));

 	if (segments[num].x == segments[num].y) return;

 	if (pos == segments[num].x)
 	{
 		sort_ord[num].erase(mp(mas[pos], pos));
 		inversions[num] -= sort_ord[num].order_of_key(mp(mas[pos], pos));
 		inv.insert(mp(inversions[num], num));
 		
 		segments[num].x++;
 		left_bounds.insert(mp(segments[num].x, num));
 		return; 	
 	}

 	if (pos == segments[num].y)
 	{
 		sort_ord[num].erase(mp(mas[pos], pos));
 		inversions[num] -= ((int) sort_ord[num].size() - sort_ord[num].order_of_key(mp(mas[pos], pos)));
 		inv.insert(mp(inversions[num], num));

 		segments[num].y--;
 		left_bounds.insert(mp(segments[num].x, num));
 		return;
 	}

 	int lef_seg = num, rig_seg = num;
 	sort_ord[num].erase(mp(mas[pos], pos));

 	++quant;
 	sort_ord[quant].clear();
 	inversions[quant] = 0;
 	//cout << pos << ' ' << segments[num].x << ' ' << segments[num].y << '\n';
 	if (pos - segments[num].x <= segments[num].y - pos)
 	{   
 	 	lef_seg = quant;

 		for (int i = pos - 1; i >= segments[num].x; i--)
 		{
 			sort_ord[rig_seg].erase(mp(mas[i], i));
 			inversions[lef_seg] += sort_ord[lef_seg].order_of_key(mp(mas[i], i));
 			sort_ord[lef_seg].insert(mp(mas[i], i));	
 		}                                 
 		inversions[rig_seg] -= inversions[lef_seg];
 		for (int i = pos - 1; i >= segments[num].x; i--)
 		{
 			inversions[rig_seg] -= sort_ord[rig_seg].order_of_key(mp(mas[i], i));
 		}
 		inversions[rig_seg] -= ((int) sort_ord[lef_seg].size() - sort_ord[lef_seg].order_of_key(mp(mas[pos], pos))) + 
 								sort_ord[rig_seg].order_of_key(mp(mas[pos], pos));
 	}
 	else
 	{
 	 	rig_seg = quant;

 	 	for (int i = segments[num].y; i > pos; i--)
 		{
 			sort_ord[lef_seg].erase(mp(mas[i], i));
 			inversions[rig_seg] += sort_ord[rig_seg].order_of_key(mp(mas[i], i));
 			sort_ord[rig_seg].insert(mp(mas[i], i));	
 		}                                 
 		inversions[lef_seg] -= inversions[rig_seg];
 		for (int i = segments[num].y; i > pos; i--)
 		{
 			inversions[lef_seg] -= ((int) sort_ord[lef_seg].size() - sort_ord[lef_seg].order_of_key(mp(mas[i], i)));
 		}
 		inversions[lef_seg] -= ((int) sort_ord[lef_seg].size() - sort_ord[lef_seg].order_of_key(mp(mas[pos], pos))) + 
 								sort_ord[rig_seg].order_of_key(mp(mas[pos], pos));
 	}

 	int L = segments[num].x, R = segments[num].y;
 	segments[lef_seg] = mp(L, pos - 1);
 	segments[rig_seg] = mp(pos + 1, R);
 	left_bounds.insert(mp(segments[lef_seg].x, lef_seg));
 	left_bounds.insert(mp(segments[rig_seg].x, rig_seg));
 	inv.insert(mp(inversions[lef_seg], lef_seg));
 	inv.insert(mp(inversions[rig_seg], rig_seg));
 	return;
}

ll calc_inversion(int n)
{
	ll ans = 0;
	for (int i = n; i >= 1; i--)
	{
		ans += sort_ord[quant].order_of_key(mp(mas[i], i));
		sort_ord[quant].insert(mp(mas[i], i));	 	
	}
	return ans;
}

int main()
{
 	//freopen("input.txt", "r", stdin);
 	//freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);

	int test;
	cin >> test;

	for (int rep = 1; rep <= test; rep++)
	{
	 	int n;
	 	cin >> n;

	 	for (int i = 1; i <= n; i++) cin >> mas[i];

	 	left_bounds.clear();
	 	inv.clear();
	 	quant = 0;
	 	left_bounds.insert(mp(1, ++quant));
	 	segments[quant] = mp(1, n);
   		sort_ord[quant].clear();
	 	inversions[quant] = calc_inversion(n);
	 	inv.insert(mp(inversions[quant], quant));

	 	for (int i = 1; i <= n; i++)
	 	{
	 	 	//for (const auto &[in, num] : inv) cout << "[" << in << ", " << num << "], ";
	 	 	//cout << '\n';
	 	 	//for (int j = 1; j <= quant; j++) cout << "[" << segments[j].x << ", " << segments[j].y << "], ";
	 	 	//cout << '\n';
	 	 	
	 	 	ll nxt;
	 	 	cin >> nxt;

	 	 	ll ans = get_answer(n);
	 	 	cout << ans;
	 	 	if (i != n) cout << ' ';
	 	 	else cout << '\n';

	 	 	nxt ^= ans;
	 	 	update(nxt, n);
	 	}
	}

	return 0;
}
源文件, 语言: C++23

这程序好像有点Bug，我给组数据试试？

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 12940kb

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: 0
Accepted
time: 2263ms
memory: 22228kb

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:

ok 11116 lines

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

伺服器時間: 2024-12-03 04:13:53 | 開源專案