Submission #1820482

---

Source Code Expand

#include<cstdio>
#include<algorithm>
using namespace std;
#define INF ((1<<30) - 1)
int n;
struct Tree {
	Tree *c1, *c2;
	int L, S, pv;
	Tree(int b, int e) {
		L = 0;
		c1 = c2 = NULL;
		pv = b - 1;
		S = -1 * (e - b + 1);
	}
	Tree GetMax(int b, int e, int s) {
		if (b == s)return *this;
		int m = (b + e) >> 1;
		if (!c1) {
			c1 = new Tree(b, m);
			c2 = new Tree(m + 1, e);
		}
		if (m < s) return c2->GetMax(m + 1, e, s);
		Tree ret = c1->GetMax(b, m, s);
		if (ret.L < ret.S + c2->L) {
			ret.L = ret.S + c2->L;
			ret.pv = c2->pv;
		}
		ret.S = ret.S + c2->S;
		return ret;
	}
	void Add(int b, int e, int x) {
		if (b == e) {
			S++;
			if (S > 0) {
				L = S;
				pv = b;
			}
			return;
		}
		int m = (b + e) >> 1;
		if (c1 == NULL) {
			c1 = new Tree(b, m);
			c2 = new Tree(m + 1, e);
		}
		if (x <= m)c1->Add(b, m, x);
		else c2->Add(m + 1, e, x);
		S = c1->S + c2->S;
		L = max(c1->L, c1->S + c2->L);
		pv = c1->pv;
		if (L != c1->L) pv = c2->pv;
	}
	int Sum(int b, int e, int x) {
		if (b == x)return S;
		int m = (b + e) >> 1, r = 0;
		if (!c1) {
			c1 = new Tree(b, m);
			c2 = new Tree(m+1, e);
		}
		if (x <= m) {
			r = c2->S + c1->Sum(b, m, x);
		}
		else {
			r = c2->Sum(m + 1, e, x);
		}
		return r;
	}
};
int main() {
	int i, a;
	scanf("%d", &n);
	long long res = 0, SS = 0;
	Tree *Root = new Tree(0, INF);
	for (i = 1; i <= n; i++) {
		scanf("%d", &a);
		Tree rr = Root->GetMax(0, INF, a+1);
		res += rr.pv - a;
		res += Root->Sum(0, INF, rr.pv + 1) + (INF - rr.pv);
		Root->Add(0, INF, rr.pv);
		SS += rr.pv - a;
	}
	printf("%lld\n", res);
}

Submission Info

Compile Error

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

Judge Result