oj.uz

Submission #1114383

# Submission time Handle Problem Language Result Execution time Memory
1114383 2024-11-18T18:07:04 Z Thunnus Žarulje (COI15_zarulje) C++17
100 / 100
 500 ms 436520 KB 
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 5;
int fact[MAXN], ifact[MAXN];

inline int binpow(int a, int b){
    int ret = 1;
    while(b){
        if(b & 1){
            ret = (ret * a) % MOD;
        }
        a = (a * a) % MOD;
        b >>= 1;
    }
    return ret;
}

inline int comb(int a, int b){
    int ret = (((fact[a] * ifact[b]) % MOD) * ifact[a - b]) % MOD;
    return ret;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    fact[0] = 1;
    for(int i = 1; i < MAXN; i++){
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    ifact[MAXN - 1] = binpow(fact[MAXN - 1], MOD - 2);
    for(int i = MAXN - 2; i >= 0; i--){
        ifact[i] = (ifact[i + 1] * (i + 1)) % MOD;
    }
    int n, k;
    cin >> n >> k;
    vi a(n + 1), b(k);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int &i : b){
        cin >> i;
    }

    vector<stack<pii>> to_le(n + 1), to_ri(n + 1);
    for(int i = 2; i <= n; i++){
        to_le[i] = to_le[i - 1];
        while(!to_le[i].empty() && a[i - 1] < to_le[i].top().fi){
            to_le[i].pop();
        }
        int cnt = 1;
        while(!to_le[i].empty() && a[i - 1] == to_le[i].top().fi){
            cnt += to_le[i].top().se;
            to_le[i].pop();
        }
        to_le[i].emplace(a[i - 1], cnt);
    }

    for(int i = n - 1; i >= 1; i--){
        to_ri[i] = to_ri[i + 1];
        while(!to_ri[i].empty() && a[i + 1] < to_ri[i].top().fi){
            to_ri[i].pop();
        }
        int cnt = 1;
        while(!to_ri[i].empty() && a[i + 1] == to_ri[i].top().fi){
            cnt += to_ri[i].top().se;
            to_ri[i].pop();
        }
        to_ri[i].emplace(a[i + 1], cnt);
    }

    vi ans(n + 1);
    for(int i = 0; i < k; i++){
        if(!ans[b[i]]){
            int res = 1;
            while(!to_le[b[i]].empty() && !to_ri[b[i]].empty()){
                if(to_le[b[i]].top().fi > to_ri[b[i]].top().fi){
                    to_le[b[i]].pop();
                }
                else if(to_ri[b[i]].top().fi > to_le[b[i]].top().fi){
                    to_ri[b[i]].pop();
                }
                else{
                    int cntl = to_le[b[i]].top().se, cntr = to_ri[b[i]].top().se;
                    res = (res * comb(cntl + cntr, cntr)) % MOD;
                    to_le[b[i]].pop(), to_ri[b[i]].pop();
                }
            }
            ans[b[i]] = res;
        }
        cout << ans[b[i]] << "\n";
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3664 KB Output is correct
2 Correct 6 ms 5712 KB Output is correct
3 Correct 8 ms 7776 KB Output is correct
4 Correct 10 ms 7760 KB Output is correct
5 Correct 9 ms 7760 KB Output is correct
6 Correct 9 ms 7928 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 217416 KB Output is correct
2 Correct 392 ms 427164 KB Output is correct
3 Correct 382 ms 431020 KB Output is correct
4 Correct 387 ms 431432 KB Output is correct
5 Correct 374 ms 432016 KB Output is correct
6 Correct 376 ms 431896 KB Output is correct
7 Correct 393 ms 431944 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3664 KB Output is correct
2 Correct 6 ms 5712 KB Output is correct
3 Correct 8 ms 7776 KB Output is correct
4 Correct 10 ms 7760 KB Output is correct
5 Correct 9 ms 7760 KB Output is correct
6 Correct 9 ms 7928 KB Output is correct
7 Correct 197 ms 217416 KB Output is correct
8 Correct 392 ms 427164 KB Output is correct
9 Correct 382 ms 431020 KB Output is correct
10 Correct 387 ms 431432 KB Output is correct
11 Correct 374 ms 432016 KB Output is correct
12 Correct 376 ms 431896 KB Output is correct
13 Correct 393 ms 431944 KB Output is correct
14 Correct 29 ms 25168 KB Output is correct
15 Correct 244 ms 219776 KB Output is correct
16 Correct 459 ms 431940 KB Output is correct
17 Correct 494 ms 433436 KB Output is correct
18 Correct 444 ms 436520 KB Output is correct
19 Correct 477 ms 433680 KB Output is correct
20 Correct 481 ms 435140 KB Output is correct
21 Correct 500 ms 435272 KB Output is correct