UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#206275#3700. 火柴排队hujunyi66100130ms3548kbC++756b2024-07-21 18:20:402024-07-21 20:01:54

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005,mod=99999997;
int A[N],B[N],a[N],b[N],l[N],c[5*N];
ll ans;
int n;
void add(int x,int y)
{
	for(;x<=n;x+=x&-x) c[x]+=y;
}
int ask(int x)
{
	ll ans=0;
	for(;x;x-=x&-x) ans+=c[x];
	return ans;
}
bool cmp1(int i,int j){
	return A[i]<A[j];
}
bool cmp2(int i,int j){
	return B[i]<B[j];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&A[i]),a[i]=i;
	for(int i=1;i<=n;++i) scanf("%d",&B[i]),b[i]=i;
	sort(a+1,a+1+n),sort(b+1,b+1+n);
	sort(a+1,a+1+n,cmp1),sort(b+1,b+1+n,cmp2);
	for(int i=1;i<=n;++i) l[a[i]]=b[i];
	for(int i=n;i;i--)
{
		ans=(ans+ask(l[i]-1))%mod;
		add(l[i],1);	
	}
	printf("%lld",ans%mod);
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 1228kb

input:

10
10 1 5 2 7 4 9 3 6 8
7 5 1 8 10 4 6 2 3 9

output:

18

result:

ok single line: '18'

Test #2:

score: 10
Accepted
time: 0ms
memory: 1228kb

input:

50
41 29 19 46 13 28 47 17 45 4 34 14 37 7 30 24 27 9 11 15 50 8 39 32 3 42 10 16 31 6 1 43 21 36 2 ...

output:

540

result:

ok single line: '540'

Test #3:

score: 10
Accepted
time: 0ms
memory: 1224kb

input:

100
99 6 48 29 62 84 91 41 4 25 71 90 53 38 80 30 65 52 35 94 97 89 27 28 23 36 59 40 12 21 13 60 44...

output:

2546

result:

ok single line: '2546'

Test #4:

score: 10
Accepted
time: 0ms
memory: 1232kb

input:

500
469 1 475 414 470 87 323 138 390 500 14 86 289 374 9 130 171 70 166 407 145 250 256 238 356 380 ...

output:

60636

result:

ok single line: '60636'

Test #5:

score: 10
Accepted
time: 0ms
memory: 1248kb

input:

1000
862 417 848 334 434 61 919 162 893 972 179 144 502 83 750 457 908 150 264 45 564 771 312 84 559...

output:

259816

result:

ok single line: '259816'

Test #6:

score: 10
Accepted
time: 4ms
memory: 1332kb

input:

5000
4361 1 4216 1620 1548 146 3343 330 263 4996 4893 70 3053 833 579 4999 507 3890 547 3946 1895 40...

output:

6225256

result:

ok single line: '6225256'

Test #7:

score: 10
Accepted
time: 7ms
memory: 1452kb

input:

10000
9328 868 9128 1330 1883 2321 5754 10 9609 6604 2514 5 5178 7488 3971 9170 7605 3044 916 1426 7...

output:

24906204

result:

ok single line: '24906204'

Test #8:

score: 10
Accepted
time: 11ms
memory: 1688kb

input:

20000
18271 950 12480 16977 14282 14658 12427 4142 6276 19576 17366 17604 5713 1635 10966 12013 1459...

output:

99902736

result:

ok single line: '99902736'

Test #9:

score: 10
Accepted
time: 33ms
memory: 2388kb

input:

50000
48199 3134 33319 30418 34414 7392 29871 41472 11673 33938 34985 37354 5549 25811 13334 29512 7...

output:

23190504

result:

ok single line: '23190504'

Test #10:

score: 10
Accepted
time: 75ms
memory: 3548kb

input:

100000
82112 75046 5985 34284 96873 1220 23850 81070 16197 95848 47020 49570 57518 89281 68914 4491 ...

output:

97187296

result:

ok single line: '97187296'