#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
long long int t[1200000];
long long int g[300000];
long long 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;
freopen("13.in.txt", "r", stdin);
cin >> n;
vector<long long int>b;
for(int i = 0; i < n; i++){
cin >> g[i];
b.push_back(g[i]);
}
sort(b.begin(), b.end());
map<long long int,long long 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 += 1LL * left1[i] * right1[i];
}
cout << ans;
return 0;
}
Compilation message
Mountains.cpp: In function 'int main()':
Mountains.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i = 0; i < b.size(); i++){
| ~~^~~~~~~~~~
Mountains.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | freopen("13.in.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9676 KB |
Output is correct |
2 |
Correct |
6 ms |
9676 KB |
Output is correct |
3 |
Correct |
6 ms |
9596 KB |
Output is correct |
4 |
Correct |
6 ms |
9676 KB |
Output is correct |
5 |
Correct |
6 ms |
9676 KB |
Output is correct |
6 |
Correct |
6 ms |
9676 KB |
Output is correct |
7 |
Correct |
5 ms |
9676 KB |
Output is correct |
8 |
Correct |
6 ms |
9676 KB |
Output is correct |
9 |
Correct |
5 ms |
9676 KB |
Output is correct |
10 |
Correct |
6 ms |
9676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
9676 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
9676 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
9584 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
9584 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
9676 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9676 KB |
Output is correct |
2 |
Correct |
6 ms |
9676 KB |
Output is correct |
3 |
Correct |
6 ms |
9596 KB |
Output is correct |
4 |
Correct |
6 ms |
9676 KB |
Output is correct |
5 |
Correct |
6 ms |
9676 KB |
Output is correct |
6 |
Correct |
6 ms |
9676 KB |
Output is correct |
7 |
Correct |
5 ms |
9676 KB |
Output is correct |
8 |
Correct |
6 ms |
9676 KB |
Output is correct |
9 |
Correct |
5 ms |
9676 KB |
Output is correct |
10 |
Correct |
6 ms |
9676 KB |
Output is correct |
11 |
Incorrect |
7 ms |
9676 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |