oj.uz

Submission #1095842

# Submission time Handle Problem Language Result Execution time Memory
1095842 2024-10-03T10:06:29 Z windowwife Žarulje (COI15_zarulje) C++14
22 / 100
 1000 ms 36980 KB 
#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];
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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15960 KB Output is correct
2 Correct 16 ms 15964 KB Output is correct
3 Correct 17 ms 16220 KB Output is correct
4 Correct 20 ms 16216 KB Output is correct
5 Correct 20 ms 16216 KB Output is correct
6 Correct 21 ms 16220 KB Output is correct

Subtask #2
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 20416 KB Output is correct
2 Correct 223 ms 24432 KB Output is correct
3 Correct 291 ms 24548 KB Output is correct
4 Correct 616 ms 24764 KB Output is correct
5 Correct 783 ms 25704 KB Output is correct
6 Correct 952 ms 33160 KB Output is correct
7 Execution timed out 1029 ms 36980 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15960 KB Output is correct
2 Correct 16 ms 15964 KB Output is correct
3 Correct 17 ms 16220 KB Output is correct
4 Correct 20 ms 16216 KB Output is correct
5 Correct 20 ms 16216 KB Output is correct
6 Correct 21 ms 16220 KB Output is correct
7 Correct 312 ms 20416 KB Output is correct
8 Correct 223 ms 24432 KB Output is correct
9 Correct 291 ms 24548 KB Output is correct
10 Correct 616 ms 24764 KB Output is correct
11 Correct 783 ms 25704 KB Output is correct
12 Correct 952 ms 33160 KB Output is correct
13 Execution timed out 1029 ms 36980 KB Time limit exceeded
14 Halted 0 ms 0 KB -