fork download 
  1. /*****************************************************************************************************************/
  2. /*
  3.                                         $,  $,     ,
  4.                                         "ss.$ss. .s'
  5.                                 ,     .ss$$$$$$$$$$s,
  6.                                 $. s$$$$$$$$$$$$$$`$$Ss
  7.                                 "$$$$$$$$$$$$$$$$$$o$$$       ,
  8.                                s$$$$$$$$$$$$$$$$$$$$$$$$s,  ,s
  9.                               s$$$$$$$$$"$$$$$$""""$$$$$$"$$$$$,
  10.                               s$$$$$$$$$$s""$$$$ssssss"$$$$$$$$"
  11.                              s$$$$$$$$$$'         `"""ss"$"$s""
  12.                              s$$$$$$$$$$,              `"""""$  .s$$s
  13.                              s$$$$$$$$$$$$s,...               `s$$'  `
  14.                          `ssss$$$$$$$$$$$$$$$$$$$$####s.     .$$"$.   , s-
  15.                            `""""$$$$$$$$$$$$$$$$$$$$#####$$$$$$"     $.$'
  16.                                  "$$$$$$$$$$$$$$$$$$$$$####s""     .$$$|
  17.                                   "$$$$$$$$$$$$$$$$$$$$$$$$##s    .$$" $
  18.                                    $$""$$$$$$$$$$$$$$$$$$$$$$$$$$$$$"   `
  19.                                   $$"  "$"$$$$$$$$$$$$$$$$$$$$S""""'
  20.                              ,   ,"     '  $$$$$$$$$$$$$$$$####s
  21.                              $.          .s$$$$$$$$$$$$$$$$$####"
  22.                  ,           "$s.   ..ssS$$$$$$$$$$$$$$$$$$$####"
  23.                  $           .$$$S$$$$$$$$$$$$$$$$$$$$$$$$#####"
  24.                  Ss     ..sS$$$$$$$$$$$$$$$$$$$$$$$$$$$######""
  25.                   "$$sS$$$$$$$$$$$$$$$$$$$$$$$$$$$########"
  26.            ,      s$$$$$$$$$$$$$$$$$$$$$$$$#########""'
  27.            $    s$$$$$$$$$$$$$$$$$$$$$#######""'      s'         ,
  28.            $$..$$$$$$$$$$$$$$$$$$######"'       ....,$$....    ,$
  29.             "$$$$$$$$$$$$$$$######"' ,     .sS$$$$$$$$$$$$$$$$s$$
  30.               $$$$$$$$$$$$#####"     $, .s$$$$$$$$$$$$$$$$$$$$$$$$s.
  31.    )          $$$$$$$$$$$#####'      `$$$$$$$$$###########$$$$$$$$$$$.
  32.   ((          $$$$$$$$$$$#####       $$$$$$$$###"       "####$$$$$$$$$$
  33.   ) \         $$$$$$$$$$$$####.     $$$$$$###"             "###$$$$$$$$$   s'
  34.  (   )        $$$$$$$$$$$$$####.   $$$$$###"                ####$$$$$$$$s$$'
  35.  )  ( (       $$"$$$$$$$$$$$#####.$$$$$###'                 .###$$$$$$$$$$"
  36.  (  )  )   _,$"   $$$$$$$$$$$$######.$$##'                .###$$$$$$$$$$
  37.  ) (  ( \.         "$$$$$$$$$$$$$#######,,,.          ..####$$$$$$$$$$$"
  38. (   )$ )  )        ,$$$$$$$$$$$$$$$$$$####################$$$$$$$$$$$"
  39. (   ($$  ( \     _sS"  `"$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$S$$,
  40.  )  )$$$s ) )  .      .   `$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$"'  `$$
  41.   (   $$$Ss/  .$,    .$,,s$$$$$$##S$$$$$$$$$$$$$$$$$$$$$$$$S""        '
  42.     \)_$$$$$$$$$$$$$$$$$$$$$$$##"  $$        `$$.        `$$.
  43.         `"S$$$$$$$$$$$$$$$$$#"      $          `$          `$
  44.             `"""""""""""""'         '           '           '
  45. */
  46. #include<bits/stdc++.h>
  47. using namespace std;
  48. #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  49. #define ll long long
  50. #define vll vector<ll>
  51. #define vvll vector<vll>
  52. #define FOR(i,a,b) for(ll i = a;i<b;i++)
  53. #define pll pair<ll,ll>
  54. #define pb push_back
  55. int n;
  56. template <typename T> struct BIT{
  57. 	int size;
  58. 	vector<T> bit;
  59. 	BIT(int n){
  60. 		size = n;
  61. 		bit.assign(n+1,0);
  62. 	}
  63. 	void update(int idx, T val){
  64. 		while(idx <=size){
  65. 			bit[idx]+= val;
  66. 			idx+= idx&(-idx);
  67. 		}
  68. 	}
  69. 	T query(int idx){
  70. 		T sum = 0;
  71. 		while(idx > 0){
  72. 			sum+=bit[idx];
  73. 			idx-=idx&(-idx);
  74. 		}
  75. 		return sum;
  76. 	}
  77. 	T sum(int l,int r){
  78. 		return query(r) - query(l-1);
  79. 	}
  80. };
  81. void solve(){
  82. 	cin >> n;
  83. 	vector<ll> a(n);
  84. 	for(int i = 0;i<n;i++){
  85. 		cin >>a[i];
  86. 	}
  87. 	vector<ll> b = a;
  88. 	sort(b.begin(),b.end());
  89. 	map<ll,int> mp;
  90. 	int S = 1;
  91. 	for(ll i : b){
  92. 		if(mp.find(i) == mp.end()){
  93. 			mp[i] = S++;
  94. 		}
  95. 	}
  96. 	int C = mp.size();
  97. 	for(int i = 0;i<n;i++){
  98. 		a[i] = mp[a[i]];
  99. 	}
  100. 	BIT<ll> ftree(C);
  101. 	vector<ll> pref(n+1,0);
  102. 	for(int i = 1;i<=n;i++){
  103. 		int x = a[i-1];
  104. 		ll cnt = ftree.sum(x+1,C);
  105. 		pref[i] = pref[i-1]+cnt;
  106. 		ftree.update(x,1);
  107. 	}
  108. 	BIT<ll> stree(C);
  109. 	vector<ll> suff(n+1,0);
  110. 	reverse(a.begin(),a.end());
  111. 	for(int i = 1;i<=n;i++){
  112. 		int x = a[i-1];
  113. 		ll cnt = stree.sum(x+1,C);
  114. 		suff[i] = suff[i-1]+cnt;
  115. 		stree.update(x,1);
  116. 	}
  117. 	reverse(suff.begin()+1,suff.end());
  118. 	ll ans = LLONG_MAX;
  119. 	for(int i = 1;i<n;i++){
  120. 		ans = min(ans, pref[i]+suff[i+1]);
  121. 	}
  122. 	cout << ans;
  123. }
  124. int main(){
  125.     fast;
  126.     solve();
  127. }
  128.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
Standard input is empty
stdout 
9223372036854775807
https://ideone.com/wR0UsU
language:
C++14 (gcc 8.3)
created:
1 day 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!