Submission #826493

#	Time	Username	Problem	Language	Result	Execution time	Memory
826493		nasir_bashirov	Cryptography (NOI20_crypto)	C++11	100 / 100	387 ms	31404 KiB

Crypto

#include "bits/stdc++.h"
using namespace std;

#define int long long

#define endl '\n'
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define all(x)    x.begin(), x.end()
#define fastio\
    ios_base::sync_with_stdio(0);\
    cin.tie(0);\
    cout.tie(0)\

const int sz = 3e5 + 5;
ll a[sz], b[sz], f[sz], n, ind;
const int mod = 1e9 + 7;
map<int, int> mp;

struct fenwickTree{
    int n;
    vi BIT;
    fenwickTree(int sz){
        n = sz;
        BIT.resize(n + 1, 0);
    }
    void update(int i, int v){
        if(i == 0)    return;
        while(i <= n){
            BIT[i] += v;
            i += i & (-i);
        }
    }
    int query(int l, int r){
        if(l > r)   return 0;   
        if(l != 1)    return query(1, r) - query(1, l - 1);
        int res = 0;
        while(r > 0){
            res += BIT[r];
            r -= r & (-r);
        }
        return res;
    }
};

void preComp(){
    f[0] = 1;
    for(ll i = 1; i <= 300000; i++){
        f[i] = f[i - 1] * i % mod;
    }
}

signed main(){
    fastio;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    for(int i = 1; i <= n; i++){
        mp[b[i]] = ++ind;
    }
    for(int i = 1; i <= n; i++){
        a[i] = mp[a[i]];
    }
    ll res = 0;
    fenwickTree t(n);
    for(int i = 1; i <= n; i++){
        t.update(i, 1);
    }
    preComp();
    for(int i = 1; i <= n; i++){
        res += f[n - i] * (t.query(1, a[i] - 1)) % mod;
        res %= mod;
        t.update(a[i], -1);
    }
    cout << (res + 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