# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
583507 | 2022-06-25T12:52:17 Z | Kanaifu | Mountains (NOI20_mountains) | C++17 | 94 ms | 9868 KB |
#include <bits/stdc++.h> using namespace std; #define pb push_back #define fr first #define sc second int tree[300001]; int n; int sum(int ind) { int zbir = 0; while (ind > 0) { zbir += tree[ind]; ind = (ind)&(ind-1); } return zbir; } void update(int ind) { while (ind <= n) { tree[ind]++; ind += (ind & (-ind)); } } long long query(int left, int right) { return (sum(right) - sum(left - 1)); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); long long brojac = 0; memset(tree, 0, sizeof(tree)); vector <int> reset; vector <pair<long long, int>> order; cin>>n; for (int i=1; i<=n; i++) { long long height; cin>>height; order.pb({height, i}); } sort(order.begin(), order.end()); int last = -1; for (int i=0; i<order.size(); i++) { if (order[i].fr != last) { for (int el : reset) { update(el); } reset.clear(); } brojac += (query(1, order[i].sc-1))*(query(order[i].sc+1, n)); reset.pb(order[i].sc); last = order[i].fr; } cout<<brojac; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 1492 KB | Output is correct |
2 | Correct | 69 ms | 9736 KB | Output is correct |
3 | Correct | 82 ms | 9836 KB | Output is correct |
4 | Correct | 84 ms | 9780 KB | Output is correct |
5 | Correct | 68 ms | 9808 KB | Output is correct |
6 | Correct | 73 ms | 9804 KB | Output is correct |
7 | Correct | 73 ms | 9828 KB | Output is correct |
8 | Correct | 73 ms | 9760 KB | Output is correct |
9 | Correct | 74 ms | 9824 KB | Output is correct |
10 | Correct | 81 ms | 9840 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 59 ms | 9800 KB | Output is correct |
2 | Correct | 61 ms | 9816 KB | Output is correct |
3 | Correct | 65 ms | 9804 KB | Output is correct |
4 | Correct | 58 ms | 9792 KB | Output is correct |
5 | Correct | 72 ms | 9844 KB | Output is correct |
6 | Correct | 64 ms | 9760 KB | Output is correct |
7 | Correct | 56 ms | 9764 KB | Output is correct |
8 | Correct | 43 ms | 9860 KB | Output is correct |
9 | Correct | 44 ms | 9744 KB | Output is correct |
10 | Correct | 1 ms | 1492 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 59 ms | 9800 KB | Output is correct |
2 | Correct | 61 ms | 9816 KB | Output is correct |
3 | Correct | 65 ms | 9804 KB | Output is correct |
4 | Correct | 58 ms | 9792 KB | Output is correct |
5 | Correct | 72 ms | 9844 KB | Output is correct |
6 | Correct | 64 ms | 9760 KB | Output is correct |
7 | Correct | 56 ms | 9764 KB | Output is correct |
8 | Correct | 43 ms | 9860 KB | Output is correct |
9 | Correct | 44 ms | 9744 KB | Output is correct |
10 | Correct | 1 ms | 1492 KB | Output is correct |
11 | Correct | 87 ms | 9800 KB | Output is correct |
12 | Correct | 76 ms | 9800 KB | Output is correct |
13 | Correct | 69 ms | 9844 KB | Output is correct |
14 | Correct | 71 ms | 9768 KB | Output is correct |
15 | Correct | 73 ms | 9820 KB | Output is correct |
16 | Correct | 72 ms | 9832 KB | Output is correct |
17 | Correct | 84 ms | 9740 KB | Output is correct |
18 | Correct | 47 ms | 9848 KB | Output is correct |
19 | Correct | 43 ms | 9788 KB | Output is correct |
20 | Correct | 1 ms | 1364 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 1492 KB | Output is correct |
2 | Correct | 1 ms | 1492 KB | Output is correct |
3 | Correct | 1 ms | 1492 KB | Output is correct |
4 | Correct | 1 ms | 1492 KB | Output is correct |
5 | Correct | 1 ms | 1492 KB | Output is correct |
6 | Correct | 1 ms | 1492 KB | Output is correct |
7 | Correct | 1 ms | 1492 KB | Output is correct |
8 | Incorrect | 2 ms | 1492 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 1492 KB | Output is correct |
2 | Correct | 1 ms | 1492 KB | Output is correct |
3 | Correct | 1 ms | 1492 KB | Output is correct |
4 | Correct | 1 ms | 1492 KB | Output is correct |
5 | Correct | 1 ms | 1492 KB | Output is correct |
6 | Correct | 1 ms | 1492 KB | Output is correct |
7 | Correct | 1 ms | 1492 KB | Output is correct |
8 | Incorrect | 2 ms | 1492 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 59 ms | 9800 KB | Output is correct |
2 | Correct | 61 ms | 9816 KB | Output is correct |
3 | Correct | 65 ms | 9804 KB | Output is correct |
4 | Correct | 58 ms | 9792 KB | Output is correct |
5 | Correct | 72 ms | 9844 KB | Output is correct |
6 | Correct | 64 ms | 9760 KB | Output is correct |
7 | Correct | 56 ms | 9764 KB | Output is correct |
8 | Correct | 43 ms | 9860 KB | Output is correct |
9 | Correct | 44 ms | 9744 KB | Output is correct |
10 | Correct | 1 ms | 1492 KB | Output is correct |
11 | Correct | 87 ms | 9800 KB | Output is correct |
12 | Correct | 76 ms | 9800 KB | Output is correct |
13 | Correct | 69 ms | 9844 KB | Output is correct |
14 | Correct | 71 ms | 9768 KB | Output is correct |
15 | Correct | 73 ms | 9820 KB | Output is correct |
16 | Correct | 72 ms | 9832 KB | Output is correct |
17 | Correct | 84 ms | 9740 KB | Output is correct |
18 | Correct | 47 ms | 9848 KB | Output is correct |
19 | Correct | 43 ms | 9788 KB | Output is correct |
20 | Correct | 1 ms | 1364 KB | Output is correct |
21 | Correct | 94 ms | 9800 KB | Output is correct |
22 | Correct | 77 ms | 9844 KB | Output is correct |
23 | Correct | 75 ms | 9864 KB | Output is correct |
24 | Correct | 76 ms | 9808 KB | Output is correct |
25 | Correct | 84 ms | 9788 KB | Output is correct |
26 | Correct | 77 ms | 9868 KB | Output is correct |
27 | Correct | 74 ms | 9832 KB | Output is correct |
28 | Correct | 47 ms | 9800 KB | Output is correct |
29 | Correct | 50 ms | 9832 KB | Output is correct |
30 | Correct | 1 ms | 1492 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 1492 KB | Output is correct |
2 | Correct | 69 ms | 9736 KB | Output is correct |
3 | Correct | 82 ms | 9836 KB | Output is correct |
4 | Correct | 84 ms | 9780 KB | Output is correct |
5 | Correct | 68 ms | 9808 KB | Output is correct |
6 | Correct | 73 ms | 9804 KB | Output is correct |
7 | Correct | 73 ms | 9828 KB | Output is correct |
8 | Correct | 73 ms | 9760 KB | Output is correct |
9 | Correct | 74 ms | 9824 KB | Output is correct |
10 | Correct | 81 ms | 9840 KB | Output is correct |
11 | Correct | 59 ms | 9800 KB | Output is correct |
12 | Correct | 61 ms | 9816 KB | Output is correct |
13 | Correct | 65 ms | 9804 KB | Output is correct |
14 | Correct | 58 ms | 9792 KB | Output is correct |
15 | Correct | 72 ms | 9844 KB | Output is correct |
16 | Correct | 64 ms | 9760 KB | Output is correct |
17 | Correct | 56 ms | 9764 KB | Output is correct |
18 | Correct | 43 ms | 9860 KB | Output is correct |
19 | Correct | 44 ms | 9744 KB | Output is correct |
20 | Correct | 1 ms | 1492 KB | Output is correct |
21 | Correct | 87 ms | 9800 KB | Output is correct |
22 | Correct | 76 ms | 9800 KB | Output is correct |
23 | Correct | 69 ms | 9844 KB | Output is correct |
24 | Correct | 71 ms | 9768 KB | Output is correct |
25 | Correct | 73 ms | 9820 KB | Output is correct |
26 | Correct | 72 ms | 9832 KB | Output is correct |
27 | Correct | 84 ms | 9740 KB | Output is correct |
28 | Correct | 47 ms | 9848 KB | Output is correct |
29 | Correct | 43 ms | 9788 KB | Output is correct |
30 | Correct | 1 ms | 1364 KB | Output is correct |
31 | Correct | 1 ms | 1492 KB | Output is correct |
32 | Correct | 1 ms | 1492 KB | Output is correct |
33 | Correct | 1 ms | 1492 KB | Output is correct |
34 | Correct | 1 ms | 1492 KB | Output is correct |
35 | Correct | 1 ms | 1492 KB | Output is correct |
36 | Correct | 1 ms | 1492 KB | Output is correct |
37 | Correct | 1 ms | 1492 KB | Output is correct |
38 | Incorrect | 2 ms | 1492 KB | Output isn't correct |
39 | Halted | 0 ms | 0 KB | - |