oj.uz

Submission #1016798

# Submission time Handle Problem Language Result Execution time Memory
1016798 2024-07-08T12:30:31 Z TAhmed33 Žarulje (COI15_zarulje) C++
60 / 100
 1000 ms 13244 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 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];
void solve () {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    while (k--) {
        int x; cin >> x;
        map <int, int> f, g;
        int mn = 1e9;
        for (int i = x - 1; i >= 1; i--) {
            if (a[i] <= mn) {
                mn = a[i];
                f[mn]++;
            }
        }
        mn = 1e9;
        for (int i = x + 1; i <= n; i++) {
            if (a[i] <= mn) {
                mn = a[i];
                g[mn]++;
            }
        }
        int ans = 1;
        for (auto i : f) {
            ans = mul(ans, nCr(g[i.first] + i.second, i.second));
        }
        cout << ans << '\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 11 ms 9820 KB Output is correct
2 Correct 11 ms 9820 KB Output is correct
3 Correct 15 ms 9820 KB Output is correct
4 Correct 16 ms 9820 KB Output is correct
5 Correct 13 ms 9936 KB Output is correct
6 Correct 15 ms 9988 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12376 KB Output is correct
2 Correct 21 ms 12380 KB Output is correct
3 Correct 19 ms 12636 KB Output is correct
4 Correct 22 ms 12800 KB Output is correct
5 Correct 22 ms 13148 KB Output is correct
6 Correct 22 ms 13172 KB Output is correct
7 Correct 26 ms 13244 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9820 KB Output is correct
2 Correct 11 ms 9820 KB Output is correct
3 Correct 15 ms 9820 KB Output is correct
4 Correct 16 ms 9820 KB Output is correct
5 Correct 13 ms 9936 KB Output is correct
6 Correct 15 ms 9988 KB Output is correct
7 Correct 16 ms 12376 KB Output is correct
8 Correct 21 ms 12380 KB Output is correct
9 Correct 19 ms 12636 KB Output is correct
10 Correct 22 ms 12800 KB Output is correct
11 Correct 22 ms 13148 KB Output is correct
12 Correct 22 ms 13172 KB Output is correct
13 Correct 26 ms 13244 KB Output is correct
14 Correct 81 ms 10076 KB Output is correct
15 Execution timed out 1031 ms 12880 KB Time limit exceeded
16 Halted 0 ms 0 KB -