oj.uz

Submission #1116302

# Submission time Handle Problem Language Result Execution time Memory
1116302 2024-11-21T13:08:04 Z michified Žarulje (COI15_zarulje) C++17
100 / 100
 92 ms 28644 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6480 KB Output is correct
2 Correct 7 ms 6736 KB Output is correct
3 Correct 8 ms 6904 KB Output is correct
4 Correct 8 ms 6736 KB Output is correct
5 Correct 8 ms 6736 KB Output is correct
6 Correct 8 ms 6736 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15952 KB Output is correct
2 Correct 59 ms 24912 KB Output is correct
3 Correct 63 ms 25168 KB Output is correct
4 Correct 66 ms 25524 KB Output is correct
5 Correct 70 ms 25672 KB Output is correct
6 Correct 67 ms 25788 KB Output is correct
7 Correct 71 ms 25928 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6480 KB Output is correct
2 Correct 7 ms 6736 KB Output is correct
3 Correct 8 ms 6904 KB Output is correct
4 Correct 8 ms 6736 KB Output is correct
5 Correct 8 ms 6736 KB Output is correct
6 Correct 8 ms 6736 KB Output is correct
7 Correct 36 ms 15952 KB Output is correct
8 Correct 59 ms 24912 KB Output is correct
9 Correct 63 ms 25168 KB Output is correct
10 Correct 66 ms 25524 KB Output is correct
11 Correct 70 ms 25672 KB Output is correct
12 Correct 67 ms 25788 KB Output is correct
13 Correct 71 ms 25928 KB Output is correct
14 Correct 12 ms 7760 KB Output is correct
15 Correct 48 ms 17484 KB Output is correct
16 Correct 82 ms 28232 KB Output is correct
17 Correct 75 ms 26948 KB Output is correct
18 Correct 86 ms 28644 KB Output is correct
19 Correct 77 ms 26696 KB Output is correct
20 Correct 92 ms 27520 KB Output is correct
21 Correct 90 ms 27720 KB Output is correct