Submission #1095843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095843		windowwife	Žarulje (COI15_zarulje)	C++14	100 / 100	307 ms	37280 KiB

zarulje

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e6 + 2, LG = 20, mod = 1e9 + 7;
ll n, q, f[maxn], invf[maxn], a[maxn], x, t[maxn], res = 1, ans[maxn];
unordered_map<int, int> L, R;
vector<int> stL, stR;
vector<pair<int, int>> changes;
ll power (ll a, ll b)
{
    ll res = 1;
    for (; b > 0; b >>= 1)
    {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
void prep ()
{
    f[0] = 1;
    for (int i = 1; i < maxn; i++) f[i] = f[i - 1] * i % mod;
    invf[maxn - 1] = power(f[maxn - 1], mod - 2);
    for (int i = maxn - 2; i >= 0; i--) invf[i] = invf[i + 1] * (i + 1) % mod;
}
ll C (int k, int n)
{
    return f[n] * invf[k] % mod * invf[n - k]%mod;
}
int main()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    prep();
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = n; i >= 1; i--)
    {
        while (!stR.empty() && stR.back() > a[i])
        {
            changes.push_back({0, stR.back()});
            res = res * power(C(R[stR.back()], L[stR.back()] + R[stR.back()]), mod - 2) % mod;
            R[stR.back()]--;
            res = res * C(R[stR.back()], L[stR.back()] + R[stR.back()]) % mod;
            stR.pop_back();
        }
        stR.push_back(a[i]);
        changes.push_back({1, a[i]});
        res = res * power(C(R[a[i]], L[a[i]] + R[a[i]]), mod - 2) % mod;
        R[a[i]]++;
        res = res * C(R[a[i]], L[a[i]] + R[a[i]]) % mod;
        t[i] = changes.size();
    }
    for (int i = 1; i <= n; i++)
    {
        while ((int)changes.size() > t[i + 1])
        {
            if (changes.back().first == 0)
            {
                stR.push_back(changes.back().second);
                res = res * power(C(R[stR.back()], L[stR.back()] + R[stR.back()]), mod - 2) % mod;
                R[stR.back()]++;
                res = res * C(R[stR.back()], L[stR.back()] + R[stR.back()]) % mod;
            }
            else
            {
                res = res * power(C(R[stR.back()], L[stR.back()] + R[stR.back()]), mod - 2) % mod;
                R[stR.back()]--;
                res = res * C(R[stR.back()], L[stR.back()] + R[stR.back()]) % mod;
                stR.pop_back();
            }
            changes.pop_back();
        }
        if (i > 1)
        {
            while (!stL.empty() && stL.back() > a[i - 1])
            {
                res = res * power(C(L[stL.back()], L[stL.back()] + R[stL.back()]), mod - 2) % mod;
                L[stL.back()]--;
                res = res * C(L[stL.back()], L[stL.back()] + R[stL.back()]) % mod;
                stL.pop_back();
            }
            stL.push_back(a[i - 1]);
            res = res * power(C(L[a[i - 1]], L[a[i - 1]] + R[a[i - 1]]), mod - 2) % mod;
            L[a[i - 1]]++;
            res = res * C(L[a[i - 1]], L[a[i - 1]] + R[a[i - 1]]) % mod;
        }
        ans[i] = res;
    }
    while (q--)
    {
        cin >> x;
        cout << ans[x] << '\n';
    }
}

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