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;
long long n,x,p[3][300005],ans,d[300005],sum,sum1,s[300005];
map <long long,int> mp;
void update(int a){
for(int i = a; i <= n; i += (i & -i)){
p[x][i]++;
}
}
void deleteit(int a){
for(int i = a; i <= n; i += (i & -i)){
p[1][i]--;
}
}
void solve(int a){
sum = 0;
for(int i = a - 1; i >= 1; i -= (i & -i)){
sum += p[x][i];
}
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> d[i];
s[i] = d[i];
}
sort(s + 1, s + n + 1);
for(int i = 1; i <= n; i++){
if(mp[s[i]] == 0){
x++;
mp[s[i]] = x;
}
}
x = 1;
for(int i = n; i >= 2; i--){
update(mp[d[i]]);
}
for(int i = 2; i < n; i++){
deleteit(mp[d[i]]);
x = 0;
update(mp[d[i - 1]]);
x = 1;
solve(mp[d[i]]);
sum1 = sum;
x = 0;
solve(mp[d[i]]);
ans += sum * sum1;
//cout << sum << " " << sum1 << " " << mp[d[i]] << endl;
}
cout << ans << endl;
}
# | 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... |