QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#624734	#6434. Paimon Sorting	GepiWang	WA	102ms	5136kb	C++23	2.2kb	2024-10-09 16:31:54	2024-10-09 16:31:55

Judging History

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

[2024-10-09 16:31:55]
评测

测评结果：WA
用时：102ms
内存：5136kb

查看

[2024-10-09 16:31:54]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int, int>
const int N = 1e5 + 5;
const int M = 1e5 + 5;
const int INF = 1e18 + 10;

int n;
int tr[N];

int lowbit(int x) { return x & -x; }

void add(int x, int d)
{
    while (x <= n)
    {
        tr[x] += d;
        x += lowbit(x);
    }
}

int ask(int x)
{
    int res = 0;
    while (x)
    {
        res += tr[x];
        x -= lowbit(x);
    }
    return res;
}

void solve()
{
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        tr[i] = 0;
    }

    int mx = a[1];
    cout << 0;
    if (n != 1)
        cout << " ";
    int ans = 0;

    vector<bool> st(n + 1);
    st[a[1]] = true;
    add(a[1], 1);
    for (int i = 2; i <= n; i++)
    {
        if (a[i] > mx)
        {
            if (ans == 0)
                ans = i;
            else
                ans += 2;
        }
        else
        {
            int res = ask(n) - ask(a[i]);
            ans += res;
        }

        mx = max(mx, a[i]);
        if (!st[a[i]])
        {
            st[a[i]] = true;
            add(a[i], 1);
        }
        cout << ans;
        if (i != n)
            cout << " ";
    }
    cout << endl;

    // for (int i = 1; i <= n; i++)
    // {
    //     vector<int> b(i + 1);
    //     for (int j = 1; j <= i; j++)
    //         b[j] = a[j];
    //     int res = 0;

    //     // cout << i << ": " << endl;
    //     for (int l = 1; l <= i; l++)
    //     {
    //         for (int r = 1; r <= i; r++)
    //         {
    //             if (b[l] < b[r])
    //             {
    //                 swap(b[l], b[r]);
    //                 res++;
    //             }
    //         }
    //         // for (int r = 1; r <= i; r++)
    //         //     cout << b[r] << " ";
    //         // cout << endl;
    //     }
    //     cout << res << " ";
    // }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

/*
1
14
2 2 4 1 5 8 2 3 3 4 4 1 1 5

1
6
2 2 4 1 3 5
*/

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3492kb

input:

output:

0 2 3 5 7
0 2 4
0

result:

ok 3 lines

Test #2:

score: -100

Wrong Answer

time: 102ms

memory: 5136kb

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 3
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'