QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#180768	#6434. Paimon Sorting	0x4F5DA2	WA	132ms	3484kb	C++14	1.3kb	2023-09-16 12:08:48	2023-09-16 12:08:48

Judging History

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

[2023-09-16 12:08:48]
评测

测评结果：WA
用时：132ms
内存：3484kb

查看

[2023-09-16 12:08:48]
提交

answer

#include <cstdio>

const int maxn = 100000;
int n;
int a[maxn + 10];
long long tree[maxn + 10];
int lowbit(int x){
	return (x & (-x));
}
void add_n(int p){
	while(p <= n){
		++tree[p];
		p = p + lowbit(p);
	}
	return ;
}
long long query_n(int p){
	long long ans = 0;
	while(p > 0){
		ans = ans + tree[p];
		p = p - lowbit(p);
	}
	return ans;
}
long long query_s(int l, int r){
	return query_n(r) - query_n(l - 1);
}

long long sum[maxn + 10];

int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		scanf("%d", &n);
		for(int i = 1; i <= n; ++i){
			scanf("%d", &a[i]);
			sum[i] = query_s(a[i] + 1, n);
			if(query_s(a[i], a[i]) == 0){
				add_n(a[i]);
			}
		}
		/*for(int i = 1; i <= n; ++i){
			printf("%d\n", sum[i]);
		}*/
		putchar('0');
		if(n != 1)
			putchar(' ');
		else
			putchar('\n');
		int pre_num = a[1];
		int eql_num = 0;
		int pre_eql = 0;
		long long ans = 0;
		for(int i = 2; i <= n; ++i){
			if(a[i] == pre_num){
				++pre_eql;
			}
			if(a[i] > pre_num){
				eql_num = eql_num + pre_eql;
				pre_eql = 0;
				ans = ans + 2;
				pre_num = a[i];
			}
			ans = ans + sum[i];
			printf("%lld", ans + eql_num);
			if(i != n)
				putchar(' ');
			else
				putchar('\n');
		}
		
		for(int i = 1; i <= n; ++i){
			tree[i] = 0;
		}
		
	}
	return 0;
} 
/*
1
7
2 1 2 3 2 3 4
*/

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 1624kb

input:

output:

0 2 3 5 7
0 2 4
0

result:

ok 3 lines

Test #2:

score: -100

Wrong Answer

time: 132ms

memory: 3484kb

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'