Submission #563043

#	Time	Username	Problem	Language	Result	Execution time	Memory
563043		ddy888	Cryptography (NOI20_crypto)	C++17	100 / 100	155 ms	10532 KiB

Crypto

#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
#define pb push_back
#define fi first
#define si second
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef tuple<int,int,int> ti;  
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 300010;
const ll MOD = 1e9 + 7;
int n;
int a[MAXN];
vi vals;
ll fac[MAXN];
ll ans;

ll mult(int x, int y) {
    return (x % MOD * y % MOD) % MOD;
}

ll add(int x, int y) {
    return (x % MOD + y % MOD) % MOD;
}

struct FwTree {
    int sz;
    vector<int> fw, fw2;
    void init(int _n) {sz = _n;fw.resize(_n + 10);fw2.resize(_n + 10);}
    void update(int x, int y, int v) { //inclusive
        for (int tx=x; tx <= sz; tx += tx&(-tx)) fw[tx] += v, fw2[tx] -= v*(x-1);
        for (int ty=y+1; ty <= sz; ty += ty&(-ty)) fw[ty] -= v, fw2[ty] += v*y; 
    }
    int sum(int x) {
        int res = 0;
        for (int tx=x; tx; tx -= tx&(-tx)) res += fw[tx]*x + fw2[tx];
        return res;
    }
    int query(int x, int y) {
        return sum(y) - sum(x - 1);
    }
} fw;

int main() {
    fast;   
    cin >> n;
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        vals.pb(a[i]);
        fac[i] = mult(fac[i - 1], i);
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    for (int i = 1; i <= n; ++i) {
        a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() + 1;
    }
    fw.init(n);
    for (int i = 1; i <= n; ++i) {
        fw.update(a[i], a[i], 1);
        int pos = a[i] - fw.query(1, a[i]);
        ll contribute = mult(pos, fac[n - i]);
        ans = add(ans, contribute);
    }
    ans = add(ans, 1);
    cout << ans;
    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