Untitled
unknown
plain_text
a year ago
1.5 kB
8
Indexable
#include <bits/stdc++.h> using namespace std; typedef long long LL; LL cnt = 0; void merge(vector<pair<int, int>> &arr, int l, int m, int r) { vector<pair<int, int>> tmp; int i = l, j = m + 1; while (i <= m && j <= r) { if (arr[i].second <= arr[j].second ) { cnt += m + 1 - i; tmp.emplace_back( make_pair( arr[i].first, arr[i].second ) ); i++; } else { tmp.emplace_back( make_pair( arr[j].first, arr[j].second ) ); j++; } } while (i <= m) { tmp.emplace_back( make_pair( arr[i].first, arr[i].second ) ); i++; } while (j <= r) { tmp.emplace_back( make_pair( arr[j].first, arr[j].second ) ); j++; } for (int k = 0; k < tmp.size(); k++) { arr[l + k] = tmp[k]; } } void merge_sort(vector<pair<int, int>> &arr, int l, int r) { if (l < r) { int m = (l + r) / 2; merge_sort(arr, l, m); merge_sort(arr, m + 1, r); merge(arr, l, m, r); } } int main() { int n; cin >> n; vector<pair<int, int>> pts(n); for (auto &x : pts ) { int u, r; cin >> u >> r; x.first = min(u, r); x.second = max(u, r); } sort( pts.begin(), pts.end() ); merge_sort(pts, 0, n - 1); cout << cnt << "\n"; }
Editor is loading...
Leave a Comment