Submission #2822650

---

Source Code Expand

#include <algorithm>
#include <utility>
#include <cstdio>
int arr[200005], app[200005], lazy[800005]; 
std::pair<int, int> seg[800005];
inline void paint(int u, int x)
{
	seg[u].first += x; 
	lazy[u] += x; 
}
inline void push_down(int u)
{
	if (lazy[u])
	{
		paint(u << 1, lazy[u]);
		paint(u << 1 | 1, lazy[u]); 
		lazy[u] = 0; 
	}
}
void build(int u, int l, int r)
{
	if (l == r)
	{
		seg[u] = {app[l], l}; 
		return; 
	}
	int m = l + r >> 1; 
	build(u << 1, l, m); 
	build(u << 1 | 1, m + 1, r); 
	seg[u] = std::min(seg[u << 1], seg[u << 1 | 1]); 
}
void modify(int u, int l, int r, int L, int R)
{
	if (L > R)
		return; 
	if (L <= l && r <= R)
	{
		paint(u, 1);
		return; 
	}
	push_down(u); 
	int m = l + r >> 1; 
	if (L <= m)
		modify(u << 1, l, m, L, R); 
	if (m < R)
		modify(u << 1 | 1, m + 1, r, L, R); 
	seg[u] = std::min(seg[u << 1], seg[u << 1 | 1]); 
}
std::pair<int, int> query(int u, int l, int r, int L, int R)
{
	if (L <= l && r <= R)
		return seg[u];
	push_down(u); 
	int m = l + r >> 1;
	if (R <= m)
		return query(u << 1, l, m, L, R); 
	if (m < L)
		return query(u << 1 | 1, m + 1, r, L, R); 
	return std::min(query(u << 1, l, m, L, R), query(u << 1 | 1, m + 1, r, L, R)); 
}
int main()
{
	// freopen("CF17-EX-B.in", "r", stdin); 
	int n;
	scanf("%d", &n); 
	for (int i = 0; i < n; i++)
	{
		scanf("%d", arr + i);
		app[i] = arr[i]; 
	}
	std::sort(app, app + n); 
	build(1, 0, n - 1); 
	long long ans = 0; 
	for (int i = 0; i < n; i++)
	{
		int pos = std::lower_bound(app, app + n, arr[i]) - app; 
		auto res = query(1, 0, n - 1, pos, n - 1); 
		ans += res.first - arr[i]; 
		modify(1, 0, n - 1, 0, res.second - 1); 
	}
	printf("%lld\n", ans);
	return 0; 
}

Submission Info

Compile Error

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

Judge Result