oj.uz

Submission #1095845

# Submission time Handle Problem Language Result Execution time Memory
1095845 2024-10-03T10:16:23 Z vjudge1 Žarulje (COI15_zarulje) C++17
100 / 100
 329 ms 24740 KB 
#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e6 + 2, LG = 20, mod = 1e9 + 7;
int 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;
int power (int a, int b)
{
    int res = 1;
    for (; b > 0; b >>= 1)
    {
        if (b & 1) res = 1LL * res * a % mod;
        a = 1LL * a * a % mod;
    }
    return res;
}
void prep ()
{
    f[0] = 1;
    for (int i = 1; i < maxn; i++) f[i] = 1LL * f[i - 1] * i % mod;
    invf[maxn - 1] = power(f[maxn - 1], mod - 2);
    for (int i = maxn - 2; i >= 0; i--) invf[i] = 1LL * invf[i + 1] * (i + 1) % mod;
}
int C (int k, int n)
{
    return 1LL * 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 = 1LL * res * power(C(R[stR.back()], L[stR.back()] + R[stR.back()]), mod - 2) % mod;
            R[stR.back()]--;
            res = 1LL * 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 = 1LL * res * power(C(R[a[i]], L[a[i]] + R[a[i]]), mod - 2) % mod;
        R[a[i]]++;
        res = 1LL * 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 = 1LL * res * power(C(R[stR.back()], L[stR.back()] + R[stR.back()]), mod - 2) % mod;
                R[stR.back()]++;
                res = 1LL * res * C(R[stR.back()], L[stR.back()] + R[stR.back()]) % mod;
            }
            else
            {
                res = 1LL * res * power(C(R[stR.back()], L[stR.back()] + R[stR.back()]), mod - 2) % mod;
                R[stR.back()]--;
                res = 1LL * 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 = 1LL * res * power(C(L[stL.back()], L[stL.back()] + R[stL.back()]), mod - 2) % mod;
                L[stL.back()]--;
                res = 1LL * res * C(L[stL.back()], L[stL.back()] + R[stL.back()]) % mod;
                stL.pop_back();
            }
            stL.push_back(a[i - 1]);
            res = 1LL * res * power(C(L[a[i - 1]], L[a[i - 1]] + R[a[i - 1]]), mod - 2) % mod;
            L[a[i - 1]]++;
            res = 1LL * 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 8284 KB Output is correct
2 Correct 15 ms 8424 KB Output is correct
3 Correct 17 ms 8284 KB Output is correct
4 Correct 16 ms 8176 KB Output is correct
5 Correct 17 ms 8284 KB Output is correct
6 Correct 17 ms 8288 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 11196 KB Output is correct
2 Correct 252 ms 13964 KB Output is correct
3 Correct 280 ms 13768 KB Output is correct
4 Correct 265 ms 13960 KB Output is correct
5 Correct 278 ms 14572 KB Output is correct
6 Correct 309 ms 21912 KB Output is correct
7 Correct 329 ms 24332 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8284 KB Output is correct
2 Correct 15 ms 8424 KB Output is correct
3 Correct 17 ms 8284 KB Output is correct
4 Correct 16 ms 8176 KB Output is correct
5 Correct 17 ms 8284 KB Output is correct
6 Correct 17 ms 8288 KB Output is correct
7 Correct 142 ms 11196 KB Output is correct
8 Correct 252 ms 13964 KB Output is correct
9 Correct 280 ms 13768 KB Output is correct
10 Correct 265 ms 13960 KB Output is correct
11 Correct 278 ms 14572 KB Output is correct
12 Correct 309 ms 21912 KB Output is correct
13 Correct 329 ms 24332 KB Output is correct
14 Correct 27 ms 8672 KB Output is correct
15 Correct 152 ms 12224 KB Output is correct
16 Correct 268 ms 15816 KB Output is correct
17 Correct 281 ms 14760 KB Output is correct
18 Correct 277 ms 15812 KB Output is correct
19 Correct 282 ms 15032 KB Output is correct
20 Correct 312 ms 22184 KB Output is correct
21 Correct 327 ms 24740 KB Output is correct