Submission #1016818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016818		TAhmed33	Žarulje (COI15_zarulje)	C++98	100 / 100	780 ms	91220 KiB

zarulje

#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 / 22
• Subtask 2: 38 / 38
• Subtask 3: 40 / 40