제출 #1307082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307082		dang_hai_long	Cryptography (NOI20_crypto)	C++20	100 / 100	95 ms	9928 KiB

Crypto

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MOD = 1000000007;

const int MAXN = 300010;

ll fact[MAXN];

struct Fenwick {
    vector<int> tree;
    int n;
    Fenwick(int _n) : n(_n), tree(_n + 1, 0) {}
    void upd(int idx, int val) {
        while (idx <= n) {
            tree[idx] += val;
            idx += idx & -idx;
        }
    }
    int qry(int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= idx & -idx;
        }
        return sum;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    int n;
    cin >> n;
    vector<ll> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    vector<ll> vals = p;
    sort(vals.begin(), vals.end());
    vector<int> rank(n);
    for (int i = 0; i < n; i++) {
        rank[i] = lower_bound(vals.begin(), vals.end(), p[i]) - vals.begin() + 1;
    }
    Fenwick ft(n);
    for (int i = 0; i < n; i++) {
        ft.upd(rank[i], 1);
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        int rnk = rank[i];
        int cnt = ft.qry(rnk - 1);
        ans = (ans + (ll)cnt * fact[n - 1 - i] % MOD) % MOD;
        ft.upd(rnk, -1);
    }
    ans = (ans + 1) % MOD;
    cout << ans << endl;
    return 0;
}

• 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