Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstdlib>
- #include <cmath>
- #include <vector>
- #include <map>
- #include <set>
- #include <queue>
- #include <string>
- #include <cstring>
- #include <cassert>
- #include <ctime>
- using namespace std;
- typedef long long int int64;
- const int INF = (int)1e9;
- const int N = 100500;
- struct FenwickTree
- {
- int a[N];
- FenwickTree()
- {
- clear();
- }
- void clear()
- {
- memset(a, 0, sizeof(a));
- }
- void add(int p, int val)
- {
- for (int i = p; i < N; i = (i | (i + 1)))
- a[i] += val;
- }
- int get_prefix_sum(int p)
- {
- if (p < 0)
- return 0;
- int sum = 0;
- for (int i = p; i >= 0; i = (i & (i + 1)) - 1)
- sum += a[i];
- return sum;
- }
- int get_sum(int l, int r)
- {
- return get_prefix_sum(r) - get_prefix_sum(l - 1);
- }
- };
- FenwickTree tree;
- int64 get_inv_cnt(vector<int> a)
- {
- tree.clear();
- vector<int> compress(a.begin(), a.end());
- sort(compress.begin(), compress.end());
- compress.resize(unique(compress.begin(), compress.end()) - compress.begin());
- for (int i = 0; i < (int)a.size(); i++)
- a[i] = lower_bound(compress.begin(), compress.end(), a[i]) - compress.begin();
- int64 res = 0;
- for (int i = 0; i < (int)a.size(); i++)
- {
- res += tree.get_sum(a[i] + 1, N - 1);
- tree.add(a[i], 1);
- }
- return res;
- /*
- int res = 0;
- for (int i = 0; i < (int)a.size(); i++)
- for (int j = 0; j < i; j++)
- if (a[j] > a[i])
- res++;
- return res;
- */
- }
- int64 get_inv_cnt(vector<pair<int, int> > list)
- {
- vector<int> a, b;
- for (int i = 0; i < (int)list.size(); i++)
- {
- a.push_back(list[i].first);
- b.push_back(list[i].second);
- }
- int64 res = get_inv_cnt(a) + get_inv_cnt(b);
- return res;
- }
- int slow_solve(vector<pair<int, int> > list)
- {
- sort(list.begin(), list.end());
- int res = INF;
- do
- {
- int cur_res = get_inv_cnt(list);
- res = min(res, cur_res);
- } while (next_permutation(list.begin(), list.end()));
- return res;
- }
- int solve1(vector<pair<int, int> > list)
- {
- sort(list.begin(), list.end());
- int res1 = get_inv_cnt(list);
- for (int i = 0; i < (int)list.size(); i++)
- swap(list[i].first, list[i].second);
- sort(list.begin(), list.end());
- int res2 = get_inv_cnt(list);
- return min(res1, res2);
- }
- vector<pair<int, int> > gen()
- {
- int n = rand() % 7 + 1;
- vector<pair<int, int> > list;
- for (int i = 0; i < n; i++)
- list.push_back(make_pair(rand() % 3, rand() % 3));
- return list;
- }
- vector<pair<int, int> > scan()
- {
- int n;
- scanf("%d", &n);
- vector<pair<int, int> > list(n);
- for (int i = 0; i < n; i++)
- scanf("%d%d", &list[i].first, &list[i].second);
- return list;
- }
- void stress()
- {
- int it = 0;
- while (true)
- {
- auto l = gen();
- int ans1 = slow_solve(l);
- int ans2 = solve1(l);
- cerr << it++ << endl;
- if (ans1 == ans2)
- continue;
- cout << "NO =(" << endl;
- break;
- }
- }
- void solve()
- {
- auto l = scan();
- //cout << slow_solve(l) << endl;
- cout << solve1(l) << endl;
- }
- int main()
- {
- freopen("john.in", "r", stdin);
- freopen("john.out", "w", stdout);
- srand(time(0));
- //stress();
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement