Submission #698540

#	Time	Username	Problem	Language	Result	Execution time	Memory
698540		bin9638	Cryptography (NOI20_crypto)	C++17	100 / 100	137 ms	12764 KiB

Crypto

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define N 300010
#define fs first
#define sc second
#define ii pair<int,int>
#define iii pair<ii,int>
#define ld long double
#define pb push_back
#define int ll

const ll mod=1e9+7;

void selfadd(int&u,int v)
{
    u=(u+v)%mod;
}

int gt[N],ans=1,n,a[N],b[N],bit[N];

void update(int u,int val)
{
    for(;u<=n;u+=u&(-u))
        bit[u]+=val;
}

int get(int u)
{
    int res=0;
    for(;u>0;u-=u&(-u))
        res+=bit[u];
    return res;
}

int32_t main()
{
   // freopen("crypto.inp","r",stdin);
   // freopen("crypto.out","w",stdout);
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(0);
    cin>>n;
    gt[0]=1;
    for(int i=1;i<=n;i++)
        gt[i]=gt[i-1]*i%mod;
   // cout<<gt[n]<<endl;
    for(int i=1;i<=n;i++)
        cin>>a[i],b[i]=a[i];
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(b+1,b+1+n,a[i])-b;
      //  cout<<a[i]<<endl;
    }
    for(int i=1;i<=n;i++)
        update(i,1);
    for(int i=1;i<=n;i++)
    {
        selfadd(ans,get(a[i]-1)*gt[n-i]);
        update(a[i],-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