제출 #693713

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
693713		zeroesandones	Cryptography (NOI20_crypto)	C++17	100 / 100	301 ms	26776 KiB

Crypto

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
template<typename T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define FOR(i, j, k) for (ll i = j; i < (ll) k; ++i)
#define FORD(i, j, k) for (ll i = j; i >= (ll) k; --i)
#define nl "\n"
#define sp " "

#define all(x) (x).begin(), (x).end()
#define sc second
#define fr first
#define pb emplace_back

const int mod = 1e9 + 7;

void solve()
{
    ll n;
    cin >> n;

    ll a[n];
    FOR(i, 0, n) {
        cin >> a[i];
    }

    ll fac[n + 1] = {};
    fac[0] = 1;
    FOR(i, 1, n + 1) {
        fac[i] = (fac[i - 1] * i) % mod;
    }

    iset<ll> s;
    ll ans = 0;
    FORD(i, n - 1, 0) {
        ans += (s.order_of_key(a[i]) * fac[n - i - 1]) % mod;
        ans %= mod;
        s.insert(a[i]);
    }
    ++ans;

    cout << ans%mod << nl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
}

• 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