#include <iostream>
#include <map>
using namespace std;
const int nmax = 3e5 + 7;
int dr[nmax], st[nmax], f[nmax], v[nmax];
map<int, int> mp;
void update(int i) {
int val = 1;
while(i < nmax) {
f[i] += val;
i += (i & (-i));
}
}
int query(int i) {
int sum = 0;
while(i > 0) {
sum += f[i];
i -= (i & (-i));
}
return sum;
}
int main() {
int n;
cin >> n;
for(int i = 1; i <= n; i ++) {
cin >> v[i];
mp[v[i]];
}
int cnt = 2;
for(auto &it : mp) {
it.second = cnt;
cnt ++;
}
for(int i = 1; i <= n; i ++) {
v[i] = mp[v[i]];
}
for(int i = 1; i <= n; i ++) {
dr[i] = query(v[i] - 1);
update(v[i]);
}
for(int i = 0; i < nmax; i ++) {
f[i] = 0;
}
for(int i = n; i >= 1; i --) {
st[i] = query(v[i] - 1);
update(v[i]);
}
long long ans = 0;
for(int i = 1; i <= n; i ++) {
ans += dr[i] * st[i];
}
cout << ans;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1492 KB |
Output is correct |
2 |
Correct |
27 ms |
4924 KB |
Output is correct |
3 |
Correct |
27 ms |
4980 KB |
Output is correct |
4 |
Correct |
27 ms |
4944 KB |
Output is correct |
5 |
Correct |
27 ms |
4996 KB |
Output is correct |
6 |
Correct |
28 ms |
5052 KB |
Output is correct |
7 |
Correct |
27 ms |
4924 KB |
Output is correct |
8 |
Correct |
27 ms |
5112 KB |
Output is correct |
9 |
Correct |
27 ms |
4948 KB |
Output is correct |
10 |
Correct |
27 ms |
5012 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
62 ms |
5444 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
62 ms |
5444 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
1472 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
1472 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
62 ms |
5444 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1492 KB |
Output is correct |
2 |
Correct |
27 ms |
4924 KB |
Output is correct |
3 |
Correct |
27 ms |
4980 KB |
Output is correct |
4 |
Correct |
27 ms |
4944 KB |
Output is correct |
5 |
Correct |
27 ms |
4996 KB |
Output is correct |
6 |
Correct |
28 ms |
5052 KB |
Output is correct |
7 |
Correct |
27 ms |
4924 KB |
Output is correct |
8 |
Correct |
27 ms |
5112 KB |
Output is correct |
9 |
Correct |
27 ms |
4948 KB |
Output is correct |
10 |
Correct |
27 ms |
5012 KB |
Output is correct |
11 |
Incorrect |
62 ms |
5444 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |