Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <algorithm>
- #include <set>
- #include <cstring>
- #include <fstream>
- using namespace std;
- using namespace std;
- long long my_merge(vector<int>&v, vector<int> &tmp, int L, int mid, int R) {
- int i = L, j = mid;
- int idx = L;
- long long inversions = 0;
- while(i <= mid - 1 and j <= R) {
- if(v[i] <= v[j]) {
- tmp[idx++] = v[i++];
- }
- else {
- tmp[idx++] = v[j++];
- inversions += mid - i;
- }
- }
- while(i <= mid - 1) {
- tmp[idx++] = v[i++];
- }
- while(j <= R) {
- tmp[idx++] = v[j++];
- }
- for(int id = L; id <= R; id++) {
- v[id] = tmp[id];
- }
- return inversions;
- }
- long long merge_sort(vector<int> &v, vector<int> &tmp, int L, int R) {
- int mid = (L + R) / 2;
- long long inversions = 0;
- if(R > L) {
- inversions += merge_sort(v, tmp, L, mid);
- inversions += merge_sort(v, tmp, mid + 1, R);
- inversions += my_merge(v, tmp, L, mid + 1, R);
- }
- return inversions;
- }
- int main()
- {
- int n;
- cin >> n;
- vector<int> v(n);
- for(int i = 0; i < n; i++) {
- cin >> v[i];
- }
- vector<int> tmp(n);
- cout << merge_sort(v, tmp, 0, n - 1) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement