QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #687863 | #6434. Paimon Sorting | xinlengweishang | WA | 207ms | 10040kb | C++20 | 1.6kb | 2024-10-29 21:38:33 | 2024-10-29 21:38:34 |
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);
}
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;
build(1,1,n);
printf("%d",0);
change(1,a[1],1,n);
for(int i=2;i<=n;i++){
if(a[i]<maxn){
int tt=find(1,a[i]+1,n,1,n);
// printf(" %d %d %d\n",i,a[i],tt);
ans+=tt;
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
*/
/*
1
19
10 13 8 8 11 18 12 9 15 19 6 13 11 11 17 9 14 2 18
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5888kb
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: 207ms
memory: 10040kb
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 21 23 24 28 30 36 40 49 0 0 0 0 1 1 0 2 4 6 9 9 9 11 15 19 25 31 33 36 40 44 53 0 0 3 0 1 3 5 8 10 14 0 1 3 4 6 9 9 0 1 1 3 6 10 ...
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 21 23 24 28 30 36 40 49'