Submission #1263440

#TimeUsernameProblemLanguageResultExecution timeMemory
1263440sohamsen15Cryptography (NOI20_crypto)C++20
35 / 100
191 ms30972 KiB
#pragma GCC optimize("Ofast,unroll-loops") #include <bits/stdc++.h> using namespace std; using ll = long long; const ll MOD = 1e9 + 7; struct BIT { int n; vector<ll> B1, B2; BIT(int n) : n(n), B1(n + 1, 0), B2(n + 1, 0) {} void update(vector<ll>& B, int i, ll v) { for (; i <= n; i += i & -i) B[i] += v; } void range_update(int l, int r, ll v) { // add v to range [l, r] update(B1, l, v); update(B1, r + 1, -v); update(B2, l, v * (l - 1)); update(B2, r + 1, -v * r); } ll query(const vector<ll>& B, int i) { ll res = 0; for (; i > 0; i -= i & -i) res += B[i]; return res; } ll prefix_sum(int i) { return query(B1, i) * i - query(B2, i); } ll range_sum(int l, int r) { return prefix_sum(r) - prefix_sum(l - 1); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout << fixed << setprecision(0); ll n, curr = 1, ans = 0; cin >> n; vector<ll> a(n); for (auto &x: a) cin >> x; vector<ll> ac(n); for (ll i = 0; i < n; i++) ac[i] = a[i]; sort(ac.begin(), ac.end()); map<ll, ll> m; for (auto x: ac) if (!m.count(x)) m[x] = curr++; for (ll i = 0; i < n; i++) a[i] = m[a[i]]; vector<ll> f(n + 1); f[0] = 1; for (ll i = 1; i <= n; i++) f[i] = (i * f[i - 1]) % MOD; BIT bit(n + 1); for (ll i = 1; i <= n; i++) bit.range_update(i, i, 1); for (ll i = 0; i < n; i++) ans = (ans + bit.range_sum(1, a[i] - 1) * f[n - 1 - i]) % MOD, bit.range_update(a[i], a[i], -1); cout << ans + 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...