QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #687936 | #6434. Paimon Sorting | xinlengweishang | AC ✓ | 200ms | 14148kb | C++20 | 2.0kb | 2024-10-29 21:59:40 | 2024-10-29 21:59:41 |
Judging History
answer
#include<bits/stdc++.h>
#define N 200005
#define ll long long
using namespace std;
struct node{
ll l,r;
ll sum;
}tree[N*16];
ll node_cnt=0;
ll rt[N],a[N],b[N];
void build(ll p,ll l,ll r){
tree[p].l=l;
tree[p].r=r;
tree[p].sum=0;
if(l==r) return ;
ll mid=(l+r)>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
return ;
}
ll change(ll p,ll k,ll l,ll r){
if(l==r){
if(tree[p].sum==0){
tree[p].sum=1;
return 1;
}
return 0;
}
ll mid=(l+r)>>1;
if(mid>=k){
ll temp=change(p*2,k,l,mid);
if(temp) tree[p].sum++;
return temp;
}
else{
ll temp=change(p*2+1,k,mid+1,r);
if(temp) tree[p].sum++;
return temp;
}
}
ll find(ll p,ll fl,ll fr,ll l,ll r){
// printf(" %lld %lld %lld %lld %lld\n",p,fl,fr,l,r);
ll ans=0;
if(l>=fl&&r<=fr){
return tree[p].sum;
}
ll 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(){
ll n;
scanf("%lld",&n);
for(ll i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
ll maxn=a[1],maxnum=1,maxsite=0;
ll ans=0;
build(1,1,n);
printf("%lld",0ll);
change(1,a[1],1,n);
for(ll i=2;i<=n;i++){
if(a[i]<maxn){
ll 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(" %lld",ans);
}
printf("\n");
return ;
}
int main(){
ll T;
scanf("%lld",&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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7980kb
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: 0
Accepted
time: 200ms
memory: 14148kb
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:
ok 6107 lines