fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el '\n'
  5. #define TASK "test"
  6. #define fi first
  7. #define se second
  8.  
  9. #define all(v) (v).begin(), (v).end()
  10. #define rall(v) (v).rbegin(), (v).rend()
  11. #define sz(s) (int)(s).size()
  12.  
  13. #define FOR(i, a, b, s) for (auto i = (a), _b = (b); i <= _b; i += (s))
  14. #define FORD(i, a, b, s) for (auto i = (a), _b = (b); i >= _b; i -= (s))
  15. #define REP(i, n) for (int i = 1, _n = (n); i <= _n; ++i)
  16. #define FORE(i, v) for (auto &i : (v))
  17.  
  18. #define ShinzouWoSasageyo ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  19. #define FoundingTitan if (fopen(TASK ".inp", "r")) freopen(TASK ".inp", "r", stdin), freopen(TASK ".out", "w", stdout);
  20.  
  21. using namespace std;
  22.  
  23. template<class X, class Y>
  24. bool minimize(X &x, const Y &y)
  25. {
  26.     if (x > y)
  27.     {
  28.         x = y;
  29.         return true;
  30.     }
  31.     return false;
  32. }
  33.  
  34. template<class X, class Y>
  35. bool maximize(X &x, const Y &y)
  36. {
  37.     if (x < y)
  38.     {
  39.         x = y;
  40.         return true;
  41.     }
  42.     return false;
  43. }
  44.  
  45. const int N      = 6e4 + 9;
  46. const int INT_MX = (1LL << 30);
  47. const ll LL_MX   = (1LL << 62);
  48. const int mod    = 1e9 + 7;
  49. const int base   = 131;
  50.  
  51. /*
  52.      Author: Minh Son Nguyen - Huynh Dong Nhi Nguyen - Tanh Linh High School
  53.      A2 - K39 (2025 - 2028)
  54. */
  55.  
  56. int n;
  57. vector<int> a;
  58. int ans = 0;
  59.  
  60. vector<int> Merge(const vector<int> &a, const vector<int> &b)
  61. {
  62.     vector<int> c;
  63.     int i = 0, j = 0;
  64.     while (i < sz(a) || j < sz(b))
  65.     {
  66.         if (i == sz(a))
  67.         {
  68.             c.push_back(b[j++]);
  69.         }
  70.         else if (j == sz(b))
  71.         {
  72.             c.push_back(a[i++]);
  73.         }
  74.         else if (a[i] <= b[j])
  75.         {
  76.             c.push_back(a[i++]);
  77.         }
  78.         else
  79.         {
  80.             ans += sz(a) - i;
  81.             c.push_back(b[j++]);
  82.         }
  83.     }
  84.     return c;
  85. }
  86.  
  87. void Msort(vector<int> &a, int l, int r)
  88. {
  89.     if (l == r) return;
  90.  
  91.     int mid = (l + r) >> 1;
  92.     Msort(a, l, mid);
  93.     Msort(a, mid + 1, r);
  94.  
  95.     vector<int> b, c;
  96.     FOR (i, l, mid, 1) 
  97.     {
  98.         b.push_back(a[i]);
  99.     }
  100.     FOR (i, mid + 1, r, 1)
  101.     {
  102.         c.push_back(a[i]);
  103.     }
  104.  
  105.     b = Merge(b, c);
  106.     FOR (i, l, r, 1)
  107.     {
  108.         a[i] = b[i - l];
  109.     }
  110.  
  111. }
  112.  
  113. namespace ErenxMikasa
  114. {
  115.     /*
  116.          Welcome to the battlefield :D
  117.          Now, let's solve the problem!
  118.     */
  119.  
  120.     void process(void)
  121.     {
  122.         cin >> n;
  123.         a.resize(n + 9);
  124.         FOR (i, 1, n, 1)
  125.         {
  126.             cin >> a[i];
  127.         }
  128.  
  129.         Msort(a, 1, n);
  130.         cout << ans;
  131.  
  132.     }
  133. }
  134.  
  135. signed main(void)
  136. {
  137.     ShinzouWoSasageyo;
  138.     FoundingTitan;
  139.     ErenxMikasa::process();
  140.     return 0;
  141. }
  142.  
  143. /*
  144.     That is the end of my template, let's drink a coffee and chill with my code ~~
  145.     Dedicate your heart! ~~~ Shinzou Wo Sasageyo! - Scout Regiment
  146.     Tatakae! ~~~ Keep fighting - Eren Yeager
  147. */
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
3
3
1
2
stdout
copy 
2
https://ideone.com/hLrUcG
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!