Submission #951643

#	Time	Username	Problem	Language	Result	Execution time	Memory
951643		Irate	Cryptography (NOI20_crypto)	C++17	100 / 100	74 ms	11544 KiB

Crypto

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int mxN = 3e5 + 5;
int fact[mxN];
struct FenwickTree{
    vector<int>fen;
    int sz;
    FenwickTree(int n){
        sz = n;
        fen.resize(n + 1);
    }
    void Update(int pos){
        while(pos <= sz){
            fen[pos]++;
            pos += (pos & -pos);
        }
    }
    int Sum(int pos){
        int sum = 0;
        while(pos > 0){
            sum += fen[pos];
            pos -= (pos & -pos);
        }
        return sum;
    }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    fact[0] = 1;
    for(int i = 1;i < mxN;++i){
        fact[i] = (long long)fact[i - 1] * i % MOD;
    }
    int n;
    cin >> n;
    vector<int>v(n);
    vector<pair<int, int>>compress;
    for(int i = 0;i < n;++i){
        cin >> v[i];
        compress.push_back({v[i], i});
    }
    sort(compress.begin(), compress.end());
    int num = 1;
    v[compress[0].second] = num;
    FenwickTree tree(n);
    for(int i = 1;i < n;++i){
        if(compress[i].first != compress[i - 1].first)num++;
        v[compress[i].second] = num;
    }    
    int res = 1;
    for(int i = 1;i <= n;++i){
        int k = v[i - 1] - tree.Sum(v[i - 1]);
        res += (long long)fact[n - i] * (k - 1) % MOD;
        tree.Update(v[i - 1]);
        res %= MOD;
    }
    cout << res << '\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