#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
int n;
const int maxn = 3e5 + 69;
int a[maxn];
set <int> send;
map <int, int> comp;
int seg[4*maxn];
int b[maxn];
void Update(int l, int r, int pos, int qpos, int qval){
seg[pos]+=qval;
if (l==r) return;
int mid = (l+r)/2;
if (qpos<=mid) Update(l, mid, pos*2, qpos, qval);
else Update(mid + 1, r, pos*2 + 1, qpos, qval);
}
int Query(int l, int r, int pos, int ql, int qr){
if (l>=ql && r<=qr) return seg[pos];
else if (l>qr || r<ql) return 0;
int mid = (l+r)/2;
return Query(l, mid, pos*2, ql, qr) + Query(mid + 1, r, pos*2 + 1, ql, qr);
}
void compress()
{
int p = 1;
for (auto x: send){
comp[x] = p++;
}
}
void Solve()
{
cin>>n;
for (int i=1; i<=n; i++){
cin>>a[i];
send.insert(a[i]);
}
compress();
for (int i=1; i<=n; i++)
a[i] = comp[a[i]];
for (int i=1; i<=n; i++){
b[i] = Query(1, n, 1, 1, a[i]-1);
Update(1, n, 1, a[i], 1);
}
for (int i=0; i<4*maxn; i++)
seg[i] = 0;
int sum = 0;
for (int i=n; i>=1; i--){
b[i] *= Query(1, n, 1, 1, a[i]-1);
Update(1, n, 1, a[i], 1);
sum += b[i];
}
cout<<sum;
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
9684 KB |
Output is correct |
2 |
Correct |
297 ms |
47180 KB |
Output is correct |
3 |
Correct |
295 ms |
52752 KB |
Output is correct |
4 |
Correct |
296 ms |
52728 KB |
Output is correct |
5 |
Correct |
298 ms |
52856 KB |
Output is correct |
6 |
Correct |
295 ms |
52764 KB |
Output is correct |
7 |
Correct |
303 ms |
52868 KB |
Output is correct |
8 |
Correct |
302 ms |
52808 KB |
Output is correct |
9 |
Correct |
235 ms |
36992 KB |
Output is correct |
10 |
Correct |
242 ms |
36892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
70 ms |
14300 KB |
Output is correct |
2 |
Correct |
79 ms |
14864 KB |
Output is correct |
3 |
Correct |
72 ms |
14924 KB |
Output is correct |
4 |
Correct |
70 ms |
14980 KB |
Output is correct |
5 |
Correct |
72 ms |
14908 KB |
Output is correct |
6 |
Correct |
69 ms |
14968 KB |
Output is correct |
7 |
Correct |
70 ms |
14948 KB |
Output is correct |
8 |
Correct |
67 ms |
14920 KB |
Output is correct |
9 |
Correct |
75 ms |
15052 KB |
Output is correct |
10 |
Correct |
4 ms |
9684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
70 ms |
14300 KB |
Output is correct |
2 |
Correct |
79 ms |
14864 KB |
Output is correct |
3 |
Correct |
72 ms |
14924 KB |
Output is correct |
4 |
Correct |
70 ms |
14980 KB |
Output is correct |
5 |
Correct |
72 ms |
14908 KB |
Output is correct |
6 |
Correct |
69 ms |
14968 KB |
Output is correct |
7 |
Correct |
70 ms |
14948 KB |
Output is correct |
8 |
Correct |
67 ms |
14920 KB |
Output is correct |
9 |
Correct |
75 ms |
15052 KB |
Output is correct |
10 |
Correct |
4 ms |
9684 KB |
Output is correct |
11 |
Correct |
125 ms |
15268 KB |
Output is correct |
12 |
Correct |
132 ms |
15196 KB |
Output is correct |
13 |
Correct |
132 ms |
15240 KB |
Output is correct |
14 |
Correct |
128 ms |
15248 KB |
Output is correct |
15 |
Correct |
135 ms |
15256 KB |
Output is correct |
16 |
Correct |
129 ms |
15264 KB |
Output is correct |
17 |
Correct |
128 ms |
15180 KB |
Output is correct |
18 |
Correct |
89 ms |
15228 KB |
Output is correct |
19 |
Correct |
83 ms |
15144 KB |
Output is correct |
20 |
Correct |
4 ms |
9684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
4 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
4 |
Correct |
6 ms |
9684 KB |
Output is correct |
5 |
Correct |
4 ms |
9684 KB |
Output is correct |
6 |
Correct |
4 ms |
9684 KB |
Output is correct |
7 |
Correct |
5 ms |
9732 KB |
Output is correct |
8 |
Correct |
4 ms |
9676 KB |
Output is correct |
9 |
Correct |
4 ms |
9700 KB |
Output is correct |
10 |
Correct |
4 ms |
9684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
4 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
4 |
Correct |
6 ms |
9684 KB |
Output is correct |
5 |
Correct |
4 ms |
9684 KB |
Output is correct |
6 |
Correct |
4 ms |
9684 KB |
Output is correct |
7 |
Correct |
5 ms |
9732 KB |
Output is correct |
8 |
Correct |
4 ms |
9676 KB |
Output is correct |
9 |
Correct |
4 ms |
9700 KB |
Output is correct |
10 |
Correct |
4 ms |
9684 KB |
Output is correct |
11 |
Correct |
16 ms |
10916 KB |
Output is correct |
12 |
Correct |
14 ms |
10964 KB |
Output is correct |
13 |
Correct |
14 ms |
10948 KB |
Output is correct |
14 |
Correct |
14 ms |
10880 KB |
Output is correct |
15 |
Correct |
15 ms |
10984 KB |
Output is correct |
16 |
Correct |
14 ms |
10984 KB |
Output is correct |
17 |
Correct |
15 ms |
10964 KB |
Output is correct |
18 |
Correct |
12 ms |
10260 KB |
Output is correct |
19 |
Correct |
8 ms |
9940 KB |
Output is correct |
20 |
Correct |
4 ms |
9684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
70 ms |
14300 KB |
Output is correct |
2 |
Correct |
79 ms |
14864 KB |
Output is correct |
3 |
Correct |
72 ms |
14924 KB |
Output is correct |
4 |
Correct |
70 ms |
14980 KB |
Output is correct |
5 |
Correct |
72 ms |
14908 KB |
Output is correct |
6 |
Correct |
69 ms |
14968 KB |
Output is correct |
7 |
Correct |
70 ms |
14948 KB |
Output is correct |
8 |
Correct |
67 ms |
14920 KB |
Output is correct |
9 |
Correct |
75 ms |
15052 KB |
Output is correct |
10 |
Correct |
4 ms |
9684 KB |
Output is correct |
11 |
Correct |
125 ms |
15268 KB |
Output is correct |
12 |
Correct |
132 ms |
15196 KB |
Output is correct |
13 |
Correct |
132 ms |
15240 KB |
Output is correct |
14 |
Correct |
128 ms |
15248 KB |
Output is correct |
15 |
Correct |
135 ms |
15256 KB |
Output is correct |
16 |
Correct |
129 ms |
15264 KB |
Output is correct |
17 |
Correct |
128 ms |
15180 KB |
Output is correct |
18 |
Correct |
89 ms |
15228 KB |
Output is correct |
19 |
Correct |
83 ms |
15144 KB |
Output is correct |
20 |
Correct |
4 ms |
9684 KB |
Output is correct |
21 |
Correct |
359 ms |
26528 KB |
Output is correct |
22 |
Correct |
333 ms |
26468 KB |
Output is correct |
23 |
Correct |
332 ms |
26488 KB |
Output is correct |
24 |
Correct |
354 ms |
26612 KB |
Output is correct |
25 |
Correct |
342 ms |
26496 KB |
Output is correct |
26 |
Correct |
350 ms |
26640 KB |
Output is correct |
27 |
Correct |
346 ms |
26544 KB |
Output is correct |
28 |
Correct |
177 ms |
26532 KB |
Output is correct |
29 |
Correct |
182 ms |
26440 KB |
Output is correct |
30 |
Correct |
4 ms |
9684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
9684 KB |
Output is correct |
2 |
Correct |
297 ms |
47180 KB |
Output is correct |
3 |
Correct |
295 ms |
52752 KB |
Output is correct |
4 |
Correct |
296 ms |
52728 KB |
Output is correct |
5 |
Correct |
298 ms |
52856 KB |
Output is correct |
6 |
Correct |
295 ms |
52764 KB |
Output is correct |
7 |
Correct |
303 ms |
52868 KB |
Output is correct |
8 |
Correct |
302 ms |
52808 KB |
Output is correct |
9 |
Correct |
235 ms |
36992 KB |
Output is correct |
10 |
Correct |
242 ms |
36892 KB |
Output is correct |
11 |
Correct |
70 ms |
14300 KB |
Output is correct |
12 |
Correct |
79 ms |
14864 KB |
Output is correct |
13 |
Correct |
72 ms |
14924 KB |
Output is correct |
14 |
Correct |
70 ms |
14980 KB |
Output is correct |
15 |
Correct |
72 ms |
14908 KB |
Output is correct |
16 |
Correct |
69 ms |
14968 KB |
Output is correct |
17 |
Correct |
70 ms |
14948 KB |
Output is correct |
18 |
Correct |
67 ms |
14920 KB |
Output is correct |
19 |
Correct |
75 ms |
15052 KB |
Output is correct |
20 |
Correct |
4 ms |
9684 KB |
Output is correct |
21 |
Correct |
125 ms |
15268 KB |
Output is correct |
22 |
Correct |
132 ms |
15196 KB |
Output is correct |
23 |
Correct |
132 ms |
15240 KB |
Output is correct |
24 |
Correct |
128 ms |
15248 KB |
Output is correct |
25 |
Correct |
135 ms |
15256 KB |
Output is correct |
26 |
Correct |
129 ms |
15264 KB |
Output is correct |
27 |
Correct |
128 ms |
15180 KB |
Output is correct |
28 |
Correct |
89 ms |
15228 KB |
Output is correct |
29 |
Correct |
83 ms |
15144 KB |
Output is correct |
30 |
Correct |
4 ms |
9684 KB |
Output is correct |
31 |
Correct |
4 ms |
9684 KB |
Output is correct |
32 |
Correct |
4 ms |
9684 KB |
Output is correct |
33 |
Correct |
4 ms |
9684 KB |
Output is correct |
34 |
Correct |
6 ms |
9684 KB |
Output is correct |
35 |
Correct |
4 ms |
9684 KB |
Output is correct |
36 |
Correct |
4 ms |
9684 KB |
Output is correct |
37 |
Correct |
5 ms |
9732 KB |
Output is correct |
38 |
Correct |
4 ms |
9676 KB |
Output is correct |
39 |
Correct |
4 ms |
9700 KB |
Output is correct |
40 |
Correct |
4 ms |
9684 KB |
Output is correct |
41 |
Correct |
16 ms |
10916 KB |
Output is correct |
42 |
Correct |
14 ms |
10964 KB |
Output is correct |
43 |
Correct |
14 ms |
10948 KB |
Output is correct |
44 |
Correct |
14 ms |
10880 KB |
Output is correct |
45 |
Correct |
15 ms |
10984 KB |
Output is correct |
46 |
Correct |
14 ms |
10984 KB |
Output is correct |
47 |
Correct |
15 ms |
10964 KB |
Output is correct |
48 |
Correct |
12 ms |
10260 KB |
Output is correct |
49 |
Correct |
8 ms |
9940 KB |
Output is correct |
50 |
Correct |
4 ms |
9684 KB |
Output is correct |
51 |
Correct |
359 ms |
26528 KB |
Output is correct |
52 |
Correct |
333 ms |
26468 KB |
Output is correct |
53 |
Correct |
332 ms |
26488 KB |
Output is correct |
54 |
Correct |
354 ms |
26612 KB |
Output is correct |
55 |
Correct |
342 ms |
26496 KB |
Output is correct |
56 |
Correct |
350 ms |
26640 KB |
Output is correct |
57 |
Correct |
346 ms |
26544 KB |
Output is correct |
58 |
Correct |
177 ms |
26532 KB |
Output is correct |
59 |
Correct |
182 ms |
26440 KB |
Output is correct |
60 |
Correct |
4 ms |
9684 KB |
Output is correct |
61 |
Correct |
702 ms |
52748 KB |
Output is correct |
62 |
Correct |
680 ms |
52776 KB |
Output is correct |
63 |
Correct |
688 ms |
52800 KB |
Output is correct |
64 |
Correct |
699 ms |
52812 KB |
Output is correct |
65 |
Correct |
703 ms |
52880 KB |
Output is correct |
66 |
Correct |
693 ms |
52720 KB |
Output is correct |
67 |
Correct |
674 ms |
52844 KB |
Output is correct |
68 |
Correct |
485 ms |
36904 KB |
Output is correct |
69 |
Correct |
407 ms |
30456 KB |
Output is correct |
70 |
Correct |
4 ms |
9684 KB |
Output is correct |