This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define LIFESUCKS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ld long double
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define ar array
#include<cstdio>
#define vt vector
#include<fstream>
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define length(x) (int)(x).size()
#define fi first
#define se second
#define vt vector
int n;
ll a[300000];
ll b[300000];
vt<int>tree; vt<int>tr;
ll gett(int nd, int l, int r, int q_l, int q_r){
if(q_l > r || q_r < l)return(0);
if(q_l <= l && q_r >= r)return(tree[nd]);
int mid = (l + r) >> 1;
return(gett((nd << 1), l, mid, q_l, q_r) + gett((nd << 1) + 1, mid + 1, r, q_l, q_r));
}
ll get(int nd, int l, int r, int q_l, int q_r){
if(q_l > r || q_r < l)return(0);
if(q_l <= l && q_r >= r)return(tr[nd]);
int mid = (l + r) >> 1;
return(get((nd << 1), l, mid, q_l, q_r) + get((nd << 1) + 1, mid + 1, r, q_l, q_r));
}
void upd(int p){
tree[p + n]++;
for(int i = (p + n) >> 1; i >= 1; i = i >> 1){
tree[i]++;
}
}
void updd(int p, ll v){
tr[p + n] += v;
for(int i = (p + n) >> 1; i >= 1; i = i >> 1){
tr[i] += v;
}
}
int main(){
LIFESUCKS;
cin >> n;
int cr = n;
for(int i = 0; i < n; i++){
cin >> a[i]; b[i] = a[i];
}
sort(b, b + n);
for(int i = 0; i < n; i++){
a[i] = lower_bound(b, b + n, a[i]) - b;
}
while(__builtin_popcount(n) != 1)n++;
tree.resize(2 * n, 0);
ll left[n] = {0};
for(int i = cr - 1; i >= 0; i--){
left[i] = gett(1, 0, n - 1, 0, a[i] - 1);
upd(a[i]);
}
ll right[n] = {0};
tr.resize(2 * n, 0);
for(int i = 0; i < cr; i++ ){
right[i] = get(1, 0, n - 1, 0, a[i] - 1);
updd(a[i], 1);
}
ll ans = 0;
for(int i = 1; i < n - 1; i++){
ans += (right[i] * left[i]);
}
cout << ans;
}
Compilation message (stderr)
Mountains.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
7 | #pragma GCC optimization ("O3")
|
Mountains.cpp:8: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
8 | #pragma GCC optimization ("unroll-loops")
|
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |