QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#300813 | #6434. Paimon Sorting | JooDdae | WA | 0ms | 3508kb | C++20 | 942b | 2024-01-08 20:50:43 | 2024-01-08 20:50:43 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// find_by_order(K) = K번째 수(0 base), order_of_key(K) = K보다 작은 수의 개수, less -> less_equal to multiset, change null_type to map
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using pbds = tree <int, int, less<>, rb_tree_tag, tree_order_statistics_node_update>;
int n, a[100100];
int main() {
cin.tie(0)->sync_with_stdio(0);
int tc; cin >> tc;
while(tc--) {
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
pbds mp;
int L = 1;
ll ans = 0;
for(int i=1;i<=n;i++) {
mp[-a[i]]++;
if(a[i] > a[1]) {
ans += i-L, L = i+1;
swap(a[i], a[1]);
}
ans += mp.order_of_key(-a[i]);
cout << ans << " \n"[i == n];
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3508kb
input:
3 5 2 3 2 1 5 3 1 2 3 1 1
output:
0 2 3 5 8 0 2 3 0
result:
wrong answer 1st lines differ - expected: '0 2 3 5 7', found: '0 2 3 5 8'