Submission #1131289

---

Source Code Expand

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <ctime>
#include <cassert>
#include <unordered_map>
#include <fstream>
#include <random>
#include <cstring>
#include <complex>
#include <bitset>

#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define pb push_back

using namespace std;

const int P = 1e9 + 7;

typedef long long ll;
typedef long double ld;
mt19937 rr(random_device{}());

vector<int> f;
int n;

void update(int pos, int val) {
	for (int i = pos; i < n; i = i | (i + 1))
		f[i] += val;
}

int sum(int pos) {
	int ans = 0;
	for (int i = pos; i >= 0; i = (i & (i + 1)) - 1)
		ans += f[i];
	return ans;
}

int main() {
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	vector<int> x(n);
	for (int i = 0; i < n; ++i) 
		cin >> x[i];
	
	int m = 0;
	vector<int> p;
	vector<int> used(n);
	for (int i = 0; i < n; ++i) {
		++m;
		if (m > (x[i] + 1) / 2) {
			--m;
			used[i] = 1;
			p.push_back(i);
		}
	}

	for (int i = n - 1; i >= 0; --i) {
		if (!used[i])
			p.push_back(i);
	}

	f.resize(n);
	for (int i = 0; i < n; ++i)
		update(i, 1);

	vector<ll> fact(n);
	fact[0] = 1;
	for (ll i = 1; i < n; ++i) {
		fact[i] = fact[i - 1] * i % P;
	}

	ll ans = 1;
	for (int i = 0; i < n; ++i) {
		ll x = sum(p[i]);
		ans += fact[n - i - 1] * (x - 1);
		ans %= P;
		update(p[i], -1);
	}

	cout << ans << endl;
}

Submission Info

Judge Result