Advertisement
Guest User

Untitled

a guest
Nov 28th, 2014
189
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.16 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <algorithm>
  6. #include <cstdlib>
  7. #include <cmath>
  8. #include <vector>
  9. #include <map>
  10. #include <set>
  11. #include <queue>
  12. #include <string>
  13. #include <cstring>
  14. #include <cassert>
  15. #include <ctime>
  16. using namespace std;
  17.  
  18. typedef long long int int64;
  19.  
  20. const int INF = (int)1e9;
  21.  
  22. const int N = 100500;
  23.  
  24. struct FenwickTree
  25. {
  26.     int a[N];
  27.  
  28.     FenwickTree()
  29.     {
  30.         clear();
  31.     }
  32.  
  33.     void clear()
  34.     {
  35.         memset(a, 0, sizeof(a));
  36.     }
  37.  
  38.     void add(int p, int val)
  39.     {
  40.         for (int i = p; i < N; i = (i | (i + 1)))
  41.             a[i] += val;
  42.     }
  43.  
  44.     int get_prefix_sum(int p)
  45.     {
  46.         if (p < 0)
  47.             return 0;
  48.         int sum = 0;
  49.         for (int i = p; i >= 0; i = (i & (i + 1)) - 1)
  50.             sum += a[i];
  51.         return sum;
  52.     }
  53.  
  54.     int get_sum(int l, int r)
  55.     {
  56.         return get_prefix_sum(r) - get_prefix_sum(l - 1);
  57.     }
  58. };
  59.  
  60. FenwickTree tree;
  61.  
  62. int64 get_inv_cnt(vector<int> a)
  63. {
  64.     tree.clear();
  65.     vector<int> compress(a.begin(), a.end());
  66.     sort(compress.begin(), compress.end());
  67.     compress.resize(unique(compress.begin(), compress.end()) - compress.begin());
  68.     for (int i = 0; i < (int)a.size(); i++)
  69.         a[i] = lower_bound(compress.begin(), compress.end(), a[i]) - compress.begin();
  70.  
  71.     int64 res = 0;
  72.     for (int i = 0; i < (int)a.size(); i++)
  73.     {
  74.         res += tree.get_sum(a[i] + 1, N - 1);
  75.         tree.add(a[i], 1);
  76.     }
  77.     return res;
  78.  
  79.     /*
  80.     int res = 0;
  81.     for (int i = 0; i < (int)a.size(); i++)
  82.         for (int j = 0; j < i; j++)
  83.             if (a[j] > a[i])
  84.                 res++;
  85.     return res;
  86.     */
  87. }
  88.  
  89. int64 get_inv_cnt(vector<pair<int, int> > list)
  90. {
  91.     vector<int> a, b;
  92.     for (int i = 0; i < (int)list.size(); i++)
  93.     {
  94.         a.push_back(list[i].first);
  95.         b.push_back(list[i].second);
  96.     }
  97.     int64 res = get_inv_cnt(a) + get_inv_cnt(b);
  98.     return res;
  99. }
  100.  
  101. int slow_solve(vector<pair<int, int> > list)
  102. {
  103.     sort(list.begin(), list.end());
  104.     int res = INF;
  105.  
  106.     do
  107.     {
  108.         int cur_res = get_inv_cnt(list);
  109.         res = min(res, cur_res);
  110.     } while (next_permutation(list.begin(), list.end()));
  111.    
  112.     return res;
  113. }
  114.  
  115. int solve1(vector<pair<int, int> > list)
  116. {
  117.     sort(list.begin(), list.end());
  118.     int res1 = get_inv_cnt(list);
  119.  
  120.     for (int i = 0; i < (int)list.size(); i++)
  121.         swap(list[i].first, list[i].second);
  122.  
  123.     sort(list.begin(), list.end());
  124.     int res2 = get_inv_cnt(list);
  125.  
  126.     return min(res1, res2);
  127. }
  128.  
  129. vector<pair<int, int> > gen()
  130. {
  131.     int n = rand() % 7 + 1;
  132.     vector<pair<int, int> > list;
  133.     for (int i = 0; i < n; i++)
  134.         list.push_back(make_pair(rand() % 3, rand() % 3));
  135.     return list;
  136. }
  137.  
  138. vector<pair<int, int> > scan()
  139. {
  140.     int n;
  141.     scanf("%d", &n);
  142.     vector<pair<int, int> > list(n);
  143.     for (int i = 0; i < n; i++)
  144.         scanf("%d%d", &list[i].first, &list[i].second);
  145.     return list;
  146. }
  147.  
  148. void stress()
  149. {
  150.     int it = 0;
  151.     while (true)
  152.     {
  153.         auto l = gen();
  154.         int ans1 = slow_solve(l);
  155.         int ans2 = solve1(l);
  156.        
  157.         cerr << it++ << endl;
  158.        
  159.         if (ans1 == ans2)
  160.             continue;
  161.  
  162.         cout << "NO =(" << endl;
  163.         break;
  164.     }
  165. }
  166.  
  167. void solve()
  168. {
  169.     auto l = scan();
  170.     //cout << slow_solve(l) << endl;
  171.     cout << solve1(l) << endl;
  172. }
  173.  
  174. int main()
  175. {
  176.     freopen("john.in", "r", stdin);
  177.     freopen("john.out", "w", stdout);
  178.  
  179.     srand(time(0));
  180.  
  181.     //stress();
  182.     solve();
  183.  
  184.     return 0;
  185. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement