oj.uz

Submission #1107915

# Submission time Handle Problem Language Result Execution time Memory
1107915 2024-11-02T10:18:57 Z 0x34c Žarulje (COI15_zarulje) C++17
100 / 100
 173 ms 21064 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8784 KB Output is correct
2 Correct 6 ms 8784 KB Output is correct
3 Correct 7 ms 8784 KB Output is correct
4 Correct 7 ms 8784 KB Output is correct
5 Correct 8 ms 8784 KB Output is correct
6 Correct 7 ms 8784 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 12880 KB Output is correct
2 Correct 143 ms 17384 KB Output is correct
3 Correct 145 ms 17744 KB Output is correct
4 Correct 156 ms 17932 KB Output is correct
5 Correct 142 ms 18000 KB Output is correct
6 Correct 147 ms 18504 KB Output is correct
7 Correct 145 ms 19536 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8784 KB Output is correct
2 Correct 6 ms 8784 KB Output is correct
3 Correct 7 ms 8784 KB Output is correct
4 Correct 7 ms 8784 KB Output is correct
5 Correct 8 ms 8784 KB Output is correct
6 Correct 7 ms 8784 KB Output is correct
7 Correct 76 ms 12880 KB Output is correct
8 Correct 143 ms 17384 KB Output is correct
9 Correct 145 ms 17744 KB Output is correct
10 Correct 156 ms 17932 KB Output is correct
11 Correct 142 ms 18000 KB Output is correct
12 Correct 147 ms 18504 KB Output is correct
13 Correct 145 ms 19536 KB Output is correct
14 Correct 13 ms 9428 KB Output is correct
15 Correct 83 ms 14932 KB Output is correct
16 Correct 152 ms 20552 KB Output is correct
17 Correct 156 ms 19272 KB Output is correct
18 Correct 161 ms 21064 KB Output is correct
19 Correct 157 ms 19284 KB Output is correct
20 Correct 173 ms 20300 KB Output is correct
21 Correct 173 ms 21064 KB Output is correct