Submission #330825

#	Time	Username	Problem	Language	Result	Execution time	Memory
330825		ThaiBaHung	Cryptography (NOI20_crypto)	C++14	100 / 100	572 ms	34676 KiB

Crypto

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 3;
const int mod = 1e9 + 7;
int n;
int a[N];
vector < int > num;
map < int, int > id;
long long gt[N];

struct ok
{
    int lo;
    int hi;
    int val;
};
ok Node[4 * N];

void build(int id, int l, int r)
{
    Node[id].lo = l; Node[id].hi = r;
    Node[id].val = 1;

    if (l == r) return;

    int mid = (l + r) / 2;

    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);

    Node[id].val = Node[id * 2].val + Node[id * 2 + 1].val;
}

void update(int id, int pos)
{
    if (Node[id].lo > pos || Node[id].hi < pos) return;

    if (Node[id].lo == Node[id].hi)
    {
        Node[id].val = 0;
        return;
    }

    update(id * 2, pos);
    update(id * 2 + 1, pos);

    Node[id].val = Node[id * 2].val + Node[id * 2 + 1].val;
}

int getval(int id, int pos)
{
    if (Node[id].lo >= pos) return 0;

    if (Node[id].hi < pos)
        return Node[id].val;

    return getval(id * 2, pos) + getval(id * 2 + 1, pos);
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("t.inp","r",stdin); freopen("t.out","w",stdout);

    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i], num.push_back(a[i]);

    sort(num.begin(), num.end());

    for (int i = 0; i < num.size(); i++)
        id[num[i]] = i + 1;

    for (int i = 1; i <= n; i++)
        a[i] = id[a[i]];

    gt[0] = 1;
    for (int i = 1; i <= n; i++)
        gt[i] = gt[i - 1] * 1ll * i, gt[i] %= mod;


    long long res = 0;

    build(1, 1, n);

    for (int i = 1; i <= n; i++)
    {
        int tmp = getval(1, a[i]);

        res += 1ll * tmp * gt[n - i] % mod;
        res %= mod;

        update(1, a[i]);
    }

    cout << (res + 1) % mod;
}

Compilation message (stderr)

Crypto.cpp: In function 'int main()':
Crypto.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (int i = 0; i < num.size(); 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