Submission #2824983

---

Source Code Expand

#include<cstdio>
#include<algorithm>
#include<iostream>
#define N 1e9
using namespace std;
const int maxn = 3e5 + 5;
namespace SGT {
	struct node {
		int mn, add, ch[2];
	}t[maxn * 32];
	int cnt, root;
	int Create(int l, int r) {
		return t[++cnt] = (node) {l, 0, 0, 0}, cnt;
	}
	void push_up(int rt, int l, int r) {
		if(!t[rt].ch[0]) t[rt].ch[0] = Create(l, l + r >> 1);
		if(!t[rt].ch[1]) t[rt].ch[1] = Create(((l + r) >> 1) + 1, r);
		t[rt].mn = min(t[t[rt].ch[0]].mn, t[t[rt].ch[1]].mn);
	}
	void push_down(int rt, int l, int r) {
		if(t[rt].add) {
			int mid = l + r >> 1, *ls = &t[rt].ch[0], *rs = &t[rt].ch[1];
			if(!*ls) *ls = Create(l, mid);
			if(!*rs) *rs = Create(mid + 1, r);
			t[*ls].add += t[rt].add, t[*ls].mn += t[rt].add;
			t[*rs].add += t[rt].add, t[*rs].mn += t[rt].add;
			t[rt].add = 0;
		}
	}
	int Q(int l, int r, int tl, int tr, int & rt = root) {
		if(!rt) rt = Create(tl, tr);
		if(l == tl && r == tr) 
			return t[rt].mn;
		int mid = tl + tr >> 1;
		push_down(rt, tl, tr);
		if(r <= mid) return Q(l, r, tl, mid, t[rt].ch[0]);
		else if(l > mid) return Q(l, r, mid + 1, tr, t[rt].ch[1]);
		else return min(Q(l, mid, tl, mid, t[rt].ch[0]), Q(mid + 1, r, mid + 1, tr, t[rt].ch[1]));
	}
	void add(int l, int r, int tl, int tr, int dt, int & rt = root) {
		if(!rt) rt = Create(tl, tr);
		if(tl == l && tr == r) 
			return t[rt].add += dt, t[rt].mn += dt, void();
		int mid = tl + tr >> 1;
		push_down(rt, tl, tr);
		if(r <= mid) add(l, r, tl, mid, dt, t[rt].ch[0]);
		else if(l > mid) add(l, r, mid + 1, tr, dt, t[rt].ch[1]);
		else add(l, mid, tl, mid, dt, t[rt].ch[0]), add(mid + 1, r, mid + 1, tr, dt, t[rt].ch[1]);
		push_up(rt, tl, tr);
	}
}
int n, a[maxn], ans;
int main() {
	scanf("%d", &n);
	for(register int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	for(register int i = 1; i <= n; ++i) {
		ans += SGT :: Q(a[i], N, 0, N) - a[i];
		SGT :: add(0, a[i] - 1, 0, N, 1);
	}
	printf("%d", ans);
	return 0;
}

Submission Info

Compile Error

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

Judge Result