oj.uz

Submission #1016818

# Submission time Handle Problem Language Result Execution time Memory
1016818 2024-07-08T12:47:26 Z TAhmed33 Žarulje (COI15_zarulje) C++
100 / 100
 780 ms 91220 KB 
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int M = 1e6 + 25;
int add (int a, int b) {
    a += b; if (a >= MOD) a -= MOD;
    return a;
}
int sub (int a, int b) {
    a -= b; if (a < 0) a += MOD;
    return a;
}
int mul (int a, int b) {
    return (a * 1ll * b) % MOD;
}
int power (int a, int b) {
    if (!b) return 1;
    int u = power(a, b >> 1);
    u = mul(u, u);
    if (b & 1) u = mul(u, a);
    return u;
}
int modinv (int x) {
    return power(x, MOD - 2);
}
int fact[M], inv[M];
int nCr (int a, int b) {
    if (a < b) return 0;
    return mul(fact[a], mul(inv[b], inv[a - b]));
}
void pre () {
    fact[0] = 1;
    for (int i = 1; i < M; i++) {
        fact[i] = mul(i, fact[i - 1]);
    }
    inv[M - 1] = power(fact[M - 1], MOD - 2);
    for (int i = M - 2; i >= 0; i--) {
        inv[i] = mul(i + 1, inv[i + 1]);
    }
}
int n, k, a[M];
int qq[M];
int ans2[M];
map <int, int> changes[M];
void solve () {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= k; i++) {
        cin >> qq[i];
    }
    stack <int> cur;
    map <int, int> dd;
    for (int i = 1; i <= n; i++) {
        while (!cur.empty() && a[cur.top()] > a[i]) {
            changes[i][a[cur.top()]]++;
            dd[a[cur.top()]]--;
            cur.pop();
        }
        changes[i][a[i]]--;
        dd[a[i]]++;
        cur.push(i);
    }
    while (!cur.empty()) {
        cur.pop();
    }
    int L = 1;
    map <int, int> ff;
    for (auto j : changes[n]) {
        dd[j.first] += j.second;
    }
    ans2[n] = 1;
    for (int i = n - 1; i >= 1; i--) {
        for (auto j : changes[i]) {
            L = mul(L, modinv(nCr(ff[j.first] + dd[j.first], dd[j.first])));
            dd[j.first] += j.second;
            L = mul(L, nCr(ff[j.first] + dd[j.first], dd[j.first]));
        }
        while (!cur.empty() && a[cur.top()] > a[i + 1]) {
            int x = a[cur.top()];
          cur.pop();
            L = mul(L, modinv(nCr(ff[x] + dd[x], dd[x])));
            ff[x]--;
            L = mul(L, nCr(ff[x] + dd[x], dd[x]));
        }
        L = mul(L, modinv(nCr(ff[a[i + 1]] + dd[a[i + 1]], ff[a[i + 1]])));
        ff[a[i + 1]]++;
        cur.push(i + 1);
        L = mul(L, nCr(ff[a[i + 1]] + dd[a[i + 1]], ff[a[i + 1]]));
        ans2[i] = L;
    }
    for (int i = 1; i <= k; i++) {
        cout << ans2[qq[i]] << '\n';
    }
}
signed main () {
    pre();
    ios::sync_with_stdio(0); cin.tie(0);
    int tc = 1; //cin >> tc;
    while (tc--) solve();
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 55644 KB Output is correct
2 Correct 21 ms 55644 KB Output is correct
3 Correct 22 ms 55764 KB Output is correct
4 Correct 22 ms 55740 KB Output is correct
5 Correct 27 ms 55892 KB Output is correct
6 Correct 24 ms 55896 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 65364 KB Output is correct
2 Correct 209 ms 72912 KB Output is correct
3 Correct 251 ms 75088 KB Output is correct
4 Correct 444 ms 75604 KB Output is correct
5 Correct 574 ms 76372 KB Output is correct
6 Correct 734 ms 83716 KB Output is correct
7 Correct 780 ms 87360 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 55644 KB Output is correct
2 Correct 21 ms 55644 KB Output is correct
3 Correct 22 ms 55764 KB Output is correct
4 Correct 22 ms 55740 KB Output is correct
5 Correct 27 ms 55892 KB Output is correct
6 Correct 24 ms 55896 KB Output is correct
7 Correct 243 ms 65364 KB Output is correct
8 Correct 209 ms 72912 KB Output is correct
9 Correct 251 ms 75088 KB Output is correct
10 Correct 444 ms 75604 KB Output is correct
11 Correct 574 ms 76372 KB Output is correct
12 Correct 734 ms 83716 KB Output is correct
13 Correct 780 ms 87360 KB Output is correct
14 Correct 34 ms 56660 KB Output is correct
15 Correct 247 ms 66932 KB Output is correct
16 Correct 240 ms 77140 KB Output is correct
17 Correct 264 ms 77536 KB Output is correct
18 Correct 445 ms 80216 KB Output is correct
19 Correct 584 ms 78928 KB Output is correct
20 Correct 754 ms 87428 KB Output is correct
21 Correct 779 ms 91220 KB Output is correct