QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#625712 | #6434. Paimon Sorting | Yurily | WA | 1ms | 3772kb | C++20 | 1.4kb | 2024-10-09 20:36:30 | 2024-10-09 20:36:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e5+5;
int sum[MAX*4];
int n,a[MAX];
bool flag[MAX];
int d[MAX];
long long ans1,ans2;
void modify(int k,int l,int r,int x){
if(r<x||l>x)
return;
if(l==r&&l==x){
if(!sum[k])
sum[k]=1;
return;
}
int mid=l+r>>1;
modify(k<<1,l,mid,x);
modify(k<<1|1,mid+1,r,x);
sum[k]=sum[k<<1]+sum[k<<1|1];
}
int query(int k,int l,int r,int x,int y){
if(y<l||x>r)
return 0;
if(l>=x&&r<=y)
return sum[k];
int mid=l+r>>1;
int res=0;
res=query(k<<1,l,mid,x,y);
res+=query(k<<1|1,mid+1,r,x,y);
return res;
}
// 快读
int read(){
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-'){
f = -1;
}
c = getchar();
}
while(c >= '0' && c <= '9'){
x = x*10+c-'0';
c = getchar();
}
return x*f;
}
void solve(){
n=read();
memset(sum,0,sizeof(int)*(n*4+1));
for(int i=1;i<=n;++i)
a[i]=read();
ans1=ans2=-1;
flag[1]=1;
int pre=1;
for(int i=2;i<=n;++i){
if(a[i]>a[pre]){
d[i]=d[pre]+1;
flag[i]=1;
pre=i;
}
}
for(int i=1;i<=n;++i){
if(flag[i]){
ans1=d[i];
ans2++;
}
else{
if(a[i]+1<=n){
ans2+=query(1,1,n,a[i]+1,n);
// cout<<i<<" "<<query(1,1,n,a[i]+1,n)<<endl;
}
}
modify(1,1,n,a[i]);
printf("%lld ",ans1+ans2);
}
printf("\n");
}
int main(){
int T;
cin>>T;
while(T--){
solve();
}
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3772kb
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:
wrong answer 1st lines differ - expected: '0 2 3 5 7', found: '0 2 3 5 7 '