QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #713768 | #6434. Paimon Sorting | tieguodundae | WA | 96ms | 6760kb | C++23 | 3.0kb | 2024-11-05 20:29:53 | 2024-11-05 20:29:54 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", print_args(__VA_ARGS__)
template <class... T>
void print_args(T... args) { ((cerr << args << ' '), ...) << '\n'; }
typedef long long ll;
const int mod = 998244353;
const int inf = 1e9;
const ll INF = 1e18;
const int N = 2E5 + 10;
int n, a[N], d[N], cnt[N], ans = 0;
void add(int x) {
for (int i = x; i <= n; i += (i & (-i))) {
d[i]++;
}
}
int sum(int x) {
int res = 0;
for (int i = x; i; i -= (i & (-i))) {
res += d[i];
}
return res;
}
void _() {
add(a[1]), cnt[a[1]] = 1;
int maxx = a[1];
for (int i = 1; i <= n; i++) {
if (a[i] > maxx) {
ans += 2;
maxx = a[i];
} else if (a[i] < maxx) {
int t = sum(n) - sum(a[i]);
ans += sum(n) - sum(a[i]);
}
if (!cnt[a[i]]) add(a[i]), cnt[a[i]] = 1;
cout << ans << " \n"[i == n];
}
}
void input() {
cin >> n;
for (int i = 1; i <= n; i++) {
d[i] = 0;
cnt[i] = 0;
}
ans = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
}
void sol();
void brute_force() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int k = 1; k <= n; k++) {
int cnt = 0;
vector b = a;
for (int i = 1; i <= k; i++) {
for (int j = 1; j <= k; j++) {
if (b[i] < b[j]) {
swap(b[i], b[j]);
debug(i, j);
cnt++;
}
}
}
cerr << cnt << '\n';
}
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
// brute_force();
int _ = 1;
cin >> _;
while (_--) {
sol();
}
return 0;
}
void sol() {
input(); _();
}
/*
[i, j]: 1 3
[i, j]: 1 4
[i, j]: 1 5
[i, j]: 2 1
[i, j]: 3 2
[i, j]: 4 3
[i, j]: 5 4
[i, j]: 1 2
[i, j]: 1 3
[i, j]: 1 4
[i, j]: 1 5
[i, j]: 2 1
[i, j]: 3 2
[i, j]: 4 3
[i, j]: 5 4
[i, j]: 1 4
[i, j]: 1 5
[i, j]: 2 1
[i, j]: 3 1
[i, j]: 3 2
[i, j]: 4 3
[i, j]: 5 4
//正序
1 2
1 3
1 4
1 5
2 1
3 2
4 3
5 4
...
k k - 1
逆序:
删掉正序的情况+逆序对数
2 1 3 4 5
[i, j]: 1 3
[i, j]: 1 5
[i, j]: 2 1
[i, j]: 3 2
[i, j]: 4 3
[i, j]: 5 4
[i, j]: 3 1
[i, j]: 4 1
[i, j]: 4 2
[i, j]: 1 5
[i, j]: 2 1
[i, j]: 3 2
[i, j]: 4 3
[i, j]: 5 4
[i, j]: 3 1
[i, j]: 4 1
[i, j]: 4 2
[i, j]: 5 1
[i, j]: 5 2
[i, j]: 5 3
[i, j]: 2 1
[i, j]: 3 2
[i, j]: 4 3
[i, j]: 5 4
ans = k - 1 + 逆序对数 - 已经在k - 1中的逆序对数 + a[1] 和其它数的对比
[i, j]: 5 3
[i, j]: 1 2
[i, j]: 1 3
[i, j]: 2 1
[i, j]: 3 2
[i, j]: 4 3
[i, j]: 5 4
3
5
2 3 2 1 5
3
1 2 3
1
1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5872kb
input:
3 5 2 3 2 1 5 3 1 2 3 1 1
output:
0 2 3 5 7 0 2 4 0
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 96ms
memory: 6760kb
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 20 22 23 27 29 35 39 48 0 0 0 0 1 1 0 2 4 6 9 9 9 11 15 17 23 29 31 34 38 42 51 0 0 2 0 1 3 5 8 10 14 0 1 3 4 6 9 9 0 1 1 3 5 9 1...
result:
wrong answer 5th lines differ - expected: '0 1 3 3 4 8 10 12 16 18 27 29 30 34 36 42 46 55', found: '0 1 3 3 4 8 10 12 16 18 20 22 23 27 29 35 39 48'