Submission #1696226

---

Source Code Expand

#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890123456789LL
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

typedef long long cat;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

cat mod =1000000007;

struct intervalac {
	struct node {
		int son[2];
		int z, k, sum0;
		cat sum, sum2, add;
	};
	vector<node> T;

	void constI(int akt, vector<int> &D) {
		node n =T[akt];
		if(n.k-n.z == 1) {
			T[akt].sum0 =(D[n.z] == 0);
			return;
		}
		for(int i =0; i < 2; i++) {
			if(i == 0) n.k =(n.z+n.k)/2;
			else {n.z =n.k; n.k =T[akt].k;}
			T[akt].son[i] =T.size();
			T.push_back(n);
			constI(T.size()-1, D);
		}
		T[akt].sum0 =T[T[akt].son[0]].sum0+T[T[akt].son[1]].sum0;
	}

	intervalac(int N, vector<int> &D) {
		node n;
		n.z =n.sum =n.add =n.sum0 =n.sum2 =0;
		n.k =N;
		n.son[0] =n.son[1] =-1;
		T.resize(1,n);
		constI(0,D);
	}

	void upd(int akt) {
		if(T[akt].add == 0) return;
		node n =T[akt];
		T[akt].sum +=n.sum0*n.add;
		T[akt].sum2 +=(n.k-n.z-n.sum0)*n.add;
		for(int i =0; i < 2; i++) if(n.son[i] != -1)
			T[n.son[i]].add +=n.add;
		T[akt].add =0;
	}

	void put(int akt, int zac, int kon, cat val) {
		upd(akt);
		node n =T[akt];
		if(n.k <= zac || kon <= n.z) return;
		if(n.z == zac && n.k == kon) {
			T[akt].add +=val;
			upd(akt);
			return;
		}
		put(n.son[0],zac,min(kon,(n.z+n.k)/2),val);
		put(n.son[1],max(zac,(n.z+n.k)/2),kon,val);
		T[akt].sum =T[n.son[0]].sum+T[n.son[1]].sum;
		T[akt].sum2 =T[n.son[0]].sum2+T[n.son[1]].sum2;
	}

	cat get(int akt, int zac, int kon, int tp) {
		upd(akt);
		node n =T[akt];
		if(n.k <= zac || kon <= n.z) return 0;
		if(n.z == zac && n.k == kon) {
			if(tp == 0) return n.sum;
			return n.sum2;
		}
		return get(n.son[0],zac,min(kon,(n.z+n.k)/2),tp) + get(n.son[1],max(zac,(n.z+n.k)/2),kon,tp);
	}
};

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N;
	cin >> N;
	vector<int> P(N), D(N,0);
	for(int i =0; i < N; i++) {
		cin >> P[i];
		P[i]--;
		if(P[i] >= 0) D[P[i]]++;
	}
	vector<cat> fac(N+1,1);
	for(int i =1; i <= N; i++) fac[i] =(fac[i-1]*i)%mod;
	int n =0;
	for(int i =0; i < N; i++) if(D[i] == 0) n++;
	cat ans =fac[n];

	intervalac I(N,D);
	for(int i =N-1; i >= 0; i--) {
		if(P[i] == -1) ans +=fac[N-1-i]*fac[n-1]%mod*(I.get(0,0,N,0)%mod)%mod;
		else ans +=fac[N-1-i]*fac[n]%mod*(I.get(0,P[i],P[i]+1,1)%mod)%mod;
		if(P[i] >= 0) I.put(0,P[i]+1,N,1);
	}

	vector<int> less(N,0);
	for(int i =0; i < N; i++) if(D[i] == 0) less[i] =1;
	for(int i =1; i < N; i++) less[i] +=less[i-1];
	// fac * ( sum_k k * C(n_lt, k) * C(n_gt, n_r-k) ) * n_r! * n_l! = fac * n_l * n! / 2
	int l =0;
	cat inv2 =(mod+1)/2;
	for(int i =N-1; i >= 0; i--) {
		if(P[i] == -1) ans +=fac[n]*fac[N-1-i]%mod*l%mod*inv2%mod;
		else ans +=less[P[i]]*fac[n-1]%mod*fac[N-1-i]%mod*l%mod;
		if(P[i] == -1) l++;
	}
	ans %=mod;
	if(ans < 0) ans +=mod;
	cout << ans << "\n";
	return 0;}

// look at my code
// my code is amazing

Submission Info

Judge Result