Submission #1164246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164246		ChottuF	Cryptography (NOI20_crypto)	C++20	100 / 100	174 ms	31704 KiB

Crypto

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

#define int long long

vector<int> tree;
int cfr = 0;

int sum(int a, int b){
    a += cfr;
    b += cfr;
    int s = 0;
    while (a <= b){
        if (a%2 == 1){
            s += tree[a++];
        }
        if (b%2 == 0){
            s += tree[b--];
        }
        a /= 2;
        b /= 2;
    }
    return s;
}

void update(int k, int x){
    k += cfr;
    tree[k] = x;
    k /= 2;
    while (k >= 1){
        tree[k] = tree[2*k] + tree[2*k+1];
        k /= 2;
    }
}

const int MOD = 1e9+7;
const int MAXN = 1e6;

signed main() {
    int fac[MAXN];
    fac[0] = 1;
    for (int i = 1; i<MAXN; i++){
        fac[i] = fac[i-1]*i;
        fac[i] %= MOD;
    }
    int n;
    cin >> n;
    pair<int,int> arr[n];
    for (int i = 0; i<n; i++){
        int a;
        cin >> a;
        arr[i] = {a,i};
    }
    sort(arr,arr+n);
    vector<int> nw(n);
    for (int i = 0; i<n; i++){
        nw[arr[i].second] = cfr++;
    }
	cfr++;
    while (__builtin_popcount(cfr) != 1){
        cfr++;
    }
	cfr *= 2;
    tree.resize(2*cfr);
    for (int i = 0; i<cfr; i++){
        update(i,1); //set update
    }
    __int128 ans = 0;
    for (int i = 0; i<n; i++){
        int bef = sum(0,nw[i]-1);
        int ln = n-i-1;
        ans += bef*fac[ln];
        ans %= MOD; ans += MOD; ans %= MOD;
        update(nw[i],0);
    }
	int one = ans+1LL;
	one %= MOD;
    cout << one << '\n';
    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