ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#206275 | #3700. 火柴排队 | hujunyi66 | 100 | 130ms | 3548kb | C++ | 756b | 2024-07-21 18:20:40 | 2024-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'