Submission #1914644

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

long long N, a[500009], bit[500009], mod = 1000000007; bool used[500009]; vector<long long>A, B;

long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (long long i = 0; i < 63; i++) {
		if ((b&(1LL << i)) != 0) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}
long long Div(long long a, long long b, long long m) {
	a %= m;
	return (a*modpow(b, m - 2, m)) % m;
}
void Add(long long p, long long x) {
	p++;
	while (p <= 500008) { bit[p] += x; p += (p&-p); }
}
long long Sum(long long p) {
	p++; long long s = 0;
	while (p >= 1) { s += bit[p]; p -= (p&-p); }
	return s;
}

int main() {
	cin >> N;
	for (long long i = 1; i <= N; i++) {
		scanf("%lld", &a[i]); if (a[i] >= 1)used[a[i]] = true;
	}
	for (long long i = 1; i <= N; i++) {
		if (used[i] == true)A.push_back(i);
		if (used[i] == false)B.push_back(i);
	}
	long long fact2 = 1;
	for (long long i = 0; i < B.size(); i++) { fact2 *= (i + 1); fact2 %= mod; }
	long long cnt = 0, fact = 1, ret = 0, sum = 0, cnt2 = 0;
	for (long long i = N; i >= 1; i--) {
		if (a[i] == 0) {
			long long V = sum; V = Div(V, B.size(), mod);
			long long W = cnt2; W = Div(W, 2, mod);
			long long X = V + W; X *= fact2; X %= mod;
			ret += X * fact; ret %= mod; cnt2++;
		}
		else {
			long long pos1 = lower_bound(B.begin(), B.end(), a[i]) - B.begin();
			sum += (B.size() - pos1);
			long long V = Sum(a[i]); Add(a[i], 1);
			long long W = pos1; W = Div(W, B.size(), mod); W *= cnt2; W %= mod;
			long long X = V + W; X *= fact2; X %= mod;
			ret += X*fact; ret %= mod;
		}
		cnt++; fact *= cnt; fact %= mod;
	}
	ret += fact2; ret %= mod;
	cout << ret << endl;
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:34:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a[i]); if (a[i] >= 1)used[a[i]] = true;
                       ^

Judge Result