fork download
copy 
  1. /*
  2.     Cred : SunnyYeahBoi
  3.     It's my last chance (⌐■_■)
  4.     Problem :
  5. */
  6.  
  7. #include<bits/stdc++.h>
  8.  
  9. using namespace std;
  10.  
  11. #define int long long
  12. #define double long double
  13. #define endl "\n"
  14. #define NAME "a"
  15.  
  16. const int MAXN = 1e6 + 5;
  17. const int inf = 1e18;
  18. const int MOD = 1e9 + 7;
  19.  
  20. void FileInput(){
  21.     if(fopen(NAME".inp" , "r") == NULL)
  22.         freopen(NAME".inp" , "w" , stdout);
  23.     freopen(NAME".inp" , "r" , stdin);
  24.     freopen(NAME".out" , "w" , stdout);
  25. }
  26.  
  27. int n;
  28. int a[MAXN];
  29. int cnt[MAXN];
  30.  
  31. struct Segtree{
  32.     vector<int> tree;
  33.     int n;
  34.  
  35.     void init(int x){
  36.         n = x + 1;
  37.         tree.resize(4 * n + 1 , 0);
  38.     }
  39.  
  40.     void update(int vt , int l , int r , int x){
  41.         if(l == r){
  42.             tree[vt]++;
  43.             return;
  44.         }
  45.         int mid = (l + r) / 2;
  46.  
  47.         if(x <= mid)
  48.             update(vt * 2 , l , mid , x);
  49.         else update(vt * 2 + 1 , mid + 1 , r , x);
  50.  
  51.         tree[vt] = tree[vt * 2] + tree[vt * 2 + 1];
  52.     }
  53.  
  54.     void update(int x){
  55.         update(1 , 1 , n , x);
  56.     }
  57.  
  58.     int get(int vt , int l , int r , int u , int v){
  59.         if(u <= l && r <= v)
  60.             return tree[vt];
  61.  
  62.         if(l > v || r < u)
  63.             return 0;
  64.  
  65.         int mid = (l + r) / 2;
  66.         return get(vt * 2 , l , mid , u , v) + get(vt * 2 + 1 , mid + 1 , r , u , v);
  67.     }
  68.  
  69.     int get(int l , int r){
  70.         return get( 1 , 1 , n , l , r);
  71.     }
  72. } ST;
  73.  
  74. void solve(){
  75.     cin >> n;
  76.     for(int i = 1 ; i <= n ; i++)
  77.         cin >> a[i];
  78.  
  79.     map<int , int> mp;
  80.     for(int i = 1 ; i <= n ; i ++)
  81.         mp[a[i]]++;
  82.     mp[-inf];
  83.  
  84.     vector<int> nums;
  85.     for(auto x : mp)
  86.         nums.push_back(x.first);
  87.  
  88.     // for(auto x : nums)
  89.     //     cout << x << endl;
  90.  
  91.     ST.init(n);
  92.  
  93.     int res = 0;
  94.     for(int i = 1 ; i <= n ; i++){
  95.         int id = lower_bound(nums.begin() , nums.end() , a[i]) - nums.begin();
  96.         // cout << i << " " << id << " " << ST.get(1 , id - 1)<< endl;
  97.         res += ST.get(id + 1 , (int)nums.size() - 1);
  98.         ST.update(id);
  99.  
  100.         /*
  101.             truy vấn:
  102.                 lấy tổng 0 -> x - 1
  103.                 cập nhật a[x] += 1
  104.  
  105.             => Segtree
  106.         */
  107.     }
  108.     cout << res << endl;
  109. }
  110.  
  111. int32_t main(){
  112.     //FileInput();
  113.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  114.     int t = 1;
  115.     // cin >> t;
  116.     while(t--)
  117.         solve();
  118.     return 0;
  119. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/xV4URJ
language:
C++14 (gcc 8.3)
created:
11 hours 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!