Submission #2019574

---

Source Code Expand

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
//#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

const double PI = acos(-1);
const double EPS = 1e-9;

const int MX = 1<<20;
const int MM = 1000000007;

struct Tree{
	struct node{
		pii v;
		int add;
	};
	node t[MX*2];
	void update(int l, int r, int v, int n = 1, int s = 0, int e = MX-1){
		if( r < s || e < l ) return;
		else if( l <= s && e <= r ){
			t[n].v.first += v;
			t[n].add += v;
		}
		else{
			int m = (s+e) / 2;
			update(l, r, v, n*2, s, m);
			update(l, r, v, n*2+1, m+1, e);
			t[n].v = min(t[n*2].v, t[n*2+1].v);
			t[n].v.first += t[n].add;
		}
	}
	pii read(int l, int r, int n = 1, int s = 0, int e = MX-1){
		if( r < s || e < l ) return pii(1e9, -1);
		else if( l <= s && e <= r ) return t[n].v;
		else{
			int m = (s+e) / 2;
			pii res = min(read(l, r, n*2, s, m), read(l, r, n*2+1, m+1, e));
			res.first += t[n].add;
			return res;
		}
	}
} tree;

int A[MX];

int main()
{
	int N;
	vector<int> X;
	scanf("%d", &N);
	for(int i = 1; i <= N; i++) scanf("%d", A+i), X.push_back(A[i]);
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());

	for(int i = 0; i < X.size(); i++) tree.t[i+MX].v = pii(X[i], i);
	for(int i = MX-1; i >= 1; i--) tree.t[i].v = min(tree.t[i*2].v, tree.t[i*2+1].v);

	ll ans = 0;
	for(int i = 1; i <= N; i++){
		int v = A[i], w = lower_bound(X.begin(), X.end(), A[i]) - X.begin();
		pii t = tree.read(w, X.size()-1);
		ans += t.first - v;
		tree.update(0, t.second-1, 1);
	}
	printf("%lld\n", ans);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:79:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
./Main.cpp:80:65: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= N; i++) scanf("%d", A+i), X.push_back(A[i]);
                                                                 ^

Judge Result