Submission #734089

#	Time	Username	Problem	Language	Result	Execution time	Memory
734089		vjudge1	Cryptography (NOI20_crypto)	C++17	14 / 100	1084 ms	110964 KiB

Crypto

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
#define oset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>

template<typename... T>
void see(T&... args) {((cin >> args), ...);}
template<typename... T>
void put(T&&... args) {((cout << args << ' '), ...);}
template<typename... T>
void putl(T&&... args) {((cout << args << ' '), ...); cout << '\n';}

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define F first
#define S second
#define ii pair<int, int>

#define vt vector
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define sz size()

#define endl '\n'

#define rep(i,a,b) for(int i=a; i<=b; i++)
#define rev(i,b,a) for(int i=b; i>=a; i--)

#define reada(a,x,y) for(int i=x; i<=y; i++){cin >> a[i];}

const int M = 1e9+7;
const int Mxn = 1e6, Nxn = 2*1e5, Mxm = 3e5+5, Nxm = 1005, Dxn = 1e9+1;

int a[Mxm];
vt<int> t[4*Mxm];

void build(int id, int L, int R) {
    if(L == R) {
        t[id].pb(a[L]);
        return;
    }

    int mid = (L+R)/2;
    build(2*id, L, mid);
    build(2*id+1, mid+1, R);

    int n = t[2*id].sz, m = t[2*id+1].sz, i = 0, j = 0;

    while(i < n && j < m) {
        if(t[2*id][i] < t[2*id+1][j]) {
            t[id].pb(t[2*id][i]);
            i++;
        }
        else {
            t[id].pb(t[2*id+1][j]);
            j++;
        }
    }
    while(i < n) {
        t[id].pb(t[2*id][i]);
        i++;
    }
    while(j < m) {
        t[id].pb(t[2*id+1][j]);
        j++;
    }
}

int query(int id, int L, int R, int l, int r, int x) {
    if(L > r || R < l) return 0;
    if(l <= L && R <= r) {
        int n = t[id].sz;
        int k = upper_bound(all(t[id]), x) - t[id].begin();
        return k;
    }

    int mid = (L+R)/2;
    return query(2*id, L, mid, l, min(r, mid), x) + query(2*id+1, mid+1, R, max(l, mid+1), r, x);
}

int fact(int n) {
    if(n == 1) return 1;
    return (n * fact(n-1)) % M;
}

void solve() {
    int n; see(n);
    rep(i,1,n) see(a[i]);

    build(1, 1, n);

    int s = 0;
    rep(i,1,n-1) {
        s += ((query(1, 1, n, i+1, n, a[i]) * fact(n-i))) % M;
    }
    cout << s + 1;
    return;
}

signed main() { IOS
    int t=1;
    //cin >> t;
    while(t--) {
        solve();
        cout << endl;
    }
    return 0;
}

Compilation message (stderr)

Crypto.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int, long long int)':
Crypto.cpp:76:13: warning: unused variable 'n' [-Wunused-variable]
   76 |         int n = t[id].sz;
      |             ^

• Subtask 1: 5 / 5
• Subtask 2: 9 / 9
• Subtask 3: 0 / 10
• Subtask 4: 0 / 11
• Subtask 5: 0 / 21
• Subtask 6: 0 / 13
• Subtask 7: 0 / 19
• Subtask 8: 0 / 12