Submission #1295831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295831		uranium235	Žarulje (COI15_zarulje)	C++17	60 / 100	44 ms	20484 KiB

zarulje

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1'000'000'007;

ll pow(ll x, int p) {
    ll res = 1;
    while (p > 0) {
        if (p % 2) res = res * x % mod;
        x = x * x % mod;
        p /= 2;
    }
    return res;
}

struct node {
    int x, y;
    bool rem;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<ll> fac(n + 1), inv(n + 1);
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
    inv[n] = pow(fac[n], mod - 2);
    for (int i = n - 1; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % mod;

    auto comb = [&](int n, int k) -> ll {
        return (fac[n] * inv[k] % mod) * inv[n - k] % mod;
    };
    auto bmoc = [&](int n, int k) -> ll {
        return (inv[n] * fac[k] % mod) * fac[n - k] % mod;
    };

    assert(n * k <= 4e6);

    vector<vector<node>> log(n);
    vector<pair<int, int>> s;
    s.push_back({0, 1});
    for (int i = n - 1; i >= 0; i--) {
        while (s.back().first > a[i]) {
            // add in reverse
            log[i].push_back({s.back().first, s.back().second, false});
            s.pop_back();
        }
        if (s.back().first == a[i]) {
            // remove then add
            log[i].push_back({s.back().first, s.back().second, false});
            log[i].push_back({-1, -1, true});
            s.back().second++;
        } else {
            // remove in reverse
            log[i].push_back({-1, -1, true});
            s.push_back({a[i], 1});
        }
        reverse(log[i].begin(), log[i].end());
    }

    vector<ll> ans(n);
    vector<pair<int, int>> r;
    r.push_back({0, 1});
    vector<int> fa(n + 1), fb(n + 1);
    ll cur = 1;
    auto seta = [&](int i, int x) -> void {
        cur = cur * bmoc(fa[i] + fb[i], fa[i]) % mod;
        fa[i] = x;
        cur = cur * comb(fa[i] + fb[i], fa[i]) % mod;
    };
    auto setb = [&](int i, int x) -> void {
        cur = cur * bmoc(fa[i] + fb[i], fa[i]) % mod;
        fb[i] = x;
        cur = cur * comb(fa[i] + fb[i], fa[i]) % mod;
    };

    for (int i = 0; i < n; i++) {
        for (node &j : log[i]) {
            if (j.rem) {
                setb(s.back().first, 0);
                s.pop_back();
            } else {
                setb(j.x, j.y);
                s.push_back({j.x, j.y});
            }
        }

        ans[i] = cur;

        while (r.back().first > a[i]) {
            seta(r.back().first, 0);
            r.pop_back();
        }
        if (r.back().first == a[i]) {
            seta(r.back().first, r.back().second + 1);
            r.back().second++;
        } else {
            seta(a[i], 1);
            r.push_back({a[i], 1});
        }
    }

    while (k--) {
        int q;
        cin >> q;
        q--;
        cout << ans[q] << '\n';
    }
}

• Subtask 1: 22 / 22
• Subtask 2: 38 / 38
• Subtask 3: 0 / 40