UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#207552#3742. 排排序Allen123456hello100844ms5028kbC++11764b2024-07-29 14:42:232024-07-29 17:02:19

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL ans[200005];
int n,pos,brr[200005];
struct nd{
    int num,id;
    nd(int _num=0,int _id=0){num=_num;id=_id;}
    bool operator<(const nd& a) const{
        return num==a.num?id<a.id:num<a.num;
    }
}arr[200005];
int main(){
    int m,x,y;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i){scanf("%d",&arr[i].num);brr[i]=arr[i].num;arr[i].id=i;}
    sort(arr+1,arr+1+n);
    for (int i=1;i<=n;++i){ans[i]=lower_bound(arr+1,arr+1+n,nd(brr[i],0))-arr-1;}
    ++m;while (--m){
        scanf("%d%d",&x,&y);
        if (brr[x]>brr[y]){--ans[x];}
        if (brr[x]<brr[y]){--ans[y];}
    }
    for (int i=1;i<=n;++i){printf("%lld%c",ans[i]," \n"[i==n]);}
    return 0;
}

详细

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

Test #1:

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

input:

68 87
672247318 508774772 290746326 176428976 476886942 917833152 777797902 785151058 467283207 7739...

output:

45 35 21 11 33 61 52 53 33 51 20 17 4 39 43 25 26 40 12 37 62 0 28 53 64 10 22 19 45 43 36 1 30 53 6...

result:

ok 68 numbers

Test #2:

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

input:

53 70
59415795 789388430 66644621 639264350 492235826 838262724 429290911 468756919 688924005 793327...

output:

3 40 3 28 23 43 20 21 31 39 50 9 32 24 30 1 44 26 17 48 29 47 35 17 44 48 36 12 47 7 22 21 5 38 9 2 ...

result:

ok 53 numbers

Test #3:

score: 10
Accepted
time: 72ms
memory: 4800kb

input:

174111 1
279813522 906313758 857856003 210034707 11448887 481103816 592484284 431951955 436135357 40...

output:

48974 157928 149500 36936 2053 84191 103697 75671 76394 71360 79089 67154 35827 85894 1556 3479 4047...

result:

ok 174111 numbers

Test #4:

score: 10
Accepted
time: 66ms
memory: 4548kb

input:

152911 1
702306111 404797947 717879124 601798916 140665800 940013176 122317960 540228104 840512228 1...

output:

107364 61941 109757 91889 21525 143800 18665 82493 128706 18508 27581 122845 10939 148353 150037 104...

result:

ok 152911 numbers

Test #5:

score: 10
Accepted
time: 62ms
memory: 4404kb

input:

140495 83
66605606 834848402 683426896 920210623 485320690 968755640 86073240 87086888 347495502 130...

output:

9421 117400 96232 129361 68254 136148 12158 12305 49045 18400 68045 68009 136292 18861 114232 3336 1...

result:

ok 140495 numbers

Test #6:

score: 10
Accepted
time: 45ms
memory: 4080kb

input:

112168 52
407475517 329684865 911044403 234279461 538316933 972347344 476635176 36005246 246434866 9...

output:

45978 37211 102319 26403 60561 109080 53715 4070 27767 108716 43478 63436 25682 41964 78802 58083 58...

result:

ok 112168 numbers

Test #7:

score: 10
Accepted
time: 110ms
memory: 4552kb

input:

152826 77
123622344 428145246 910612231 219277869 261355649 859120370 883327925 985917667 906182455 ...

output:

18979 65460 139198 33465 39988 131439 135118 150625 138520 41555 104479 45048 41065 80283 7637 8833 ...

result:

ok 152826 numbers

Test #8:

score: 10
Accepted
time: 209ms
memory: 5028kb

input:

193435 192486
270221619 837207913 153334187 60454282 677657649 608643506 233776256 137272392 8118486...

output:

51859 161827 29358 11595 130892 117496 44883 26330 156940 45696 180135 20043 7713 54395 25003 191373...

result:

ok 193435 numbers

Test #9:

score: 10
Accepted
time: 145ms
memory: 3968kb

input:

103040 194775
24304967 522487456 523147399 346252957 473225628 737528188 388059441 73215599 83832834...

output:

2519 53732 53806 35627 48631 75844 39890 7447 86319 10401 84403 84538 54042 46673 92229 62376 4233 4...

result:

ok 103040 numbers

Test #10:

score: 10
Accepted
time: 135ms
memory: 4316kb

input:

132794 133327
827618495 201784982 335022182 339430727 402586090 79494916 665376077 351042609 2477541...

output:

109921 26950 44481 45025 53434 10739 88261 46546 33031 61848 58099 75643 44452 80388 62497 49357 824...

result:

ok 132794 numbers