QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #687929 | #6434. Paimon Sorting | xinlengweishang | WA | 202ms | 9968kb | C++20 | 2.0kb | 2024-10-29 21:58:14 | 2024-10-29 21:58:14 |
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){
// printf(" %d %d %d %d %d\n",p,fl,fr,l,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,maxsite=0;
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++;
if(maxnum==2) maxsite=i;
}
else {
ans+=maxnum;
ans++;
if(maxsite!=0){
ans+=i-maxsite-maxnum+1;
// printf("maxsite %d %d %d ",i,maxsite,maxnum);
}
// printf("%d %d",i,maxn);
maxsite=0;
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
*/
/*
5
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
17
11 15 3 10 7 15 15 10 5 17 3 3 14 13 11 11 2
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 6008kb
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: 202ms
memory: 9968kb
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 27 29 30 34 36 42 46 55 0 0 0 0 1 1 0 2 4 6 9 9 9 11 15 21 27 33 35 38 42 46 55 0 0 3 0 1 3 5 8 10 14 0 1 3 4 6 9 9 0 1 1 3 7 11 ...
result:
wrong answer 6104th lines differ - expected: '0 0 1 2 4 7 10 14 18 22 27 32 ...161222304 3161285479 3161348654', found: '0 0 1 2 4 7 10 14 18 22 27 32 ...3744992 -1133681817 -1133618642'