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 | a966cdf3732ec3e635a3a1c66f5fe7f4dcf4682a (patch) | |
| tree | 9d79575d43f260ff344a3bcbe30c5528a50861f8 /works/solutions/acwing | |
| parent | b312fa43308e3fb24730127e6c063624e7648ff2 (diff) | |
| download | crupest-a966cdf3732ec3e635a3a1c66f5fe7f4dcf4682a.tar.gz crupest-a966cdf3732ec3e635a3a1c66f5fe7f4dcf4682a.tar.bz2 crupest-a966cdf3732ec3e635a3a1c66f5fe7f4dcf4682a.zip | |
import(solutions): Add problem 1215.
Diffstat (limited to 'works/solutions/acwing')
| -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;
+}
|