#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <map>
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;
vector<int>b;
for(int i = 0; i < n; i++){
cin >> g[i];
b.push_back(g[i]);
}
sort(b.begin(), b.end());
map<int,int>c;
for(int i = 0; i < b.size(); i++){
c[b[i]] = i;
}
for(int i = 0; i < n; i++){
g[i] = c[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]) * 1200000);
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:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int i = 0; i < b.size(); i++){
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
178 ms |
9752 KB |
Output is correct |
3 |
Correct |
152 ms |
9732 KB |
Output is correct |
4 |
Correct |
147 ms |
9780 KB |
Output is correct |
5 |
Correct |
176 ms |
9768 KB |
Output is correct |
6 |
Correct |
151 ms |
9776 KB |
Output is correct |
7 |
Correct |
153 ms |
9740 KB |
Output is correct |
8 |
Correct |
153 ms |
9764 KB |
Output is correct |
9 |
Correct |
148 ms |
9776 KB |
Output is correct |
10 |
Correct |
148 ms |
9780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
226 ms |
9680 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
226 ms |
9680 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
226 ms |
9680 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
178 ms |
9752 KB |
Output is correct |
3 |
Correct |
152 ms |
9732 KB |
Output is correct |
4 |
Correct |
147 ms |
9780 KB |
Output is correct |
5 |
Correct |
176 ms |
9768 KB |
Output is correct |
6 |
Correct |
151 ms |
9776 KB |
Output is correct |
7 |
Correct |
153 ms |
9740 KB |
Output is correct |
8 |
Correct |
153 ms |
9764 KB |
Output is correct |
9 |
Correct |
148 ms |
9776 KB |
Output is correct |
10 |
Correct |
148 ms |
9780 KB |
Output is correct |
11 |
Incorrect |
226 ms |
9680 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |