Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define fr(i, n, m) for(int i = (n); i < (m); i ++)
- #define pb push_back
- #define st first
- #define nd second
- #define pq priority_queue
- #define all(x) begin(x), end(x)
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef pair<int,int> pii;
- ll const inf = 1e9;
- ll const mod = 1e9 + 7;
- ld const eps = 1e-13;
- int a[1000001];
- int idx[1000001];
- int n;
- ll bit[1000001];
- ll sum(int k){
- ll s = 0;
- while(k > 0){
- s += bit[k];
- k -= k&-k;
- }
- return s;
- }
- void update(int k, int x){
- while(k <= n){
- bit[k] += x;
- k += k&-k;
- }
- }
- bool cmp(int i, int j){
- return a[i] < a[j];
- }
- int main()
- {
- cin >> n;
- fr(i, 0, n){
- cin >> a[i];
- idx[i] = i;
- }
- sort(idx, idx + n, cmp);
- ll ans = 0;
- fr(i, 0, n){
- ans += (ll)sum(n) - sum(idx[i]);
- update(idx[i] + 1, 1);
- }
- cout << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement