Submission #1107915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107915		0x34c	Žarulje (COI15_zarulje)	C++17	100 / 100	173 ms	21064 KiB

zarulje

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'
#define int ll

using namespace std;

const int MAX_A = 2e5 + 1;
const int MOD = 1e9 + 7;

int bin_exp(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = (res * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res;
}

int inv(int x)
{
    return bin_exp(x, MOD - 2);
}

int add(int a, int b)
{
    return ((a % MOD) + (b % MOD)) % MOD;
}

int mul(int a, int b)
{
    return ((a % MOD) * (b % MOD)) % MOD;
}

int sub(int a, int b)
{
    return ((a % MOD) - (b % MOD) + MOD) % MOD;
}

int vydel(int a, int b)
{
    return mul(a, inv(b % MOD));
}

int mapa[MAX_A], lmapa[MAX_A], arr[MAX_A], res[MAX_A], fact[MAX_A], ifact[MAX_A];

void pre_comp()
{
    fact[0] = ifact[0] = 1;
    for (int i = 1; i < MAX_A; i++)
        fact[i] = mul(i, fact[i - 1]);

    ifact[MAX_A - 1] = inv(fact[MAX_A - 1]);
    for (int i = MAX_A - 2; i >= 1; i--)
        ifact[i] = mul(i + 1, ifact[i + 1]);
}

int C(int n, int k)
{
    return mul(mul(fact[n], ifact[n - k]), ifact[k]);
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    pre_comp();

    int N, K;
    cin >> N >> K;
    for (int i = 0; i < N; i++)
        cin >> arr[i];

    vector<vector<int>> ops(N);
    stack<int> stk;
    for (int i = N - 1; i >= 0; i--)
    {
        while (!stk.empty() && stk.top() > arr[i])
        {
            ops[i].push_back(stk.top());
            mapa[stk.top()]--;
            stk.pop();
        }

        stk.push(arr[i]);
        mapa[arr[i]]++;
    }

    while (!stk.empty())
        stk.pop();

    int ans = 1;
    for (int i = 0; i < N; i++)
    {
        ans = vydel(ans, C(mapa[arr[i]], lmapa[arr[i]]));
        mapa[arr[i]]--;
        ans = mul(ans, C(mapa[arr[i]], lmapa[arr[i]]));

        for (int x : ops[i])
        {
            ans = vydel(ans, C(mapa[x], lmapa[x]));
            mapa[x]++;
            ans = mul(ans, C(mapa[x], lmapa[x]));
        }

        res[i] = ans;

        while (!stk.empty() && stk.top() > arr[i])
        {
            ans = vydel(ans, C(mapa[stk.top()], lmapa[stk.top()]));
            lmapa[stk.top()]--;
            mapa[stk.top()]--;
            ans = mul(ans, C(mapa[stk.top()], lmapa[stk.top()]));
            stk.pop();
        }

        stk.push(arr[i]);
        ans = vydel(ans, C(mapa[arr[i]], lmapa[arr[i]]));
        lmapa[arr[i]]++;
        mapa[arr[i]]++;
        ans = mul(ans, C(mapa[arr[i]], lmapa[arr[i]]));
    }

    while (K--)
    {
        int x;
        cin >> x;
        --x;

        cout << res[x] << endl;
    }
    cout << endl;
}

• Subtask 1: 22 / 22
• Subtask 2: 38 / 38
• Subtask 3: 40 / 40