Submission #1295546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295546		uranium235	Žarulje (COI15_zarulje)	C++17	60 / 100	30 ms	4300 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;
}

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);

    auto push = [&](vector<pair<int, int>> &s, int x) -> void {
        while (s.back().first > x) {
            s.pop_back();
        }
        if (s.back().first == x) {
            s.back().second++;
        } else {
            s.push_back({x, 1});
        }
    };

    while (k--) {
        int q;
        cin >> q;
        q--;

        vector<pair<int, int>> l, r;
        l.push_back({0, 1}), r.push_back({0, 1});
        for (int i = 0; i < q; i++) {
            push(l, a[i]);
        }
        for (int i = n - 1; i > q; i--) {
            push(r, a[i]);
        }

        int ptr = 0;
        ll ans = 1;
        for (pair<int, int> &p : l) {
            while (ptr < r.size() && r[ptr].first < p.first) {
                ptr++;
            }
            if (ptr == r.size()) break;

            if (p.first == r[ptr].first && p.first != 0) {
                int a = p.second, b = r[ptr].second;
                ans = ans * comb(a + b, b) % mod;
            }
        }

        cout << ans << '\n';
    }   
}

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