# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
516445 | Jomnoi | Mountains (NOI20_mountains) | C++17 | 318 ms | 36844 KiB |
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>
#define DEBUG 0
using namespace std;
const int MX = 3e5 + 10;
long long h[MX];
class Fenwick {
protected :
int N;
vector <int> fenwick;
public :
Fenwick(const int &n) : N(n) {
fenwick.resize(N, 0);
}
int lsb(const int &x) const {
return x & -x;
}
void update(const int &i, const int &val) {
for(int idx = i; idx <= N; idx += lsb(idx)) {
fenwick[idx] += val;
}
}
int query(const int &i) const {
int res = 0;
for(int idx = i; idx > 0; idx -= lsb(idx)) {
res += fenwick[i];
}
return res;
}
};
int main() {
int n;
scanf(" %d", &n);
set <long long> s;
unordered_map <long long, int> mp;
for(int i = 1; i <= n; i++) {
scanf(" %lld", &h[i]);
s.insert(h[i]);
}
int cnt = 0;
for(auto v : s) {
mp[v] = ++cnt;
}
Fenwick fw1(cnt), fw2(cnt);
for(int i = 2; i <= n; i++) {
fw2.update(mp[h[i]], 1);
}
fw1.update(mp[h[1]], 1);
long long ans = 0;
for(int i = 2; i < n; i++) {
fw2.update(mp[h[i]], -1);
ans += 1ll * fw1.query(mp[h[i]] - 1) * fw2.query(mp[h[i]] - 1);
fw1.update(mp[h[i]], 1);
}
cout << ans;
return 0;
}
Compilation message (stderr)
# | 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... |