Submission #3831909

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int MAXN = 200005;
const int MAXT = 530000;

int n, a[MAXN];
vector<int> v;

struct seg{
	pi  tree[MAXT];
	int lazy[MAXT];
	void init(int s, int e, int p, vector<int> &v){
		if(s == e){
			tree[p] = pi(v[s], s);
			return;
		}
		int m = (s + e) / 2;
		init(s, m, 2*p, v);
		init(m+1, e, 2*p+1, v);
		tree[p] = min(tree[2*p], tree[2*p+1]);
	}
	void lazydown(int p){
		tree[2*p].first += lazy[p];
		tree[2*p+1].first += lazy[p];
		lazy[2*p] += lazy[p];
		lazy[2*p+1] += lazy[p];
		lazy[p] = 0;
	}
	void add(int s, int e, int ps, int pe, int p, int v){
		if(e < ps || pe < s) return;
		if(s <= ps && pe <= e){
			tree[p].first += v;
			lazy[p] += v;
			return;
		}
		int pm = (ps + pe) / 2;
		lazydown(p);
		add(s, e, ps, pm, 2*p, v);
		add(s, e, pm+1, pe, 2*p+1, v);
		tree[p] = min(tree[2*p], tree[2*p+1]);
	}
	pi query(int s, int e, int ps, int pe, int p){
		if(e < ps || pe < s) return pi(2e9, -1);
		if(s <= ps && pe <= e) return tree[p];
		int pm = (ps + pe) / 2;
		lazydown(p);
		return min(query(s, e, ps, pm, 2*p), query(s, e, pm+1, pe, 2*p+1));
	}
}seg;

int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d",&a[i]);
		v.push_back(a[i]);
	}
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	seg.init(0, v.size() - 1, 1, v);
	lint ans = 0;
	for(int i=0; i<n; i++){
		a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
		auto ret = seg.query(a[i], v.size() - 1, 0, v.size() - 1, 1);
		ans += ret.first - v[a[i]];
		seg.add(0, ret.second - 1, 0, v.size() - 1, 1, 1);
	}
	cout << ans << endl;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:54:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:56:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^

Judge Result