#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxN = 300'000;
int H[1+maxN];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
for(int i = 1; i <= N; i++) cin >> H[i];
vector<int> ind(N);
for(int i = 1; i <= N; i++) ind[i-1] = i;
sort(ind.begin(), ind.end(), [] (int p, int q)
{
if(H[p] == H[q]) return p > q;
return H[p] < H[q];
});
vector<long long> lft(1+N, 0), rgt(1+N, 0);
vector<int> BIT(1+N, 0);
for(int i: ind)
{
for(int j = i; j <= N; j += j&-j)
BIT[j]++;
for(int j = i-1; j >= 1; j -= j&-j)
lft[i] += BIT[j];
}
// cerr << "check\n";
BIT = vector<int>(1+N, 0);
sort(ind.begin(), ind.end(), [] (int p, int q)
{
if(H[p] == H[q]) return p < q;
return H[p] < H[q];
});
// cerr << "check\n";
for(int i: ind)
{
for(int j = i; j <= N; j += j&-j)
BIT[j]++;
for(int j = N; j >= 1; j -= j&-j)
rgt[i] += BIT[j];
for(int j = i; j >= 1; j -= j&-j)
rgt[i] -= BIT[j];
}
// for(int i = 1; i <= N; i++) cerr << lft[i] << ' ';
// cerr << '\n';
long long ans = 0;
for(int i = 1; i <= N; i++) ans += lft[i] * rgt[i];
cout << ans << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
208 KB |
Output is correct |
2 |
Correct |
77 ms |
8528 KB |
Output is correct |
3 |
Correct |
78 ms |
8528 KB |
Output is correct |
4 |
Correct |
77 ms |
8600 KB |
Output is correct |
5 |
Correct |
82 ms |
8464 KB |
Output is correct |
6 |
Correct |
84 ms |
8528 KB |
Output is correct |
7 |
Correct |
80 ms |
8580 KB |
Output is correct |
8 |
Correct |
79 ms |
8572 KB |
Output is correct |
9 |
Correct |
77 ms |
8576 KB |
Output is correct |
10 |
Correct |
75 ms |
8588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
94 ms |
10188 KB |
Output is correct |
2 |
Correct |
113 ms |
10184 KB |
Output is correct |
3 |
Correct |
93 ms |
10284 KB |
Output is correct |
4 |
Correct |
114 ms |
10184 KB |
Output is correct |
5 |
Correct |
93 ms |
10220 KB |
Output is correct |
6 |
Correct |
105 ms |
10168 KB |
Output is correct |
7 |
Correct |
105 ms |
10184 KB |
Output is correct |
8 |
Correct |
119 ms |
10312 KB |
Output is correct |
9 |
Correct |
120 ms |
10172 KB |
Output is correct |
10 |
Correct |
0 ms |
208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
94 ms |
10188 KB |
Output is correct |
2 |
Correct |
113 ms |
10184 KB |
Output is correct |
3 |
Correct |
93 ms |
10284 KB |
Output is correct |
4 |
Correct |
114 ms |
10184 KB |
Output is correct |
5 |
Correct |
93 ms |
10220 KB |
Output is correct |
6 |
Correct |
105 ms |
10168 KB |
Output is correct |
7 |
Correct |
105 ms |
10184 KB |
Output is correct |
8 |
Correct |
119 ms |
10312 KB |
Output is correct |
9 |
Correct |
120 ms |
10172 KB |
Output is correct |
10 |
Correct |
0 ms |
208 KB |
Output is correct |
11 |
Correct |
117 ms |
10548 KB |
Output is correct |
12 |
Correct |
118 ms |
10552 KB |
Output is correct |
13 |
Correct |
115 ms |
10440 KB |
Output is correct |
14 |
Correct |
112 ms |
10552 KB |
Output is correct |
15 |
Correct |
128 ms |
10548 KB |
Output is correct |
16 |
Correct |
119 ms |
10440 KB |
Output is correct |
17 |
Correct |
113 ms |
10436 KB |
Output is correct |
18 |
Correct |
86 ms |
10508 KB |
Output is correct |
19 |
Correct |
81 ms |
10440 KB |
Output is correct |
20 |
Correct |
1 ms |
208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
94 ms |
10188 KB |
Output is correct |
2 |
Correct |
113 ms |
10184 KB |
Output is correct |
3 |
Correct |
93 ms |
10284 KB |
Output is correct |
4 |
Correct |
114 ms |
10184 KB |
Output is correct |
5 |
Correct |
93 ms |
10220 KB |
Output is correct |
6 |
Correct |
105 ms |
10168 KB |
Output is correct |
7 |
Correct |
105 ms |
10184 KB |
Output is correct |
8 |
Correct |
119 ms |
10312 KB |
Output is correct |
9 |
Correct |
120 ms |
10172 KB |
Output is correct |
10 |
Correct |
0 ms |
208 KB |
Output is correct |
11 |
Correct |
117 ms |
10548 KB |
Output is correct |
12 |
Correct |
118 ms |
10552 KB |
Output is correct |
13 |
Correct |
115 ms |
10440 KB |
Output is correct |
14 |
Correct |
112 ms |
10552 KB |
Output is correct |
15 |
Correct |
128 ms |
10548 KB |
Output is correct |
16 |
Correct |
119 ms |
10440 KB |
Output is correct |
17 |
Correct |
113 ms |
10436 KB |
Output is correct |
18 |
Correct |
86 ms |
10508 KB |
Output is correct |
19 |
Correct |
81 ms |
10440 KB |
Output is correct |
20 |
Correct |
1 ms |
208 KB |
Output is correct |
21 |
Correct |
122 ms |
11424 KB |
Output is correct |
22 |
Correct |
125 ms |
11432 KB |
Output is correct |
23 |
Correct |
126 ms |
11472 KB |
Output is correct |
24 |
Correct |
125 ms |
11360 KB |
Output is correct |
25 |
Correct |
126 ms |
11408 KB |
Output is correct |
26 |
Correct |
146 ms |
11660 KB |
Output is correct |
27 |
Correct |
130 ms |
11432 KB |
Output is correct |
28 |
Correct |
77 ms |
11396 KB |
Output is correct |
29 |
Correct |
72 ms |
11356 KB |
Output is correct |
30 |
Correct |
0 ms |
208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
208 KB |
Output is correct |
2 |
Correct |
77 ms |
8528 KB |
Output is correct |
3 |
Correct |
78 ms |
8528 KB |
Output is correct |
4 |
Correct |
77 ms |
8600 KB |
Output is correct |
5 |
Correct |
82 ms |
8464 KB |
Output is correct |
6 |
Correct |
84 ms |
8528 KB |
Output is correct |
7 |
Correct |
80 ms |
8580 KB |
Output is correct |
8 |
Correct |
79 ms |
8572 KB |
Output is correct |
9 |
Correct |
77 ms |
8576 KB |
Output is correct |
10 |
Correct |
75 ms |
8588 KB |
Output is correct |
11 |
Correct |
94 ms |
10188 KB |
Output is correct |
12 |
Correct |
113 ms |
10184 KB |
Output is correct |
13 |
Correct |
93 ms |
10284 KB |
Output is correct |
14 |
Correct |
114 ms |
10184 KB |
Output is correct |
15 |
Correct |
93 ms |
10220 KB |
Output is correct |
16 |
Correct |
105 ms |
10168 KB |
Output is correct |
17 |
Correct |
105 ms |
10184 KB |
Output is correct |
18 |
Correct |
119 ms |
10312 KB |
Output is correct |
19 |
Correct |
120 ms |
10172 KB |
Output is correct |
20 |
Correct |
0 ms |
208 KB |
Output is correct |
21 |
Correct |
117 ms |
10548 KB |
Output is correct |
22 |
Correct |
118 ms |
10552 KB |
Output is correct |
23 |
Correct |
115 ms |
10440 KB |
Output is correct |
24 |
Correct |
112 ms |
10552 KB |
Output is correct |
25 |
Correct |
128 ms |
10548 KB |
Output is correct |
26 |
Correct |
119 ms |
10440 KB |
Output is correct |
27 |
Correct |
113 ms |
10436 KB |
Output is correct |
28 |
Correct |
86 ms |
10508 KB |
Output is correct |
29 |
Correct |
81 ms |
10440 KB |
Output is correct |
30 |
Correct |
1 ms |
208 KB |
Output is correct |
31 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
32 |
Halted |
0 ms |
0 KB |
- |