oj.uz

Submission #227187

# Submission time Handle Problem Language Result Execution time Memory
227187 2020-04-26T12:09:28 Z dolphingarlic Žarulje (COI15_zarulje) C++14
100 / 100
 159 ms 26232 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

const ll MOD = 1e9 + 7;

const ll mult(const ll &A, const ll &B) { return (A * B) % MOD; }

int a[200002], l_cnt[200002], r_cnt[200002];
ll fact[200002]{1}, inv_fact[200002]{1}, ans[200002]{1};
vector<int> l_ers[200002], r_ers[200002];

const ll choose(const ll &A, const ll &B) { return mult(mult(fact[A], inv_fact[B]), inv_fact[A - B]); }

const ll inv_choose(const ll &A, const ll &B) { return mult(mult(inv_fact[A], fact[B]), fact[A - B]); }

ll expo(ll A, ll B) {
    ll ans = 1;
    while (B) {
        if (B & 1) ans = mult(ans, A);
        A = mult(A, A);
        B >>= 1;
    }
    return ans;
}

void update(int pos, int val, bool l, bool add) {
    ans[pos] = mult(ans[pos], inv_choose(l_cnt[val] + r_cnt[val], l_cnt[val]));
    if (l) {
        if (add) l_cnt[val]++;
        else l_cnt[val]--;
    } else {
        if (add) r_cnt[val]++;
        else r_cnt[val]--;
    }
    ans[pos] = mult(ans[pos], choose(l_cnt[val] + r_cnt[val], l_cnt[val]));
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    FOR(i, 1, n + 1) {
        cin >> a[i];
        fact[i] = mult(fact[i - 1], i);
        inv_fact[i] = expo(fact[i], MOD - 2);
    }
    
    stack<int> stck;
    FOR(i, 1, n + 1) {
        while (stck.size() && stck.top() > a[i]) {
            l_ers[i].push_back(stck.top());
            stck.pop();
        }
        stck.push(a[i]);
    }
    while (stck.size()) stck.pop();
    for (int i = n; i; i--) {
        while (stck.size() && stck.top() > a[i]) {
            r_ers[i].push_back(stck.top());
            r_cnt[stck.top()]--;
            stck.pop();
        }
        stck.push(a[i]);
        r_cnt[a[i]]++;
    }

    FOR(i, 1, n + 1) {
        ans[i] = ans[i - 1];
        if (i > 1) {
            update(i, a[i - 1], 1, 1);
            for (int j : l_ers[i - 1]) update(i, j, 1, 0);
        }
        update(i, a[i], 0, 0);
        for (int j : r_ers[i]) update(i, j, 0, 1);
    }

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

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9728 KB Output is correct
2 Correct 11 ms 9856 KB Output is correct
3 Correct 13 ms 9984 KB Output is correct
4 Correct 11 ms 9984 KB Output is correct
5 Correct 13 ms 9856 KB Output is correct
6 Correct 11 ms 9856 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 16120 KB Output is correct
2 Correct 98 ms 21496 KB Output is correct
3 Correct 98 ms 22264 KB Output is correct
4 Correct 101 ms 22520 KB Output is correct
5 Correct 105 ms 22776 KB Output is correct
6 Correct 111 ms 23672 KB Output is correct
7 Correct 120 ms 24568 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9728 KB Output is correct
2 Correct 11 ms 9856 KB Output is correct
3 Correct 13 ms 9984 KB Output is correct
4 Correct 11 ms 9984 KB Output is correct
5 Correct 13 ms 9856 KB Output is correct
6 Correct 11 ms 9856 KB Output is correct
7 Correct 59 ms 16120 KB Output is correct
8 Correct 98 ms 21496 KB Output is correct
9 Correct 98 ms 22264 KB Output is correct
10 Correct 101 ms 22520 KB Output is correct
11 Correct 105 ms 22776 KB Output is correct
12 Correct 111 ms 23672 KB Output is correct
13 Correct 120 ms 24568 KB Output is correct
14 Correct 16 ms 10496 KB Output is correct
15 Correct 82 ms 17656 KB Output is correct
16 Correct 149 ms 24824 KB Output is correct
17 Correct 124 ms 23928 KB Output is correct
18 Correct 155 ms 25720 KB Output is correct
19 Correct 133 ms 23928 KB Output is correct
20 Correct 159 ms 25336 KB Output is correct
21 Correct 151 ms 26232 KB Output is correct