Submission #1116302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116302		michified	Žarulje (COI15_zarulje)	C++17	100 / 100	92 ms	28644 KiB

zarulje

#include <bits/stdc++.h>
#define ll long long
#define db double
#define imx INT_MAX
#define imn INT_MIN
#define lmx LLONG_MAX
#define lmn LLONG_MIN
#define ld long double
#define lid id * 2 + 1
#define rid id * 2 + 2
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> 
#define ordered_llset tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> 

const ll mod = 1e9 + 7, maxv = 2e5;
vector<ll> fact(maxv + 1), inv(maxv + 1);

ll exp(ll x, ll k) {
    if (k == 0) return 1;
    return (exp((x * x) % mod, k >> 1) * (k & 1 ? x : 1)) % mod;
}

ll ncr(ll n, ll r) {
    return fact[n] * inv[r] % mod * inv[n - r] % mod;
}

void edit(ll& a, ll b, ll d, ll& cur) {
    cur = cur * fact[a] % mod * fact[b] % mod * inv[a + b] % mod;
    a += d;
    cur = cur * inv[a] % mod * inv[b] % mod * fact[a + b] % mod;
}

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

    fact[0] = 1;
    for (ll i = 1; i <= maxv; i++) fact[i] = fact[i - 1] * i % mod;
    inv[maxv] = exp(fact[maxv], mod - 2);
    for (ll i = maxv - 1; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % mod;

    ll n, k, i;
    cin >> n >> k;
    vector<ll> a(n);
    for (i = 0; i < n; i++) cin >> a[i];
    vector<vector<pair<ll, ll>>> delta(n);
    stack<ll> st;
    for (i = n - 1; i >= 0; i--) {
        while (not st.empty() and a[i] < st.top()) {
            delta[i].push_back({st.top(), 1ll});
            st.pop();
        }
        delta[i].push_back({a[i], -1ll});
        st.push(a[i]);
    }
    vector<ll> lcnt(maxv + 1), rcnt(maxv + 1), ans(n);
    while (not st.empty()) {
        rcnt[st.top()]++;
        st.pop();
    }
    ll cur = 1;
    for (i = 0; i < n; i++) {
        for (auto& elem : delta[i]) edit(rcnt[elem.first], lcnt[elem.first], elem.second, cur);
        ans[i] = cur;
        while (not st.empty() and a[i] < st.top()) {
            edit(lcnt[st.top()], rcnt[st.top()], -1, cur);
            st.pop();
        }
        edit(lcnt[a[i]], rcnt[a[i]], 1, cur);
        st.push(a[i]);
    }
    while (k--) {
        cin >> cur;
        cout << ans[cur - 1] << ' ';
    }
    return 0; 
}

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