Submission #1817105

---

Source Code Expand

#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN = 200000;
const int MAXS = 4 * MAXN;

int n;
int a[MAXN];
int b[MAXN], nb;

int sidx[MAXS], sval[MAXS], slazy[MAXS];
void sapply(int x, int val) {
	sval[x] += val, slazy[x] += val;
}
void spush(int x) {
	if (slazy[x] != 0) sapply(2 * x + 1, slazy[x]), sapply(2 * x + 2, slazy[x]), slazy[x] = 0;
}
void spull(int x) {
	sidx[x] = sidx[2 * x + 1], sval[x] = sval[2 * x + 1];
	if (sval[2 * x + 2] < sval[x]) sidx[x] = sidx[2 * x + 2], sval[x] = sval[2 * x + 2];
}
void sinit(int x, int l, int r) {
	slazy[x] = 0;
	if (l == r) {
		sidx[x] = l; sval[x] = b[l];
	} else {
		int m = l + (r - l) / 2;
		sinit(2 * x + 1, l, m); sinit(2 * x + 2, m + 1, r);
		spull(x);
	}
}
pair<int, int> sget(int x, int l, int r, int L, int R) {
	if (L <= l&&r <= R) {
		return MP(sidx[x], sval[x]);
	} else {
		spush(x);
		int m = l + (r - l) / 2;
		pair<int, int> ret = MP(-1, INT_MAX);
		if (L <= m) { pair<int, int> cur = sget(2 * x + 1, l, m, L, R); if (cur.second < ret.second) ret = cur; }
		if (m + 1 <= R) { pair<int, int> cur = sget(2 * x + 2, m + 1, r, L, R); if (cur.second < ret.second) ret = cur; }
		return ret;
	}
}
void smod(int x, int l, int r, int L, int R, int VAL) {
	if (L <= l&&r <= R) {
		sapply(x, VAL);
	} else {
		spush(x);
		int m = l + (r - l) / 2;
		if (L <= m) smod(2 * x + 1, l, m, L, R, VAL);
		if (m + 1 <= R) smod(2 * x + 2, m + 1, r, L, R, VAL);
		spull(x);
	}
}


void run() {
	scanf("%d", &n); REP(i, n) scanf("%d", &a[i]);

	nb = 0; REP(i, n) b[nb++] = a[i]; sort(b, b + nb); nb = unique(b, b + nb) - b;
	sinit(0, 0, nb - 1);

	ll ret = 0;
	REP(i, n) {
		int idx = lower_bound(b, b + nb, a[i]) - b;
		pair<int, int> val = sget(0, 0, nb - 1, idx, nb - 1);
		ret += val.second - b[idx];
		if (val.first != 0) smod(0, 0, nb - 1, 0, val.first - 1, 1);
	}
	printf("%lld\n", ret);
}

int main() {
	run();
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void run()’:
./Main.cpp:87:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n); REP(i, n) scanf("%d", &a[i]);
                 ^
./Main.cpp:87:47: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n); REP(i, n) scanf("%d", &a[i]);
                                               ^

Judge Result