QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #687804 | #6434. Paimon Sorting | xinlengweishang | WA | 187ms | 7216kb | C++20 | 1.5kb | 2024-10-29 21:22:01 | 2024-10-29 21:22:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define N 200005
struct node{
int l,r;
int sum;
}tree[N*16];
int node_cnt=0;
int rt[N],a[N],b[N];
void build(int p,int l,int r){
tree[p].l=l;
tree[p].r=r;
tree[p].sum=0;
if(l==r) return ;
int mid=(l+r)>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
return ;
}
int change(int p,int k,int l,int r){
if(l==r){
if(tree[p].sum==0){
tree[p].sum=1;
return 1;
}
return 0;
}
int mid=(l+r)>>1;
if(mid>=k){
int temp=change(p*2,k,l,mid);
if(temp) tree[p].sum++;
return temp;
}
else{
int temp=change(p*2+1,k,mid+1,r);
if(temp) tree[p].sum++;
return temp;
}
}
int find(int p,int fl,int fr,int l,int r){
int ans=0;
if(l>=fl&&r<=fr){
return tree[p].sum;
}
int mid=(l+r)>>1;
if(mid>fl){
ans+=find(p*2,fl,fr,l,mid);
}
else{
ans+=find(p*2+1,fl,fr,mid+1,r);
}
return ans;
}
void slove(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
int maxn=a[1],maxnum=1;
int ans=0;
printf("%d",0);
change(1,a[1],1,n);
for(int i=2;i<=n;i++){
if(a[i]<maxn){
ans+=find(1,a[i],n,1,n);
change(1,a[i],1,n);
}
else if(a[i]==maxn){
maxnum++;
}
else {
ans+=maxnum;
ans++;
maxn=a[i];
maxnum=1;
change(1,a[i],1,n);
}
printf(" %d",ans);
}
printf("\n");
return ;
}
int main(){
int T;
scanf("%d",&T);
while(T--) slove();
return 0;
}
/*
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: 5816kb
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: 187ms
memory: 7216kb
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 8 9 10 12 15 16 22 28 30 32 33 33 35 0 2 4 4 4 4 13 28 30 34 36 45 0 4 5 7 11 13 15 16 18 27 27 31 35 44 48 48 0 2 4 6 8 10 19 36 45 49 0 4 6 6 7 8 17 26 30 39 42 44 46 55 57 59 60 61 0 0 0 0 17 17 0 2 4 13 15 15 15 24 28 32 34 36 40 44 46 48 49 0 0 3 0 17 19 28 32 41 58 0 17 19 28 30 34...
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 8 9 10 12 15 16 22 28 30 32 33 33 35'