QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#40232	#3317. What Goes Up Must Come Down	hehezhou	AC ✓	19ms	5336kb	C++20	730b	2022-07-18 15:07:29	2022-07-18 15:07:31

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-07-18 15:07:31]
评测

测评结果：AC
用时：19ms
内存：5336kb

查看

[2022-07-18 15:07:29]
提交

answer

#include <bits/stdc++.h>
using namespace std;
int n, m = 100000, a[100010];
int c[100010], ans1[100010], ans2[100010];
void add(int x, int k) {
    for (; x; x -= x & -x) c[x] += k;
}
int query(int x) {
    int ans = 0;
    for (; x <= m; x += x & -x) ans += c[x];
    return ans;
}
void calc(int *ans) {
    memset(c, 0, sizeof c);
    for (int i = 1; i <= n; i++) {
        ans[i] = query(a[i] + 1);
        add(a[i], 1);
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    calc(ans1);
    reverse(a + 1, a + 1 + n);
    calc(ans2);
    long long sum = 0;
    for (int i = 1; i <= n; i++) sum += min(ans1[i], ans2[n - i + 1]);
    cout << sum << endl;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 2ms

memory: 4092kb

input:

7
3 1 4 1 5 9 2

output:

result:

ok single line: '3'

Test #2:

score: 0

Accepted

time: 2ms

memory: 4056kb

input:

9
10 4 6 3 15 9 1 1 12

output:

result:

ok single line: '8'

Test #3:

score: 0

Accepted

time: 2ms

memory: 4184kb

input:

8
9 9 8 8 7 7 6 6

output:

result:

ok single line: '0'

Test #4:

score: 0

Accepted

time: 0ms

memory: 4108kb

input:

6
8 7 2 5 4 6

output:

result:

ok single line: '4'

Test #5:

score: 0

Accepted

time: 2ms

memory: 3920kb

input:

3
1 2 3

output:

result:

ok single line: '0'

Test #6:

score: 0

Accepted

time: 0ms

memory: 4116kb

input:

3
1 3 2

output:

result:

ok single line: '0'

Test #7:

score: 0

Accepted

time: 0ms

memory: 4116kb

input:

3
2 1 3

output:

result:

ok single line: '1'

Test #8:

score: 0

Accepted

time: 2ms

memory: 4024kb

input:

3
2 3 1

output:

result:

ok single line: '0'

Test #9:

score: 0

Accepted

time: 2ms

memory: 4116kb

input:

3
3 1 2

output:

result:

ok single line: '1'

Test #10:

score: 0

Accepted

time: 2ms

memory: 4132kb

input:

3
3 2 1

output:

result:

ok single line: '0'

Test #11:

score: 0

Accepted

time: 2ms

memory: 4112kb

input:

4
1 2 3 4

output:

result:

ok single line: '0'

Test #12:

score: 0

Accepted

time: 2ms

memory: 4180kb

input:

4
1 2 4 3

output:

result:

ok single line: '0'

Test #13:

score: 0

Accepted

time: 0ms

memory: 4144kb

input:

4
1 3 2 4

output:

result:

ok single line: '1'

Test #14:

score: 0

Accepted

time: 1ms

memory: 4024kb

input:

4
1 3 4 2

output:

result:

ok single line: '0'

Test #15:

score: 0

Accepted

time: 1ms

memory: 4148kb

input:

4
1 4 2 3

output:

result:

ok single line: '1'

Test #16:

score: 0

Accepted

time: 1ms

memory: 4108kb

input:

4
1 4 3 2

output:

result:

ok single line: '0'

Test #17:

score: 0

Accepted

time: 2ms

memory: 4144kb

input:

4
2 1 3 4

output:

result:

ok single line: '1'

Test #18:

score: 0

Accepted

time: 2ms

memory: 3920kb

input:

4
2 1 4 3

output:

result:

ok single line: '1'

Test #19:

score: 0

Accepted

time: 2ms

memory: 4092kb

input:

4
2 3 1 4

output:

result:

ok single line: '1'

Test #20:

score: 0

Accepted

time: 0ms

memory: 4120kb

input:

4
2 3 4 1

output:

result:

ok single line: '0'

Test #21:

score: 0

Accepted

time: 2ms

memory: 4092kb

input:

4
2 4 1 3

output:

result:

ok single line: '1'

Test #22:

score: 0

Accepted

time: 2ms

memory: 4108kb

input:

4
2 4 3 1

output:

result:

ok single line: '0'

Test #23:

score: 0

Accepted

time: 2ms

memory: 4020kb

input:

4
3 1 2 4

output:

result:

ok single line: '2'

Test #24:

score: 0

Accepted

time: 2ms

memory: 4184kb

input:

4
3 1 4 2

output:

result:

ok single line: '1'

Test #25:

score: 0

Accepted

time: 2ms

memory: 3976kb

input:

4
3 2 1 4

output:

result:

ok single line: '2'

Test #26:

score: 0

Accepted

time: 2ms

memory: 4144kb

input:

4
3 2 4 1

output:

result:

ok single line: '1'

Test #27:

score: 0

Accepted

time: 2ms

memory: 4128kb

input:

4
3 4 1 2

output:

result:

ok single line: '1'

Test #28:

score: 0

Accepted

time: 0ms

memory: 4120kb

input:

4
3 4 2 1

output:

result:

ok single line: '0'

Test #29:

score: 0

Accepted

time: 0ms

memory: 4112kb

input:

4
4 1 2 3

output:

result:

ok single line: '2'

Test #30:

score: 0

Accepted

time: 3ms

memory: 4052kb

input:

4
4 1 3 2

output:

result:

ok single line: '1'

Test #31:

score: 0

Accepted

time: 2ms

memory: 3920kb

input:

4
4 2 1 3

output:

result:

ok single line: '2'

Test #32:

score: 0

Accepted

time: 1ms

memory: 3976kb

input:

4
4 2 3 1

output:

result:

ok single line: '1'

Test #33:

score: 0

Accepted

time: 4ms

memory: 4180kb

input:

4
4 3 1 2

output:

result:

ok single line: '1'

Test #34:

score: 0

Accepted

time: 1ms

memory: 4128kb

input:

4
4 3 2 1

output:

result:

ok single line: '0'

Test #35:

score: 0

Accepted

time: 0ms

memory: 4020kb

input:

3
11613 11613 11613

output:

result:

ok single line: '0'

Test #36:

score: 0

Accepted

time: 1ms

memory: 4088kb

input:

4
69303 69303 69303 69303

output:

result:

ok single line: '0'

Test #37:

score: 0

Accepted

time: 2ms

memory: 4024kb

input:

10
46735 46735 46735 46735 46735 46735 46735 46735 46735 46735

output:

result:

ok single line: '0'

Test #38:

score: 0

Accepted

time: 12ms

memory: 5320kb

input:

100000
34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586 34586...

output:

result:

ok single line: '0'

Test #39:

score: 0

Accepted

time: 0ms

memory: 4108kb

input:

3
2 1 1

output:

result:

ok single line: '0'

Test #40:

score: 0

Accepted

time: 2ms

memory: 4020kb

input:

3
1 2 1

output:

result:

ok single line: '0'

Test #41:

score: 0

Accepted

time: 2ms

memory: 4108kb

input:

3
2 2 1

output:

result:

ok single line: '0'

Test #42:

score: 0

Accepted

time: 2ms

memory: 4048kb

input:

3
1 1 2

output:

result:

ok single line: '0'

Test #43:

score: 0

Accepted

time: 1ms

memory: 4024kb

input:

3
2 1 2

output:

result:

ok single line: '1'

Test #44:

score: 0

Accepted

time: 2ms

memory: 3920kb

input:

3
1 2 2

output:

result:

ok single line: '0'

Test #45:

score: 0

Accepted

time: 2ms

memory: 4052kb

input:

4
2 1 1 1

output:

result:

ok single line: '0'

Test #46:

score: 0

Accepted

time: 1ms

memory: 4108kb

input:

4
1 2 1 1

output:

result:

ok single line: '0'

Test #47:

score: 0

Accepted

time: 2ms

memory: 4088kb

input:

4
2 2 1 1

output:

result:

ok single line: '0'

Test #48:

score: 0

Accepted

time: 0ms

memory: 4024kb

input:

4
1 1 2 1

output:

result:

ok single line: '0'

Test #49:

score: 0

Accepted

time: 0ms

memory: 4120kb

input:

4
2 1 2 1

output:

result:

ok single line: '1'

Test #50:

score: 0

Accepted

time: 1ms

memory: 4168kb

input:

4
1 2 2 1

output:

result:

ok single line: '0'

Test #51:

score: 0

Accepted

time: 1ms

memory: 4032kb

input:

4
2 2 2 1

output:

result:

ok single line: '0'

Test #52:

score: 0

Accepted

time: 2ms

memory: 4032kb

input:

4
1 1 1 2

output:

result:

ok single line: '0'

Test #53:

score: 0

Accepted

time: 3ms

memory: 4048kb

input:

4
2 1 1 2

output:

result:

ok single line: '2'

Test #54:

score: 0

Accepted

time: 1ms

memory: 4168kb

input:

4
1 2 1 2

output:

result:

ok single line: '1'

Test #55:

score: 0

Accepted

time: 2ms

memory: 3920kb

input:

4
2 2 1 2

output:

result:

ok single line: '1'

Test #56:

score: 0

Accepted

time: 0ms

memory: 4092kb

input:

4
1 1 2 2

output:

result:

ok single line: '0'

Test #57:

score: 0

Accepted

time: 0ms

memory: 4112kb

input:

4
2 1 2 2

output:

result:

ok single line: '1'

Test #58:

score: 0

Accepted

time: 2ms

memory: 4120kb

input:

4
1 2 2 2

output:

result:

ok single line: '0'

Test #59:

score: 0

Accepted

time: 0ms

memory: 4020kb

input:

10
1 2 3 4 5 6 7 8 9 10

output:

result:

ok single line: '0'

Test #60:

score: 0

Accepted

time: 2ms

memory: 4116kb

input:

10
10 9 8 7 6 5 4 3 2 1

output:

result:

ok single line: '0'

Test #61:

score: 0

Accepted

time: 2ms

memory: 4048kb

input:

100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

output:

result:

ok single line: '0'

Test #62:

score: 0

Accepted

time: 2ms

memory: 4048kb

input:

100
100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

output:

result:

ok single line: '0'

Test #63:

score: 0

Accepted

time: 1ms

memory: 4088kb

input:

10000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

output:

result:

ok single line: '0'

Test #64:

score: 0

Accepted

time: 4ms

memory: 4168kb

input:

10000
10000 9999 9998 9997 9996 9995 9994 9993 9992 9991 9990 9989 9988 9987 9986 9985 9984 9983 9982 9981 9980 9979 9978 9977 9976 9975 9974 9973 9972 9971 9970 9969 9968 9967 9966 9965 9964 9963 9962 9961 9960 9959 9958 9957 9956 9955 9954 9953 9952 9951 9950 9949 9948 9947 9946 9945 9944 9943 994...

output:

result:

ok single line: '0'

Test #65:

score: 0

Accepted

time: 13ms

memory: 5136kb

input:

100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

output:

result:

ok single line: '0'

Test #66:

score: 0

Accepted

time: 12ms

memory: 5192kb

input:

100000
100000 99999 99998 99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 99969 99968 99967 99966 99965 99964 99963 99962 99961 99960 99959 99958 99957 99956 99955 99954 99953 9995...

output:

result:

ok single line: '0'

Test #67:

score: 0

Accepted

time: 4ms

memory: 4164kb

input:

10
4205 19430 33986 55392 62299 94566 94427 67404 40741 32836

output:

result:

ok single line: '0'

Test #68:

score: 0

Accepted

time: 4ms

memory: 4052kb

input:

10
95796 80571 66015 44609 37702 5435 5574 32597 59260 67165

output:

result:

ok single line: '15'

Test #69:

score: 0

Accepted

time: 4ms

memory: 4048kb

input:

100
38240 60520 64698 68805 92721 98743 97213 96537 93248 92679 92596 91674 91249 91162 91142 88588 86970 84845 82598 81327 81100 80496 78461 78155 77802 77330 77307 75153 73809 73007 72874 72610 72537 70446 69587 69059 68903 68898 66210 64244 64009 63881 62696 57583 57529 57297 56117 55880 55694 54...

output:

result:

ok single line: '0'

Test #70:

score: 0

Accepted

time: 1ms

memory: 4112kb

input:

100
61761 39481 35303 31196 7280 1258 2788 3464 6753 7322 7405 8327 8752 8839 8859 11413 13031 15156 17403 18674 18901 19505 21540 21846 22199 22671 22694 24848 26192 26994 27127 27391 27464 29555 30414 30942 31098 31103 33791 35757 35992 36120 37305 42418 42472 42704 43884 44121 44307 45391 45400 4...

output:

result:

ok single line: '186'

Test #71:

score: 0

Accepted

time: 4ms

memory: 3920kb

input:

100
343 1789 5833 6804 10652 11656 12771 12875 19952 24676 25158 25282 26704 29416 31780 33643 38301 40192 41419 44425 45557 50107 52157 53095 54501 56886 60104 64979 66104 67371 67455 67947 68826 68964 69246 70146 72821 75659 80336 81792 83406 84324 87210 87300 87439 89186 89509 89931 91718 96939 9...

output:

result:

ok single line: '0'

Test #72:

score: 0

Accepted

time: 3ms

memory: 4088kb

input:

100
99658 98212 94168 93197 89349 88345 87230 87126 80049 75325 74843 74719 73297 70585 68221 66358 61700 59809 58582 55576 54444 49894 47844 46906 45500 43115 39897 35022 33897 32630 32546 32054 31175 31037 30755 29855 27180 24342 19665 18209 16595 15677 12791 12701 12562 10815 10492 10070 8283 306...

output:

result:

ok single line: '2310'

Test #73:

score: 0

Accepted

time: 13ms

memory: 5304kb

input:

100000
29129 48325 53731 54013 86616 99999 99998 99998 99996 99993 99993 99992 99991 99991 99988 99987 99984 99983 99981 99981 99981 99980 99979 99977 99976 99975 99974 99974 99974 99973 99973 99972 99971 99968 99968 99967 99965 99965 99964 99964 99964 99963 99962 99960 99960 99959 99959 99959 99957...

output:

result:

ok single line: '0'

Test #74:

score: 0

Accepted

time: 15ms

memory: 5236kb

input:

100000
70872 51676 46270 45988 13385 2 3 3 5 8 8 9 10 10 13 14 17 18 20 20 20 21 22 24 25 26 27 27 27 28 28 29 30 33 33 34 36 36 37 37 37 38 39 41 41 42 42 42 44 44 45 45 45 46 47 47 47 47 48 48 49 49 52 52 53 53 55 57 57 58 59 63 65 67 67 68 70 71 71 72 74 74 74 76 76 78 79 79 80 81 81 81 83 86 86 ...

output:

result:

ok single line: '228839'

Test #75:

score: 0

Accepted

time: 15ms

memory: 5204kb

input:

100000
1 2 2 5 10 12 12 12 16 17 17 19 20 21 22 26 27 28 32 33 34 37 38 39 39 40 41 43 45 49 50 51 52 54 67 68 69 71 76 78 79 83 83 83 85 87 89 91 93 94 100 101 104 111 111 111 113 120 124 124 124 127 127 129 131 134 135 135 138 138 138 145 147 152 152 153 154 157 158 158 158 159 165 170 171 171 174...

output:

result:

ok single line: '0'

Test #76:

score: 0

Accepted

time: 19ms

memory: 5244kb

input:

100000
100000 99999 99999 99996 99991 99989 99989 99989 99985 99984 99984 99982 99981 99980 99979 99975 99974 99973 99969 99968 99967 99964 99963 99962 99962 99961 99960 99958 99956 99952 99951 99950 99949 99947 99934 99933 99932 99930 99925 99923 99922 99918 99918 99918 99916 99914 99912 99910 9990...

output:

2495428217

result:

ok single line: '2495428217'

Test #77:

score: 0

Accepted

time: 15ms

memory: 5320kb

input:

100000
1 1 1 2 3 3 5 5 5 6 6 10 11 11 12 13 14 14 14 14 14 16 16 21 23 23 23 23 24 24 25 25 25 26 27 27 28 29 30 32 32 33 34 36 37 41 42 42 45 46 46 47 48 48 48 48 49 49 51 52 52 52 53 54 55 55 56 56 58 59 59 60 61 64 64 64 65 66 67 68 68 68 69 69 70 71 72 73 74 74 74 76 76 77 80 80 81 81 82 82 83 8...

output:

result:

ok single line: '0'

Test #78:

score: 0

Accepted

time: 15ms

memory: 5244kb

input:

100000
100000 100000 100000 99999 99998 99998 99996 99996 99996 99995 99995 99991 99990 99990 99989 99988 99987 99987 99987 99987 99987 99985 99985 99980 99978 99978 99978 99978 99977 99977 99976 99976 99976 99975 99974 99974 99973 99972 99971 99969 99969 99968 99967 99965 99964 99960 99959 99959 99...

output:

result:

ok single line: '2593801'

Test #79:

score: 0

Accepted

time: 10ms

memory: 4712kb

input:

50000
25000 24999 24998 24997 24996 24995 24994 24993 24992 24991 24990 24989 24988 24987 24986 24985 24984 24983 24982 24981 24980 24979 24978 24977 24976 24975 24974 24973 24972 24971 24970 24969 24968 24967 24966 24965 24964 24963 24962 24961 24960 24959 24958 24957 24956 24955 24954 24953 24952 ...

output:

624975000

result:

ok single line: '624975000'

Test #80:

score: 0

Accepted

time: 19ms

memory: 5324kb

input:

100000
50000 49999 49998 49997 49996 49995 49994 49993 49992 49991 49990 49989 49988 49987 49986 49985 49984 49983 49982 49981 49980 49979 49978 49977 49976 49975 49974 49973 49972 49971 49970 49969 49968 49967 49966 49965 49964 49963 49962 49961 49960 49959 49958 49957 49956 49955 49954 49953 49952...

output:

2499950000

result:

ok single line: '2499950000'

Test #81:

score: 0

Accepted

time: 2ms

memory: 4092kb

input:

3
61670 51494 15018

output:

result:

ok single line: '0'

Test #82:

score: 0

Accepted

time: 2ms

memory: 4164kb

input:

10
94410 94410 30290 46869 94410 30290 46869 46869 94410 30290

output:

result:

ok single line: '9'

Test #83:

score: 0

Accepted

time: 0ms

memory: 4092kb

input:

10
87184 58437 10232 22812 10232 94512 10232 94512 58437 40843

output:

result:

ok single line: '11'

Test #84:

score: 0

Accepted

time: 10ms

memory: 5320kb

input:

100000
83471 23343 23343 23343 23343 83471 23343 23343 83471 83471 23343 83471 83471 83471 23343 23343 23343 23343 23343 83471 83471 23343 83471 23343 83471 83471 83471 83471 83471 83471 83471 83471 23343 23343 83471 23343 23343 23343 23343 23343 23343 23343 23343 83471 83471 83471 23343 23343 83471...

output:

627802548

result:

ok single line: '627802548'

Test #85:

score: 0

Accepted

time: 11ms

memory: 5268kb

input:

100000
32209 83703 83703 32030 32209 32030 32209 32209 32209 32030 83703 32030 32209 32030 32209 32209 32030 83703 32209 83703 32209 83703 32030 32030 32209 32209 83703 32030 83703 32209 83703 32209 32030 32030 32030 32030 83703 32209 32030 32030 83703 83703 83703 32030 32030 83703 83703 32209 32209...

output:

834447929

result:

ok single line: '834447929'

Test #86:

score: 0

Accepted

time: 14ms

memory: 5336kb

input:

100000
73036 40055 73036 74542 96193 40293 64426 40293 94762 31910 40055 94762 31910 40055 73036 59323 94762 64426 40293 64426 59323 73036 40293 94762 59323 74542 59323 59323 40293 40293 94762 74542 40055 77814 96193 73036 74542 31910 64426 73036 31910 74542 64426 40293 40293 94762 64426 40055 96193...

output:

1125923559

result:

ok single line: '1125923559'

Test #87:

score: 0

Accepted

time: 13ms

memory: 5204kb

input:

100000
21488 30166 24193 32375 64923 84247 54144 63486 27254 80899 25517 36093 74251 99129 94999 51191 68451 12050 86892 36973 48208 87 74961 51379 53786 89752 26597 75611 15237 5316 22385 29912 41654 41021 25986 91193 44854 11046 78146 15304 48419 76013 66368 19901 70999 94969 5244 50823 31552 4273...

output:

1246438148

result:

ok single line: '1246438148'

Test #88:

score: 0

Accepted

time: 14ms

memory: 5268kb

input:

100000
39936 41824 47120 26852 40011 59606 76318 66544 65102 84244 33104 52562 13054 82416 65053 90449 78128 83382 73227 58986 46061 19194 3479 40507 52306 23991 14594 34245 91808 55389 56949 8203 67676 38932 60276 97528 93234 9208 44724 92170 51059 8150 79496 56499 87063 12470 45213 40153 70886 563...

output:

1248431277

result:

ok single line: '1248431277'

Test #89:

score: 0

Accepted

time: 0ms

memory: 4024kb

input:

1
14970

output:

result:

ok single line: '0'

Test #90:

score: 0

Accepted

time: 0ms

memory: 4036kb

input:

2
50587 10082

output:

result:

ok single line: '0'