# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
886494 | 2023-12-12T08:35:10 Z | Caubethieunang | Mountains (NOI20_mountains) | C++17 | 135 ms | 14592 KB |
#include <bits/stdc++.h> #define ll long long #define LOG 19 #define MASK(i) (1LL<<(i)) #define BIT(x,i) (((x)>>(i))&1) #define FIRST_BIT(mask) __builtin_ctz((mask)&(-mask)) #define ERASE_BIT(mask) (mask)^((mask)&(-mask)) #define left _left #define right _right #define task "t" using namespace std; const ll INF=1e18; const int iat=3e5+9; const int mod=1e9+7; void fast_IO() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if(fopen(task".inp","r")) { freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } } int n; ll h[iat]; struct Fenwick { int bit[iat]; void update(int pos, int val) { for(int i=pos; i<=n; i+=i&-i)bit[i]+=val; } int getSum(int pos) { int res=0; for(int i=pos; i>0; i-=i&-i)res+=bit[i]; return res; } }left,right; void compress() { vector <ll> v; for(int i=1; i<=n; i++)v.push_back(h[i]); sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); for(int i=1; i<=n; i++)h[i]=lower_bound(v.begin(),v.end(),h[i])-v.begin()+1; } signed main() { fast_IO(); cin>>n; for(int i=1; i<=n; i++)cin>>h[i]; compress(); left.update(h[1],1); for(int i=2; i<=n; i++)right.update(h[i],1); ll ans=0; for(int i=2; i<n; i++) { right.update(h[i],-1); ans+=1LL*left.getSum(h[i]-1)*right.getSum(h[i]-1); left.update(h[i],1); } cout<<ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4444 KB | Output is correct |
2 | Correct | 94 ms | 12980 KB | Output is correct |
3 | Correct | 71 ms | 13740 KB | Output is correct |
4 | Correct | 81 ms | 14280 KB | Output is correct |
5 | Correct | 104 ms | 14540 KB | Output is correct |
6 | Correct | 69 ms | 14380 KB | Output is correct |
7 | Correct | 68 ms | 14592 KB | Output is correct |
8 | Correct | 68 ms | 14024 KB | Output is correct |
9 | Correct | 73 ms | 13700 KB | Output is correct |
10 | Correct | 82 ms | 13616 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 61 ms | 7888 KB | Output is correct |
2 | Correct | 62 ms | 7992 KB | Output is correct |
3 | Correct | 50 ms | 9168 KB | Output is correct |
4 | Correct | 50 ms | 8916 KB | Output is correct |
5 | Correct | 50 ms | 7892 KB | Output is correct |
6 | Correct | 49 ms | 8916 KB | Output is correct |
7 | Correct | 57 ms | 8888 KB | Output is correct |
8 | Correct | 44 ms | 7644 KB | Output is correct |
9 | Correct | 44 ms | 8668 KB | Output is correct |
10 | Correct | 1 ms | 4700 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 61 ms | 7888 KB | Output is correct |
2 | Correct | 62 ms | 7992 KB | Output is correct |
3 | Correct | 50 ms | 9168 KB | Output is correct |
4 | Correct | 50 ms | 8916 KB | Output is correct |
5 | Correct | 50 ms | 7892 KB | Output is correct |
6 | Correct | 49 ms | 8916 KB | Output is correct |
7 | Correct | 57 ms | 8888 KB | Output is correct |
8 | Correct | 44 ms | 7644 KB | Output is correct |
9 | Correct | 44 ms | 8668 KB | Output is correct |
10 | Correct | 1 ms | 4700 KB | Output is correct |
11 | Correct | 60 ms | 9684 KB | Output is correct |
12 | Correct | 59 ms | 9284 KB | Output is correct |
13 | Correct | 58 ms | 7888 KB | Output is correct |
14 | Correct | 58 ms | 8148 KB | Output is correct |
15 | Correct | 60 ms | 9780 KB | Output is correct |
16 | Correct | 58 ms | 9160 KB | Output is correct |
17 | Correct | 66 ms | 8148 KB | Output is correct |
18 | Correct | 41 ms | 9140 KB | Output is correct |
19 | Correct | 40 ms | 8148 KB | Output is correct |
20 | Correct | 1 ms | 4440 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4444 KB | Output is correct |
2 | Correct | 1 ms | 4444 KB | Output is correct |
3 | Correct | 1 ms | 4444 KB | Output is correct |
4 | Correct | 2 ms | 4444 KB | Output is correct |
5 | Correct | 1 ms | 4444 KB | Output is correct |
6 | Correct | 1 ms | 4440 KB | Output is correct |
7 | Correct | 1 ms | 4572 KB | Output is correct |
8 | Correct | 1 ms | 4444 KB | Output is correct |
9 | Correct | 1 ms | 4444 KB | Output is correct |
10 | Correct | 1 ms | 4444 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4444 KB | Output is correct |
2 | Correct | 1 ms | 4444 KB | Output is correct |
3 | Correct | 1 ms | 4444 KB | Output is correct |
4 | Correct | 2 ms | 4444 KB | Output is correct |
5 | Correct | 1 ms | 4444 KB | Output is correct |
6 | Correct | 1 ms | 4440 KB | Output is correct |
7 | Correct | 1 ms | 4572 KB | Output is correct |
8 | Correct | 1 ms | 4444 KB | Output is correct |
9 | Correct | 1 ms | 4444 KB | Output is correct |
10 | Correct | 1 ms | 4444 KB | Output is correct |
11 | Correct | 4 ms | 4748 KB | Output is correct |
12 | Correct | 4 ms | 4876 KB | Output is correct |
13 | Correct | 4 ms | 5128 KB | Output is correct |
14 | Correct | 5 ms | 4876 KB | Output is correct |
15 | Correct | 5 ms | 4936 KB | Output is correct |
16 | Correct | 5 ms | 4880 KB | Output is correct |
17 | Correct | 5 ms | 4756 KB | Output is correct |
18 | Correct | 4 ms | 4876 KB | Output is correct |
19 | Correct | 4 ms | 4620 KB | Output is correct |
20 | Correct | 1 ms | 4444 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 61 ms | 7888 KB | Output is correct |
2 | Correct | 62 ms | 7992 KB | Output is correct |
3 | Correct | 50 ms | 9168 KB | Output is correct |
4 | Correct | 50 ms | 8916 KB | Output is correct |
5 | Correct | 50 ms | 7892 KB | Output is correct |
6 | Correct | 49 ms | 8916 KB | Output is correct |
7 | Correct | 57 ms | 8888 KB | Output is correct |
8 | Correct | 44 ms | 7644 KB | Output is correct |
9 | Correct | 44 ms | 8668 KB | Output is correct |
10 | Correct | 1 ms | 4700 KB | Output is correct |
11 | Correct | 60 ms | 9684 KB | Output is correct |
12 | Correct | 59 ms | 9284 KB | Output is correct |
13 | Correct | 58 ms | 7888 KB | Output is correct |
14 | Correct | 58 ms | 8148 KB | Output is correct |
15 | Correct | 60 ms | 9780 KB | Output is correct |
16 | Correct | 58 ms | 9160 KB | Output is correct |
17 | Correct | 66 ms | 8148 KB | Output is correct |
18 | Correct | 41 ms | 9140 KB | Output is correct |
19 | Correct | 40 ms | 8148 KB | Output is correct |
20 | Correct | 1 ms | 4440 KB | Output is correct |
21 | Correct | 92 ms | 10772 KB | Output is correct |
22 | Correct | 90 ms | 8916 KB | Output is correct |
23 | Correct | 89 ms | 10700 KB | Output is correct |
24 | Correct | 93 ms | 9676 KB | Output is correct |
25 | Correct | 92 ms | 10392 KB | Output is correct |
26 | Correct | 91 ms | 8912 KB | Output is correct |
27 | Correct | 89 ms | 8756 KB | Output is correct |
28 | Correct | 50 ms | 9420 KB | Output is correct |
29 | Correct | 56 ms | 9548 KB | Output is correct |
30 | Correct | 1 ms | 4444 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4444 KB | Output is correct |
2 | Correct | 94 ms | 12980 KB | Output is correct |
3 | Correct | 71 ms | 13740 KB | Output is correct |
4 | Correct | 81 ms | 14280 KB | Output is correct |
5 | Correct | 104 ms | 14540 KB | Output is correct |
6 | Correct | 69 ms | 14380 KB | Output is correct |
7 | Correct | 68 ms | 14592 KB | Output is correct |
8 | Correct | 68 ms | 14024 KB | Output is correct |
9 | Correct | 73 ms | 13700 KB | Output is correct |
10 | Correct | 82 ms | 13616 KB | Output is correct |
11 | Correct | 61 ms | 7888 KB | Output is correct |
12 | Correct | 62 ms | 7992 KB | Output is correct |
13 | Correct | 50 ms | 9168 KB | Output is correct |
14 | Correct | 50 ms | 8916 KB | Output is correct |
15 | Correct | 50 ms | 7892 KB | Output is correct |
16 | Correct | 49 ms | 8916 KB | Output is correct |
17 | Correct | 57 ms | 8888 KB | Output is correct |
18 | Correct | 44 ms | 7644 KB | Output is correct |
19 | Correct | 44 ms | 8668 KB | Output is correct |
20 | Correct | 1 ms | 4700 KB | Output is correct |
21 | Correct | 60 ms | 9684 KB | Output is correct |
22 | Correct | 59 ms | 9284 KB | Output is correct |
23 | Correct | 58 ms | 7888 KB | Output is correct |
24 | Correct | 58 ms | 8148 KB | Output is correct |
25 | Correct | 60 ms | 9780 KB | Output is correct |
26 | Correct | 58 ms | 9160 KB | Output is correct |
27 | Correct | 66 ms | 8148 KB | Output is correct |
28 | Correct | 41 ms | 9140 KB | Output is correct |
29 | Correct | 40 ms | 8148 KB | Output is correct |
30 | Correct | 1 ms | 4440 KB | Output is correct |
31 | Correct | 1 ms | 4444 KB | Output is correct |
32 | Correct | 1 ms | 4444 KB | Output is correct |
33 | Correct | 1 ms | 4444 KB | Output is correct |
34 | Correct | 2 ms | 4444 KB | Output is correct |
35 | Correct | 1 ms | 4444 KB | Output is correct |
36 | Correct | 1 ms | 4440 KB | Output is correct |
37 | Correct | 1 ms | 4572 KB | Output is correct |
38 | Correct | 1 ms | 4444 KB | Output is correct |
39 | Correct | 1 ms | 4444 KB | Output is correct |
40 | Correct | 1 ms | 4444 KB | Output is correct |
41 | Correct | 4 ms | 4748 KB | Output is correct |
42 | Correct | 4 ms | 4876 KB | Output is correct |
43 | Correct | 4 ms | 5128 KB | Output is correct |
44 | Correct | 5 ms | 4876 KB | Output is correct |
45 | Correct | 5 ms | 4936 KB | Output is correct |
46 | Correct | 5 ms | 4880 KB | Output is correct |
47 | Correct | 5 ms | 4756 KB | Output is correct |
48 | Correct | 4 ms | 4876 KB | Output is correct |
49 | Correct | 4 ms | 4620 KB | Output is correct |
50 | Correct | 1 ms | 4444 KB | Output is correct |
51 | Correct | 92 ms | 10772 KB | Output is correct |
52 | Correct | 90 ms | 8916 KB | Output is correct |
53 | Correct | 89 ms | 10700 KB | Output is correct |
54 | Correct | 93 ms | 9676 KB | Output is correct |
55 | Correct | 92 ms | 10392 KB | Output is correct |
56 | Correct | 91 ms | 8912 KB | Output is correct |
57 | Correct | 89 ms | 8756 KB | Output is correct |
58 | Correct | 50 ms | 9420 KB | Output is correct |
59 | Correct | 56 ms | 9548 KB | Output is correct |
60 | Correct | 1 ms | 4444 KB | Output is correct |
61 | Correct | 125 ms | 14264 KB | Output is correct |
62 | Correct | 130 ms | 14376 KB | Output is correct |
63 | Correct | 126 ms | 14024 KB | Output is correct |
64 | Correct | 120 ms | 14508 KB | Output is correct |
65 | Correct | 122 ms | 13352 KB | Output is correct |
66 | Correct | 117 ms | 14028 KB | Output is correct |
67 | Correct | 117 ms | 13768 KB | Output is correct |
68 | Correct | 135 ms | 13260 KB | Output is correct |
69 | Correct | 104 ms | 9928 KB | Output is correct |
70 | Correct | 1 ms | 4444 KB | Output is correct |