oj.uz

Submission #1107906

# Submission time Handle Problem Language Result Execution time Memory
1107906 2024-11-02T10:05:20 Z 0x34c Žarulje (COI15_zarulje) C++17
0 / 100
 20 ms 13392 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 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 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 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)
{
    if (k == 0 || k == n)
        return 0;
    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 = 0;
    for (int i = 0; i < N; i++)
    {
        ans = sub(ans, C(mapa[arr[i]], lmapa[arr[i]]));
        mapa[arr[i]]--;
        ans = add(ans, C(mapa[arr[i]], lmapa[arr[i]]));

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

        res[i] = (ans == 0 ? 1 : ans);

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

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

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

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

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 8784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 13392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 8784 KB Output isn't correct
2 Halted 0 ms 0 KB -