QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#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

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

[2024-11-05 20:29:54]
评测

测评结果：WA
用时：96ms
内存：6760kb

查看

[2024-11-05 20:29:53]
提交

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
*/

源文件, 语言: C++23

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 5872kb

input:

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'