QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#625712#6434. Paimon SortingYurilyWA 1ms3772kbC++201.4kb2024-10-09 20:36:302024-10-09 20:36:31

Judging History

你现在查看的是最新测评结果

  • [2024-10-09 20:36:31]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3772kb
  • [2024-10-09 20:36:30]
  • 提交

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 '