QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#626822	#6434. Paimon Sorting	Corzica	WA	108ms	6556kb	C++14	1.3kb	2024-10-10 13:20:35	2024-10-10 13:20:35

Judging History

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

[2024-10-10 13:20:35]
评测

测评结果：WA
用时：108ms
内存：6556kb

查看

[2024-10-10 13:20:35]
提交

answer

#include <bits/stdc++.h>
using namespace std;
int n, a[500005], qwe;
vector<pair<int, int>> changes;
int t[500005], ans[500005];
inline int lowbit(int p) {
	return p & -p;
}
inline void change(int p, int q, int flg = 1) {
	if (flg) changes.push_back(make_pair(p, q));
	while (p <= n) {
		t[p] += q;
		p += lowbit(p);
	}
}
inline int query(int p) {
	int cnt = 0;
	while (p) {
		cnt += t[p];
		p -= lowbit(p);
	}
	return cnt;
}
inline void clear() {
	for (pair<int, int> op : changes) {
		change(op.first, -op.second, 0);
	}
	changes.clear();
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> qwe;
	while (qwe--) {
		clear();
		cin >> n;
		for (int i = 1; i <= n; i++) cin >> a[i];
		int lst = 0, num = -1, lsts = 0, aans = 0, sum = 0, flg = 0;
		for (int i = 1; i <= n; i++) {
			if (query(a[i] - 1) == query(n)) {
				if (lst)aans += sum;
				lst = i, num++;
				sum = 0;
				flg = 0;
			} else if (a[i] < a[lst]) sum += 1 - flg;
			else flg = 1;
			ans[i] = ans[i - 1] + query(n) - query(a[i]);
			if (query(a[i]) == query(a[i] - 1)) change(a[i], 1);
			cout << ans[i] + num + (lst - 1) - aans ;
			if (i != n) cout << ' ';
			else cout << "\n";
		}
	}
}
//1
//18
//6 5 12 12 11 2 10 10 5 10 13 15 13 10 17 7 11 2

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 5644kb

input:

output:

0 2 3 5 7
0 2 4
0

result:

ok 3 lines

Test #2:

score: -100

Wrong Answer

time: 108ms

memory: 6556kb

input:

6107
19
10 13 8 8 11 18 12 9 15 19 6 13 11 11 17 9 14 2 18
12
1 8 10 2 10 2 6 1 5 9 5 7
16
14 4 2 15 12 14 10 3 2 9 15 4 12 9 5 15
10
3 2 5 6 7 8 6 1 6 4
18
6 5 12 12 11 2 10 10 5 10 13 15 13 10 17 7 11 2
1
1
2
1 1
3
2 1 2
17
11 15 3 10 7 15 15 10 5 17 3 3 14 13 11 11 2
3
2 2 3
7
6 1 7 5 3 5 1
7
2 1...

output:

0 2 4 6 7 9 11 16 17 19 28 31 36 41 43 51 55 67 68
0 2 4 6 6 8 10 14 17 18 22 25
0 1 3 5 7 8 11 16 22 26 26 31 33 37 42 42
0 1 3 5 7 9 11 17 19 23
0 1 3 3 4 8 10 12 16 18 27 29 30 34 36 42 46 55
0
0 0
0 1 1
0 2 4 6 9 9 9 11 15 21 27 33 35 38 42 46 55
0 0 3
0 1 3 5 8 10 14
0 1 3 4 6 9 9
0 1 1 3 7 11 ...

result:

wrong answer 6104th lines differ - expected: '0 0 1 2 4 7 10 14 18 22 27 32 ...161222304 3161285479 3161348654', found: '0 0 1 2 4 7 10 14 18 22 27 32 ...3744992 -1133681817 -1133618642'