UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#206311#3700. 火柴排队Allen123456hello100114ms5108kbC++111.1kb2024-07-21 19:08:342024-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'