Submission #1263442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263442		sohamsen15	Cryptography (NOI20_crypto)	C++20	100 / 100	292 ms	30976 KiB

Crypto

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

struct BIT {
    ll n; vector<ll> B1, B2;

    BIT(ll n) : n(n), B1(n + 1, 0), B2(n + 1, 0) {}

    void update(vector<ll>& B, ll i, ll v) {
        for (; i <= n; i += i & -i) B[i] += v;
    }

    void range_update(ll l, ll 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, ll i) {
        ll res = 0;
        for (; i > 0; i -= i & -i) res += B[i];
        return res;
    }

    ll prefix_sum(ll i) {
        return query(B1, i) * i - query(B2, i);
    }

    ll range_sum(ll l, ll 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)) % MOD, 
        bit.range_update(a[i], a[i], -1);
    cout << (ans + 1) % MOD;
}

• Subtask 1: 5 / 5
• Subtask 2: 9 / 9
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 21 / 21
• Subtask 6: 13 / 13
• Subtask 7: 19 / 19
• Subtask 8: 12 / 12