diff options
| author | crupest <crupest@outlook.com> | 2021-03-05 20:36:34 +0800 |
|---|---|---|
| committer | crupest <crupest@outlook.com> | 2021-03-05 20:36:34 +0800 |
| commit | fbf3cbb2af53546a0c2237ab2a4787acbd08e24e (patch) | |
| tree | 05ca52e6c2eba51f2559f7ae60e379a9afe3d01a /works | |
| parent | 39da64eff75ec43debcc8b1cd0d91a33ae395487 (diff) | |
| download | crupest-fbf3cbb2af53546a0c2237ab2a4787acbd08e24e.tar.gz crupest-fbf3cbb2af53546a0c2237ab2a4787acbd08e24e.tar.bz2 crupest-fbf3cbb2af53546a0c2237ab2a4787acbd08e24e.zip | |
import(solutions): Add problem 1215.
Diffstat (limited to 'works')
| -rw-r--r-- | works/solutions/acwing/1215.cpp | 59 |
1 files changed, 59 insertions, 0 deletions
diff --git a/works/solutions/acwing/1215.cpp b/works/solutions/acwing/1215.cpp new file mode 100644 index 0000000..d6832b3 --- /dev/null +++ b/works/solutions/acwing/1215.cpp @@ -0,0 +1,59 @@ +#include <cstring>
+#include <iostream>
+
+const int MAX = 1000010; // Why 1000001 is not ok!?
+
+int n;
+int H[100001];
+int bit[MAX];
+int reverse_pairs[100001];
+
+int lowbit(int x) { return x & -x; }
+
+void add(int x, int y) {
+ for (int i = x; i < MAX; i += lowbit(i)) {
+ bit[i] += y;
+ }
+}
+
+int query(int x) {
+ int result = 0;
+ for (int i = x; i != 0; i -= lowbit(i)) {
+ result += bit[i];
+ }
+ return result;
+}
+
+int main() {
+ std::ios_base::sync_with_stdio(false);
+ std::cin.tie(nullptr);
+
+ std::cin >> n;
+
+ for (int i = 1; i <= n; i++) {
+ std::cin >> H[i];
+ H[i]++;
+ }
+
+ for (int i = 1; i <= n; i++) {
+ add(H[i], 1);
+ reverse_pairs[i] = i - query(H[i]);
+ }
+
+ std::memset(bit, 0, sizeof bit);
+
+ for (int i = n; i >= 1; i--) {
+ add(H[i], 1);
+ reverse_pairs[i] += query(H[i] - 1);
+ }
+
+ long long result = 0;
+
+ for (int i = 1; i <= n; i++) {
+ result += (1LL + reverse_pairs[i]) * reverse_pairs[i] / 2;
+ }
+
+ std::cout << result;
+
+ return 0;
+}
|