Submission #504849

#	Time	Username	Problem	Language	Result	Execution time	Memory
504849		ToroTN	Cryptography (NOI20_crypto)	C++14	100 / 100	471 ms	33280 KiB

Crypto

#include<bits/stdc++.h>
using namespace std;
long long n,a[300005],b[300005],fac[300005],fen[300005],c[300005],ans=0;
vector<long long> v;
map<long long,long long> mp;
void update(long long u,long long val)
{
    while(u<=n)
    {
        fen[u]+=val;
        fen[u]%=1000000007;
        u+=(u&(-u));
    }
}
long long query(long long u)
{
    long long val=0;
    while(u>=1)
    {
        val+=fen[u];
        val%=1000000007;
        u-=(u&(-u));
    }
    return val;
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        v.push_back(a[i]);
    }
    v.push_back(-1);
    sort(v.begin(),v.end());
    for(int i=1;i<=n;i++)
    {
        mp[v[i]]=i;
    }
    for(int i=1;i<=n;i++)
    {
        b[i]=mp[a[i]];
    }
    /*for(int i=1;i<=n;i++)
    {
        printf("%lld ",b[i]);
    }
    printf("\n");*/
    fac[0]=1;
    for(int i=1;i<=300000;i++)
    {
        fac[i]=fac[i-1]*i;
        fac[i]%=1000000007;
    }
    for(int i=n;i>=1;i--)
    {
        update(b[i],1);
        c[i]=query(b[i]);
    }
    /*for(int i=1;i<=n;i++)
    {
        printf("%lld ",c[i]);
    }
    printf("\n");*/
    for(int i=1;i<=n;i++)
    {
        ans+=(c[i]-1)*fac[n-i];
        ans%=1000000007;
    }
    printf("%lld\n",(ans+1)%1000000007);
}

Compilation message (stderr)

Crypto.cpp: In function 'int main()':
Crypto.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
Crypto.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%lld",&a[i]);
      |         ~~~~~^~~~~~~~~~~~~~

• 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