This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
const int maxn = 3e5 + 5;
const int mod = 1e9 + 7;
int n, a[maxn];
int bit[maxn];
int fact[maxn];
int add(int x, int y) {
if(y < 0) y += mod;
x = x + y;
if(x >= mod) x -= mod;
return x;
}
void update(int i, int val) {
for(; i <= n; i += i & (-i)) {
bit[i] += val;
}
}
int get(int i) {
int ans = 0;
for(; i > 0; i -= i & (-i)) {
ans += bit[i];
}
return ans;
}
void solve() {
cin >> n;
vector<int> vec;
fact[0] = 1;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
fact[i] = 1ll * fact[i - 1] * i % mod;
vec.push_back(a[i]);
}
sort(vec.begin(), vec.end());
for(int i = 1; i <= n; ++i) {
a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
update(a[i], 1);
}
int ans = 1;
for(int i = 1; i <= n; ++i) {
ans = add(ans, 1ll * get(a[i] - 1) * fact[n - i] % mod);
update(a[i], -1);
}
cout << ans;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |