QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #216074 | #6434. Paimon Sorting | veg# | WA | 111ms | 4720kb | C++14 | 668b | 2023-10-15 15:33:38 | 2023-10-15 15:33:39 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int n,c[N],a[N];
bool fl[N];
void add(int x) {
for(;x;x-=x&-x) ++c[x];
}
int ask(int x) {
int ret=0;
for(;x<=n;x+=x&-x) ret+=c[x];
return ret;
}
int main() {
int T;scanf("%d",&T);
while(T--) {
scanf("%d",&n);
for(int i=1;i<=n;++i) c[i]=fl[i]=0;
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
int mx=a[1];
putchar('0');
ll ans=0;
for(int i=2;i<=n;++i) {
if(mx<a[i]) {
ans+=2; mx=a[i];
} else {
ans+=ask(a[i]+1);
}
if(!fl[a[i]]) {
add(a[i]);
fl[a[i]]=1;
}
printf(" %lld",ans);
}
puts("");
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3852kb
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: 111ms
memory: 4720kb
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 3 4 5 7 9 13 14 16 24 27 32 37 39 46 50 61 62 0 2 4 6 6 8 10 14 17 18 22 25 0 0 1 3 4 5 8 13 19 23 23 28 30 34 39 39 0 0 2 4 6 8 10 15 17 21 0 0 2 2 3 6 8 10 13 15 17 19 20 24 26 32 36 44 0 0 0 0 0 0 0 2 3 4 6 6 6 7 10 12 17 22 24 27 31 35 44 0 0 2 0 0 2 3 5 6 9 0 0 2 3 5 8 8 0 0 0 2 4 8 10 16 1...
result:
wrong answer 1st lines differ - expected: '0 2 4 6 7 9 11 16 17 19 28 31 36 41 43 51 55 67 68', found: '0 2 3 4 5 7 9 13 14 16 24 27 32 37 39 46 50 61 62'