Submission #1309937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309937		jg86	Žarulje (COI15_zarulje)	C++20	100 / 100	51 ms	13280 KiB

zarulje

#include <bits/stdc++.h>
using namespace std;

static const int MOD = 1000000007;

static long long mod_pow(long long a, long long e) {
    long long r = 1 % MOD;
    a %= MOD;
    while (e > 0) {
        if (e & 1) r = (r * a) % MOD;
        a = (a * a) % MOD;
        e >>= 1;
    }
    return r;
}

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

    int N, K;
    cin >> N >> K;

    vector<int> A(N + 1);
    int maxV = 0;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
        maxV = max(maxV, A[i]);
    }

    vector<int> P(K);
    for (int i = 0; i < K; i++) cin >> P[i];

    // Precompute factorials and inverse factorials up to N
    vector<long long> fact(N + 1), invfact(N + 1);
    fact[0] = 1;
    for (int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i % MOD;
    invfact[N] = mod_pow(fact[N], MOD - 2);
    for (int i = N; i >= 1; i--) invfact[i - 1] = invfact[i] * i % MOD;

    auto C = [&](int n, int k) -> long long {
        if (k < 0 || k > n) return 0;
        return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD;
    };
    // modular inverse of C(n,k) without pow:
    // inv(C(n,k)) = invfact[n] * fact[k] * fact[n-k]
    auto invC = [&](int n, int k) -> long long {
        if (k < 0 || k > n) return 0;
        return invfact[n] * fact[k] % MOD * fact[n - k] % MOD;
    };

    // Build "right events" in one flat array to avoid 200k vector allocations:
    // events for i = segment [evStart[i], evEnd[i]) in evFlat.
    vector<int> evStart(N + 2), evEnd(N + 2);
    vector<pair<int,int>> evFlat;
    evFlat.reserve(2 * N + 5);

    vector<int> stIdx; // monotone stack of indices
    stIdx.reserve(N);

    for (int i = N; i >= 1; i--) {
        evStart[i] = (int)evFlat.size();

        while (!stIdx.empty() && A[stIdx.back()] > A[i]) {
            evFlat.push_back({A[stIdx.back()], -1}); // popped
            stIdx.pop_back();
        }
        evFlat.push_back({A[i], +1}); // pushed
        stIdx.push_back(i);

        evEnd[i] = (int)evFlat.size();
    }

    // cntL / cntR are counts of record-minima values on left/right of current p
    vector<int> cntL(maxV + 1, 0), cntR(maxV + 1, 0);

    // Initialize cntR to record-minima of suffix starting at 1 (stack content after full build)
    for (int idx : stIdx) cntR[A[idx]]++;

    long long ans = 1; // product of C(L+R, L), initially all L=0 => 1

    auto updateValue = [&](int v, int deltaL, int deltaR) {
        int oldL = cntL[v];
        int oldR = cntR[v];

        // remove old contribution
        ans = ans * invC(oldL + oldR, oldL) % MOD;

        // apply deltas
        cntL[v] = oldL + deltaL;
        cntR[v] = oldR + deltaR;

        int newL = cntL[v];
        int newR = cntR[v];

        // add new contribution
        ans = ans * C(newL + newR, newL) % MOD;
    };

    vector<long long> M(N + 1);
    vector<int> leftStack; // store left record-minima values (monotone non-decreasing stack)
    leftStack.reserve(N);

    for (int p = 1; p <= N; p++) {
        // Move right-suffix start from p to p+1 by applying inverse events of position p
        // (events are defined for extending suffix leftward; we undo them to move start rightward)
        for (int e = evStart[p]; e < evEnd[p]; e++) {
            int v = evFlat[e].first;
            int t = evFlat[e].second; // +1 push, -1 pop (in build direction)
            updateValue(v, 0, -t);    // inverse
        }

        // Now cntL/cntR correspond to left of p and right of p, so store answer
        M[p] = ans;

        // Prepare cntL for next position (p+1): insert A[p] into left record-minima stack
        int x = A[p];
        while (!leftStack.empty() && leftStack.back() > x) {
            updateValue(leftStack.back(), -1, 0);
            leftStack.pop_back();
        }
        updateValue(x, +1, 0);
        leftStack.push_back(x);
    }

    // Output answers for queries
    for (int i = 0; i < K; i++) {
        if (i) cout << ' ';
        cout << M[P[i]];
    }
    cout << '\n';

    return 0;
}

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