ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#206311 | #3700. 火柴排队 | Allen123456hello | 100 | 114ms | 5108kb | C++11 | 1.1kb | 2024-07-21 19:08:34 | 2024-07-21 20:03:54 |
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=99999997;
LL nixudui=0;
struct nd{
LL num,id;
bool operator<(const nd& a) const{return num<a.num;}
}arr[100005],brr[100005];
int n,a[100005],tmp[100005];
void merge(int l,int m,int r){
int L=l,R=m+1,pos=0;
while (L<=m||R<=r){
if (R>r){tmp[++pos]=a[L++];}
else if (L<=m&&a[L]>a[R]){
(nixudui+=r+1-R)%=mod;
tmp[++pos]=a[L++];
}else{
tmp[++pos]=a[R++];
}
}
for (int i=l;i<=r;++i){
a[i]=tmp[i-l+1];
}
}
void mergesort(int l,int r){
if (l>=r){return;}
int mid=(l+r)>>1;
mergesort(l,mid);
mergesort(mid+1,r);
merge(l,mid,r);
return;
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;++i){scanf("%lld",&arr[i].num);arr[i].id=i;}
for (int i=1;i<=n;++i){scanf("%lld",&brr[i].num);brr[i].id=i;}
sort(arr+1,arr+1+n);
sort(brr+1,brr+1+n);
for (int i=1;i<=n;++i){a[brr[i].id]=arr[i].id;}
mergesort(1,n);
printf("%lld",nixudui);
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1220kb
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: 1224kb
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: 1ms
memory: 1236kb
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: 1256kb
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: 1408kb
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: 4ms
memory: 1608kb
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: 7ms
memory: 2000kb
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: 35ms
memory: 3168kb
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: 63ms
memory: 5108kb
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'