#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int t[1200000];
int g[300000];
int left1[300000], right1[300000];
void update (int v, int tl, int tr, int h) {
if (tl == tr)
t[v]++;
else {
int tm = (tl + tr) / 2;
if (h <= tm)
update (v*2, tl, tm, h);
else
update (v*2+1, tm+1, tr, h);
t[v] = t[v*2] + t[v*2+1];
}
}
int sum (int v, int tl, int tr, int l, int r) {
if (l > r)
return 0;
if (l == tl && r == tr)
return t[v];
int tm = (tl + tr) / 2;
return sum (v*2, tl, tm, l, min(r,tm))
+ sum (v*2+1, tm+1, tr, max(l,tm+1), r);
}
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++){
cin >> g[i];
}
update(1, 0, n, g[0]);
for(int i = 1; i < n - 1; i++){
left1[i] = sum(1, 0, n, 0, g[i] - 1);
update(1, 0, n, g[i]);
}
memset(t, 0, sizeof(t[0]) * 300000);
update(1, 0, n, g[n - 1]);
for(int i = n - 2; i >= 1; i--){
right1[i] = sum(1, 0, n, 0, g[i] - 1);
update(1, 0, n, g[i]);
}
long long int ans = 0;
for(int i = 1; i < n - 1; i++){
ans += left1[i] * right1[i];
}
cout << ans;
return 0;
}
Compilation message
Mountains.cpp: In function 'int main()':
Mountains.cpp:41:39: warning: 'memset' used with length equal to number of elements without multiplication by element size [-Wmemset-elt-size]
41 | memset(t, 0, sizeof(t[0]) * 300000);
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2100 ms |
204 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
175 ms |
4984 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
175 ms |
4984 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
1484 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
1484 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
175 ms |
4984 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2100 ms |
204 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |