Submission #795733

#	Time	Username	Problem	Language	Result	Execution time	Memory
795733		vjudge1	Cryptography (NOI20_crypto)	C++17	100 / 100	334 ms	26220 KiB

Crypto

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second

const int N = 3e5 + 5;
const int mod = 1e9 + 7;

ll fact[N];
int n, a[N], b[N];
map<int, int> m;

struct segtree {

    int st[4 * N];

    void build(int x, int tl, int tr) {
        if (tl == tr) st[x] = 1;
        else {
            int tm = (tl + tr) / 2;
            build(2 * x, tl, tm);
            build(2 * x + 1, tm + 1, tr);
            st[x] = st[2 * x] + st[2 * x + 1];
        }
    }

    void update(int x, int tl, int tr, int pos) {
        if (tl == tr) st[x] = 0;
        else {
            int tm = (tl + tr) / 2;
            if (pos <= tm) update(2 * x, tl, tm, pos);
            else update(2 * x + 1, tm + 1, tr, pos);
            st[x]--;
        }
    }

    int get(int x, int tl, int tr, int l, int r) {
        if (l <= tl and tr <= r) return st[x];
        if (l > tr or r < tl) return 0;
        int tm = (tl + tr) / 2;
        return get(2 * x, tl, tm, l, r) + get(2 * x + 1, tm + 1, tr, l, r);
    }

} t;

int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll ans = 0;
    cin >> n;
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i], fact[i] = (fact[i - 1] * i) % mod;;
    }
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++) m[b[i]] = i;
    for (int i = 1; i <= n; i++) a[i] = m[a[i]];
    t.build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        ans += 1ll * fact[n - i] * t.get(1, 1, n, 1, a[i] - 1);
        ans %= mod;
        t.update(1, 1, n, a[i]);
    }
    cout << (ans + 1) % mod << "\n"; 
}  

• 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