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 <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll=long long;
#define N 300005
#define ALL(x) x.begin(), x.end()
#define int long long
int ans, n, a[N];
struct node
{
node *l, *r;
int a;
node(int b) : a(b), l(nullptr), r(nullptr) {}
node (node *l_, node *r_) : l(l_), r(r_), a((l_?l_->a:0) + (r_?r_->a:0)) {}
};
node *build(int l, int r)
{
if (l == r) return new node(0);
return new node(build(l, (l+r)/2), build((l+r)/2+1, r));
}
node *upd(node *v, int l, int r, int p)
{
if (l == r) return new node(v->a + 1);
if (p <= (l+r)/2) return new node(upd(v->l, l, (l+r)/2, p), v->r);
return new node(v->l, upd(v->r, (l+r)/2+1, r, p));
}
int count(node *vl, node *vr, int l, int r, int x, int y)
{
if (y < l || r < x) return 0;
if (x <= l && r <= y) return vr->a - vl->a;
return count(vl->l, vr->l, l, (l+r)/2, x, y) + count(vl->r, vr->r, (l+r)/2+1, r, x, y);
}
node *root[N];
vector<int> C;
signed main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i], C.push_back(a[i]);
sort(ALL(C));
root[0] = build(0, n);
for (int i = 0; i < n; ++i) a[i] = lower_bound(ALL(C), a[i]) - C.begin(),
root[i+1] = upd(root[i], 0, n, a[i]);
for (int i = 1; i <= n; ++i)
{
int lft = count(root[0], root[i-1], 0, n, 0, a[i-1] - 1);
int rgt = count(root[i], root[n-1], 0, n, 0, a[i-1] - 1);
ans += lft * rgt;
}
cout << ans;
return 0;
}
Compilation message (stderr)
Mountains.cpp: In constructor 'node::node(long long int)':
Mountains.cpp:24:9: warning: 'node::a' will be initialized after [-Wreorder]
24 | int a;
| ^
Mountains.cpp:23:11: warning: 'node* node::l' [-Wreorder]
23 | node *l, *r;
| ^
Mountains.cpp:25:5: warning: when initialized here [-Wreorder]
25 | node(int b) : a(b), l(nullptr), r(nullptr) {}
| ^~~~
# | 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... |